RUcore Resource Object
RUcore Resource Object
PDF-1(329.70 KB)
TitleSome problems in extremal graph theory avoiding the use of the regularity lemma
NameLevitt, Ian Marc (author), Szemeredi, Endre (chair), Komlos, Janos (internal member), Saks, Michael (internal member), Magyar, Akos (outside member), Rutgers University, Graduate School - New Brunswick,
Degree Date2009-05
Date Created2009
SubjectMathematics,
Extremal problems (Mathematics),
Graph theory
DescriptionIn this thesis we present two results in Extremal Graph Theory. The first result is a new proof of a conjecture of Bollobas on embedding trees of bounded degree. The second result is a new proof of the Posa conjecture.
Let G=(W,E) be a graph on n vertices having minimum degree at least n/2 + c log(n), where c is a constant. Bela Bollobas conjectured that every tree on n vertices with bounded degree can be embedded into G. We show that this conjecture is true. In fact we show more, that unless G is very close to either the union of two complete graphs on n/2 vertices, or the complement, then a minimum degree of n/2 is sufficient to embed any tree of bounded degree.
The k-th power of C is the graph obtained from C by joining every pair of vertices at a distance at most k in C. In 1962 Posa conjectured that any graph G of order n and minimum degree at least 2n/3 contains the square of a Hamiltonian cycle. The conjecture was proven for n > n_0 by Komlos, Sarkozy and Szemeredi using the Regularity Lemma and Blow-up Lemma. The new proof removes the use of the Regularity Lemma and establishes the Posa conjecture using combinatorial arguments, thus vastly reducing n_0.
Let G=(W,E) be a graph on n vertices having minimum degree at least n/2 + c log(n), where c is a constant. Bela Bollobas conjectured that every tree on n vertices with bounded degree can be embedded into G. We show that this conjecture is true. In fact we show more, that unless G is very close to either the union of two complete graphs on n/2 vertices, or the complement, then a minimum degree of n/2 is sufficient to embed any tree of bounded degree.
The k-th power of C is the graph obtained from C by joining every pair of vertices at a distance at most k in C. In 1962 Posa conjectured that any graph G of order n and minimum degree at least 2n/3 contains the square of a Hamiltonian cycle. The conjecture was proven for n > n_0 by Komlos, Sarkozy and Szemeredi using the Regularity Lemma and Blow-up Lemma. The new proof removes the use of the Regularity Lemma and establishes the Posa conjecture using combinatorial arguments, thus vastly reducing n_0.
NotePh.D.
NoteIncludes bibliographical references (p. 57-58)
Noteby Ian Marc Levitt
Genretheses
Persistent URLhttp://hdl.rutgers.edu/1782.2/rucore10001600001.ETD.000051368
Languageeng
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.