A Ramsey–Turán theory for tilings in graphs
No TL;DR found
Abstract
For a k$$ k $$ ‐vertex graph F$$ F $$ and an n$$ n $$ ‐vertex graph G$$ G $$ , an F$$ F $$ ‐tiling in G$$ G $$ is a collection of vertex‐disjoint copies of F$$ F $$ in G$$ G $$ . For r∈ℕ$$ r\in \mathbb{N} $$ , the r$$ r $$ ‐independence number of G$$ G $$ , denoted αr(G)$$ {\alpha}_r(G) $$ , is the largest size of a Kr$$ {K}_r $$ ‐free set of vertices in G$$ G $$ . In this article, we discuss Ramsey–Turán‐type theorems for tilings where one is interested in minimum degree and independence number conditions (and the interaction between the two) that guarantee the existence of optimal F$$ F $$ ‐tilings. Our results unify and generalise previous results of Balogh–Molla–Sharifzadeh [Random Struct. Algoritm. 49 (2016), no. 4, 669–693], Nenadov–Pehova [SIAM J. Discret. Math. 34 (2020), no. 2, 1001–1010] and Balogh–McDowell–Molla–Mycroft [Comb. Probab. Comput. 27 (2018), no. 4, 449–474] on the subject.