文摘
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 n1, n2, ..., nr, and G is a graph on n ＝ n1 ＋ n2 ＋ ... ＋ nr vertices with minimum degree at least i＝1r&ceill0； ni/2 &ceilr0； , then G contains H as a subgraph. A proof of this conjecture for graphs with n &ge； n0 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 n0 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 n3 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-12 -2n/32 ＋ 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 &fll0；n4&flr0； 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-13 -3n/43 edges, then H contains a perfect matching. Our bound is tight and settles a conjecture of Han, Person and Schacht 2009).
