RUcore Resource Object
RUcore Resource Object
PDF-1(551.04 KB)
TitleEmbedding spanning subgraphs into large dense graphs
NameJamshed, Asif (author), Szemeredi, Endre (chair), Steiger, William (internal member), Grigoriadis, Michael (internal member), Abello, James (outside member), Rutgers University, Graduate School - New Brunswick,
Degree Date2010-10
Date Created2010
SubjectComputer Science,
Hamiltonian graph theory,
Spanning trees (Graph theory),
Embeddings (Mathematics)
DescriptionIn this thesis we are going to present some results on embedding spanning subgraphs into large dense graphs. Spanning Trees Bollob'as conjectured that if $G$ is a graph on $n$ vertices, $delta(G) geq (1/2 + epsilon) n$ for some $epsilon > 0$, and $T$ is a bounded degree tree on $n$ vertices, then $T$ is a subgraph of $G$. The problem was solved in the affirmative by Koml'os, S'ark"ozy and Szemer'edi for large graphs. They then strengthened their result, and showed that the maximum degree of $T$ need not be bounded: there exists a constant $c$ such that $T$ is a subgraph of $G$ if $Delta(T) leq cn / log n$, $delta(G) geq (1/2 + epsilon) n$ and $n$ is large. Both proofs are based on the Regularity Lemma-Blow-up Lemma Method. Recently, using other methods, it was shown that bounded degree trees embed into graphs with minimum degree $n/2 + C log n$, where $C$ is a constant depending on the maximum degree of $T$. Here we show that in general $n/2 + O(Delta(T) cdot log n)$ is sufficient for every $Delta(T) leq cn / log n$. We also show that this bound is tight for the two extreme values of $m$ i.e. when $m = C$ and when $m = cn / log n$. Powers of Hamiltonian Cycles In 1962 P'osa conjectured that if $delta(G) geq frac{2}{3}n$ then $G$ contains the square of a Hamiltonian cycle. Later, in 1974, Seymour generalized this conjecture: if $delta(G) geq (frac{k-1}{k})n$ then $G$ contains the $(k-1)$th power of a Hamiltonian cycle. In 1998 the conjecture was proved by Koml'os, S'ark"ozy and Szemer'edi for large graphs using the Regularity Lemma. We present a ``deregularised" proof of the P'osa-Seymour conjecture which results in a much lower threshold value for $n$, the size of the graph for which the conjecture is true. We hope that the tools used in this proof will push down the threshold value for $n$ to around 100 at which point we will be able to verify the conjecture for every $n$.
NotePh.D.
NoteIncludes bibliographical references
NoteIncludes vita
Noteby Asif Jamshed
Genretheses
Persistent URLhttp://hdl.rutgers.edu/1782.1/rucore10001600001.ETD.000056417
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.