A common extension of the Erdős-Stone theorem and the Alon-Yuster theorem for unbounded graphs (Q697080): Difference between revisions

The theorems of Erdős-Stone and Alon-Yuster are two fundamental results of extremal graph theory that ensure the existence of either one or several vertex-disjoint copies of some fixed graph \(H\) in a graph \(G\) that satisfies some condition on its minimum degree (or size) depending on the order and the chromatic number of \(H\). Recently, Komlós gave a common generalization of these results in which the order of \(H\) is fixed. In the present deep paper, the author proves the following common generalization allowing the order of \(H\) to grow with the order of \(G\): For every \(\varepsilon >0\) and \(r\geq 2\), there exist \(c>0\) and \(n_0\) such that, for any \(0\leq \theta \leq 1\), if \(H\) is a graph of order \(|H|\leq c \log n\) and chromatic number \(\chi(H)\leq r\) then every graph \(G\) of order \(n>n_0\) and with minimum degree \(\delta(G)\geq (1-\frac{1}{r-1}+\frac{\theta}{r(r-1)})n\) contains at least \((\theta-\varepsilon)n/|H|\) vertex-disjoint copies of \(H\). The special cases \(\theta=\varepsilon r(r-1)\) and \(\theta=1\) imply the above-mentioned results and the given bounds \(c \log n\) and \((1-\frac{1}{r-1}+\frac{\theta}{r(r-1)})n\) are essentially best-possible. The proof uses Szemerédi's regularity lemma.