Discrete Methods used in Graph Theory and Linear Programming
Research output: Thesis › Doctoral Thesis (monograph)
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ösSós conjecture and LoeblKomlósSó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 ndimensional 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.
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ösSós conjecture and LoeblKomlósSó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 ndimensional 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.
Details
Authors  

Organisations  
Research areas and keywords  Subject classification (UKÄ) – MANDATORY
Keywords

Original language  English 

Qualification  Doctor 
Awarding Institution  
Supervisors/Assistant supervisor 

Award date  2007 Jun 1 
Publisher 

Print ISBNs  9789162871581 
Publication status  Published  2007 
Publication category  Research 
Bibliographic note
Defence details
Date: 20070601
Time: 13:15
Place: Sal B, Matematikcentrum Sölvegatan 18 Lunds Tekniska Högskola
External reviewer(s)
Name: ShaweTaylor, John
Title: Professor
Affiliation: University College London, Storbritannien
