Generalized Erd\H{o}s--Rogers problems for $r$-uniform hypergraphs
이 뉴스, 어떠셨어요?
한 번의 탭으로 반응을 남겨요 · 로그인 불필요
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, if \(r\ge3\), \(F\) is nonempty, \(G\) is \(2\)-tightly connected, and there is no homomorphism from \(G\) to \(F\), then \[
f_{F,G}(n)\le C(\log n)^{\beta_F},
\qquad
\beta_F=
\max_{\substack{\emptyset\ne P\subseteq\partial_2F}}
\frac{e(P)}{v(P)-1}. \] For \(r=3\), this confirms a conjecture of He and Nie for tightly connected \(3\)-graphs, sharpening their earlier bound by replacing the exponent $
\max_{\substack{\emptyset\ne P\subseteq\partial_2F}}
\frac{e(P)+1}{v(P)-1} $ with \(\beta_F\).
When \(F=K_r^r\), our result recovers the Ramsey lower bound $r(G,K_n^r)\ge 2^{\Omega(n^{2/r})}$ whenever \(G\) is \(2\)-tightly connected and non-\(r\)-partite.