Komlós's tiling theorem via graphon covers |
| |
Authors: | Jan Hladký Ping Hu Diana Piguet |
| |
Institution: | 1. Institute of Mathematics, Czech Academy of Science, ?itná 25, 110 2. 00 Praha, Czech Republic;3. Department of Computer Science, University of Warwick, Coventry, CV4 7AL United Kingdom
Present address: School of Mathematics, Sun Yat-sen University, Guangzhou 510275, China;4. The Czech Academy of Sciences, Institute of Computer Science, Pod Vodárenskou vě?í 2, 182 5. 07 Prague Czech Republic |
| |
Abstract: | Komlós Komlós: Tiling Turán Theorems, Combinatorica, 2000] determined the asymptotically optimal minimum-degree condition for covering a given proportion of vertices of a host graph by vertex-disjoint copies of a fixed graph H, thus essentially extending the Hajnal–Szemerédi theorem that deals with the case when H is a clique. We give a proof of a graphon version of Komlós's theorem. To prove this graphon version, and also to deduce from it the original statement about finite graphs, we use the machinery introduced in Hladký, Hu, Piguet: Tilings in graphons, arXiv:1606.03113]. We further prove a stability version of Komlós's theorem. |
| |
Keywords: | extremal graph theory graphon graph tiling |
|
|