TY - JOUR TI - Spanning subgraphs in graphs and hypergraphs DO - https://doi.org/doi:10.7282/T3C24VSC PY - 2011 AB - This 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). KW - Computer Science KW - Graph theory KW - Hypergraphs LA - eng ER -