RUcore Resource Object
RUcore Resource Object
PDF-1(682.27 KB)
TitleSpanning subgraphs in graphs and hypergraphs
NameKhan, Imdadullah (author), Szemeredi, Endre (chair), Steiger, William (internal member), Grigoriadis, Michael (internal member), Reed, Bruce (outside member), Rutgers University, Graduate School - New Brunswick,
Degree Date2011-05
Date Created2011
SubjectComputer Science,
Graph theory,
Hypergraphs
DescriptionThis thesis consists of three new fundamental results on the existence of spanning subgraphs in graphs and hypergraphs. Cycle Factors in Graphs: A classical conjecture of El-Zahar states that if H is a graph consisting of r vertex disjoint cycles of length n_1, n_2, ldots , n_r, and G is a graph on n = n_1+n_2 + ... +n_r vertices with minimum degree at least [sigmar/i=1 n_1/2
then G contains H as a subgraph. A proof of this conjecture for graphs withn[greater than or less than] n_0 was announced by S. Abbasi (1998) using the Regularity Lemma-Blow-up Lemma method. We give a new, ``de-regularized" proof of the conjecture for large graphs that avoids the use of the Regularity Lemma, and thus the resulting n_0 is much smaller. Perfect Matching in three-uniform hypergraphs A perfect matching in a three-uniform hypergraph on n=3k vertices is a subset of n/3 disjoint edges. We prove that if $H$ is a three-uniform hypergraph on $n=3k$ vertices such that every vertex belongs to at least {n-1choose 2} - {2n/3choose 2}+1 edges, then H contains a perfect matching. We give a construction to show that our result is best possible. Perfect Matching in four-uniform hypergraphs A perfect matching in a four-uniform hypergraph is a subset of lfloorfrac{n}{4}
floor disjoint edges. We prove that if H is a sufficiently large four-uniform hypergraph on n=4k vertices such that every vertex belongs to more than ${n-1choose 3} - {3n/4 choose 3} edges, then H contains a perfect matching. Our bound is tight and settles a conjecture of Hán, Person and Schacht (2009).
then G contains H as a subgraph. A proof of this conjecture for graphs withn[greater than or less than] n_0 was announced by S. Abbasi (1998) using the Regularity Lemma-Blow-up Lemma method. We give a new, ``de-regularized" proof of the conjecture for large graphs that avoids the use of the Regularity Lemma, and thus the resulting n_0 is much smaller. Perfect Matching in three-uniform hypergraphs A perfect matching in a three-uniform hypergraph on n=3k vertices is a subset of n/3 disjoint edges. We prove that if $H$ is a three-uniform hypergraph on $n=3k$ vertices such that every vertex belongs to at least {n-1choose 2} - {2n/3choose 2}+1 edges, then H contains a perfect matching. We give a construction to show that our result is best possible. Perfect Matching in four-uniform hypergraphs A perfect matching in a four-uniform hypergraph is a subset of lfloorfrac{n}{4}
floor disjoint edges. We prove that if H is a sufficiently large four-uniform hypergraph on n=4k vertices such that every vertex belongs to more than ${n-1choose 3} - {3n/4 choose 3} edges, then H contains a perfect matching. Our bound is tight and settles a conjecture of Hán, Person and Schacht (2009).
NotePh.D.
NoteIncludes bibliographical references
NoteIncludes vita
Noteby Imdadullah Khan
Genretheses
Persistent URLhttp://hdl.rutgers.edu/1782.1/rucore10001600001.ETD.000061299
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.