首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号