Advanced

Discrete Methods used in Graph Theory and Linear Programming

Barr, Olof LU (2007)
Abstract
The content of the thesis is divided into two parts; graph theory and linear programming.



The main results in the first part concerns extremal graph theory. Here we want to determine the number of edges in a graph needed to ensure the existence of certain local structures. Upper and lower bounds are given for the number of edges in a graph to ensure triangles and quadrilaterals respectively, when a transition system defined through local edge colourings is taken in account. Partial results on the Erdös-Sós conjecture and Loebl-Komlós-Sós conjecture are given in the affirmative, both for new classes of graphs and for new classes of trees. A proof that every complete graph without monochromatic triangles contains a... (More)
The content of the thesis is divided into two parts; graph theory and linear programming.



The main results in the first part concerns extremal graph theory. Here we want to determine the number of edges in a graph needed to ensure the existence of certain local structures. Upper and lower bounds are given for the number of edges in a graph to ensure triangles and quadrilaterals respectively, when a transition system defined through local edge colourings is taken in account. Partial results on the Erdös-Sós conjecture and Loebl-Komlós-Sós conjecture are given in the affirmative, both for new classes of graphs and for new classes of trees. A proof that every complete graph without monochromatic triangles contains a properly coloured hamiltonian path is also given.



In linear programming we study the perceptron algorithm and different modifications in detail, including some geometrical properties of the unit sphere in higher dimensions. An optimal lower bound on the probability that two n-dimensional unit vectors have an inner product of at least 1/sqrt{n} is proved. Modifications to increase the expected time taken by the algorithm with a factor n², compared to earlier algorithms, are made. Also, generalisations of different parts of the modified perceptron algorithm, to make it approximating a maximal margin, are constructed in the thesis. (Less)
Please use this url to cite or link to this publication:
author
supervisor
opponent
  • Professor Shawe-Taylor, John, University College London, Storbritannien
organization
publishing date
type
Thesis
publication status
published
subject
keywords
Mathematics, Perceptron Algorithm, Graph Theory, Linear Programming, Matematik
pages
114 pages
publisher
Centre for Mathematical Sciences, Lund University
defense location
Sal B, Matematikcentrum Sölvegatan 18 Lunds Tekniska Högskola
defense date
2007-06-01 13:15
ISSN
1404-0034
ISBN
978-91-628-7158-1
language
English
LU publication?
yes
id
20cb0301-7444-4249-9cee-ee0bf725142c (old id 26898)
date added to LUP
2007-06-05 13:44:05
date last changed
2016-09-19 08:44:55
@phdthesis{20cb0301-7444-4249-9cee-ee0bf725142c,
  abstract     = {The content of the thesis is divided into two parts; graph theory and linear programming.<br/><br>
<br/><br>
The main results in the first part concerns extremal graph theory. Here we want to determine the number of edges in a graph needed to ensure the existence of certain local structures. Upper and lower bounds are given for the number of edges in a graph to ensure triangles and quadrilaterals respectively, when a transition system defined through local edge colourings is taken in account. Partial results on the Erdös-Sós conjecture and Loebl-Komlós-Sós conjecture are given in the affirmative, both for new classes of graphs and for new classes of trees. A proof that every complete graph without monochromatic triangles contains a properly coloured hamiltonian path is also given.<br/><br>
<br/><br>
In linear programming we study the perceptron algorithm and different modifications in detail, including some geometrical properties of the unit sphere in higher dimensions. An optimal lower bound on the probability that two n-dimensional unit vectors have an inner product of at least 1/sqrt{n} is proved. Modifications to increase the expected time taken by the algorithm with a factor n², compared to earlier algorithms, are made. Also, generalisations of different parts of the modified perceptron algorithm, to make it approximating a maximal margin, are constructed in the thesis.},
  author       = {Barr, Olof},
  isbn         = {978-91-628-7158-1},
  issn         = {1404-0034},
  keyword      = {Mathematics,Perceptron Algorithm,Graph Theory,Linear Programming,Matematik},
  language     = {eng},
  pages        = {114},
  publisher    = {Centre for Mathematical Sciences, Lund University},
  school       = {Lund University},
  title        = {Discrete Methods used in Graph Theory and Linear Programming},
  year         = {2007},
}