Tight connectivity and shadow densities in generalized Erdős--Rogers problems

Abstract

Let \(F\) and \(G\) be \(r\)-uniform hypergraphs, and let \(f_{F,G}(n)\) be the largest integer \(m\) such that every \(n\)-vertex \(G\)-free \(r\)-graph contains an induced \(F\)-free subgraph on \(m\) vertices. We prove that, for \(r\ge3\) and \(2\le k\le r-1\), if \(F\) is nonempty, \(G\) is \(k\)-tightly connected, and there is no homomorphism from \(G\) to \(F\) (that is, \(G\not\to F\)), then \[ f_{F,G}(n)\le C(\log n)^{β_F^{(k)}}, \qquad β_F^{(k)}= \max_{\emptyset\ne P\subseteq\partial_kF} \frac{e(P)}{v(P)-1}. \] The case \(r=3\) of our result resolves a conjecture of He and Nie. As a consequence, we obtain the Ramsey lower bound \(r(G,K_n^r)\ge2^{Ω\bigl(n^{(r-1)/\binom rk}\bigr)}\) for every \(k\)-tightly connected non-\(r\)-partite \(r\)-graph \(G\). This extends a result of Conlon, Fox, Gunby, He, Mubayi, Suk, Verstraëte and Yu from the \(3\)-uniform setting.

13 pages