PERFECT MATCHINGS, TILINGS AND HAMILTON CYCLES IN HYPERGRAPHS by

This thesis contains problems in finding spanning subgraphs in graphs, such as, perfect matchings, tilings and Hamilton cycles. First, we consider the tiling problems in graphs, which are natural generalizations of the matching problems. We give new proofs of the multipartite Hajnal-Szemerédi Theorem for the tripartite and quadripartite cases. Second, we consider Hamilton cycles in hypergraphs. In particular, we determine the minimum codegree thresholds for Hamilton `-cycles in large k-uniform hypergraphs for ` < k/2. We also determine the minimum vertex degree threshold for loose Hamilton cycle in large 3-uniform hypergraphs. These results generalize the well-known theorem of Dirac for graphs. Third, we determine the minimum codegree threshold for near perfect matchings in large k-uniform hypergraphs, thereby confirming a conjecture of Rödl, Ruciński and Szemerédi. We also show that the decision problem on whether a k-uniform hypergraph with certain minimum codegree condition contains a perfect matching can be solved in polynomial time, which solves a problem of Karpiński, Ruciński and Szymańska completely. At last, we determine the minimum vertex degree threshold for perfect tilings of C34 in large 3-uniform hypergraphs, where C34 is the unique 3-uniform hypergraph on four vertices with two edges