Discrete Methods used in Graph Theory and Linear Programming
(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ö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... (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ö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. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/26898
 author
 Barr, Olof ^{LU}
 supervisor

 Victor Ufnarovski ^{LU}
 opponent

 Professor ShaweTaylor, John, University College London, Storbritannien
 organization
 publishing date
 2007
 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
 20070601 13:15
 ISSN
 14040034
 ISBN
 9789162871581
 language
 English
 LU publication?
 yes
 id
 20cb0301744442499ceeee0bf725142c (old id 26898)
 date added to LUP
 20070605 13:44:05
 date last changed
 20160919 08:44:55
@phdthesis{20cb0301744442499ceeee0bf725142c, 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ö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.<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 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.}, author = {Barr, Olof}, isbn = {9789162871581}, issn = {14040034}, 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}, }