We consider tiling problems for graphs and hypergraphs. For two graphs and , an -tiling of is a subgraph of consisting of only vertex disjoint copies of . By using the absorbing method, we give a short proof that in a balanced tripartite graph , if every vertex is adjacent to of the vertices in each of the other vertex partitions, then has a -tiling. Previously, Magyar and Martin [11] proved the same result (without ) by using the Regularity Lemma.
In a 3-uniform hypergraph , let denote the minimum number of edges that contain for all pairs of vertices. We show that if , there exists a -tiling that misses at most vertices of . On the other hand, we show that there exist hypergraphs such that and does not have a perfect -tiling. These extend the results of Pikhurko [12] on -tilings.
Identifer | oai:union.ndltd.org:GEORGIA/oai:digitalarchive.gsu.edu:math_theses-1112 |
Date | 01 August 2011 |
Creators | Lightcap, Andrew |
Publisher | Digital Archive @ GSU |
Source Sets | Georgia State University |
Detected Language | English |
Type | text |
Format | application/pdf |
Source | Mathematics Theses |
Page generated in 0.0017 seconds