Generalized Erdős-Rogers problems for hypergraphs
Xiaoyu He, Jiaxi Nie · 2025
Read Generalized Erdős-Rogers problems for hypergraphs by Xiaoyu He, Jiaxi Nie (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-03138.txt.
Introduction
Xiaoyu He and Jiaxi Nie generalize Erdős-Rogers problems to hypergraphs. For uniform hypergraphs G and F, they study a quantity that measures guaranteed free subgraphs. It is the largest m such that every n vertex G free hypergraph has an F free induced subgraph on m vertices. Knowing whether that quantity grows polynomially or slowly guides extremal combinatorics.
The value is polynomial in n when G sits inside an iterated blowup of F. As a partial converse, when G is not such a subgraph and is 2 tightly connected, the value is at most polylogarithmic. The bounds extend earlier results by Dudek and Mubayi for complete F and G. The work sharpens the boundary between the two growth regimes.
Catalog record
| CREATOR | Xiaoyu He, Jiaxi Nie |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 25 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-03138
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Generalized Erdős-Rogers problems for hypergraphs Xiaoyu He, Jiaxi Nie Abstract Given r r -uniform hypergraphs G G and F F and an integer n n , let f F , G ( n ) f_{F,G}(n) be the maximum m m such that every n n -vertex G G -free r r -graph has an F F -free induced subgraph on m m vertices. We show that f F , G ( n ) f_{F,G}(n) is polynomial in n n when G G is a subgraph of an iterated blowup of F F . As a partial converse, we show that if G G is not a subgraph of an F F -iterated blowup and is 2 2 -tightly connected, then f F , G ( n ) f_{F,G}(n) is at most polylogarithmic in n n . Our bounds generalize previous results of Dudek and Mubayi for the case when F F and G G are complete. 1 Introduction Given r -uniform hypergraphs (henceforth r -graphs) G and F and an integer n\geq 1 , we let f_{F,G}(n) be the maximum integer m such that every n -vertex G -free r -graph contains an F -free induced subgraph on m vertices. When F=K^{r}_{r} the single edge r -graph, determining f_{K^{r}_{r},G}(n) is equivalent to determining the classical off-diagonal hypergraph Ramsey number, which is one of the central problems in extremal combinatorics. Even for graphs, our knowledge of these numbers so far is quite limited: for K_{3} , Ajtai-Komlós-Szemerédi [ 1 ] and Kim [ 15 ] showed that f_{K_{2},K_{3}}(n)=\Theta(\sqrt{n\log n}) ; for K_{4} , Mattheus and Verstraëte [ 16 ] showed that f_{K_{2},K_{4}}(n)=n^{1/3+o(1)} . We still don’t know the correct exponent of f_{K_{2},G}(n) when G is C_{4} or K_{5} . Erdős and Rogers [ 10 ] , generalizing the off-diagonal Ramsey problem, initiated the study of f_{K_{s},K_{t}}(n) ; these problems have since attracted significant attention and are known as Erdős-Rogers problems. The state of the art on t=s+1 are results of Dudek-Mubayi [ 8 ] and Mubayi-Verstraëte [ 18 ] , establishing the bounds \Omega(\sqrt{n\log n/\log\log n})=f_{K_{s},K_{s+1}}(n)=O(\sqrt{n}\log n). For t=s+2 , Sudakov [ 19 ] and Janzer-Sudakov [ 14 ] showed that n^{\frac{1}{2}-\frac{1}{6s-6}}(\log n)^{\Omega(1)}=f_{K_{s},K_{s+2}}(n)=O(n^{\frac{1}{2}-\frac{1}{8s-10}}(\log n)^{3}). Recently, Mubayi-Verstraëte [ 17 ] and Balogh-Chen-Luo [ 3 ] , followed soon after by Gishboliner, Janzer and Sudakov [ 12 ] , started the systematic study of the function f_{F,G}(n) where F and G are graphs. Their results mostly concern the case when G is a clique, and established bounds for f_{F,K_{r}} when F satisfies certain properties such as clique-free, bipartite, containing a cycle, or having large minimum degree. In this paper, we consider the natural generalization of this line of research to hypergraphs. Note that the previous bounds for f_{F,G}(n) are all polynomial. Our first result shows that this is not a coincidence: we find a sufficient condition for f_{F,G}(n) being polynomial, which is satisfied by all pairs of graphs. Let H and G be r -graphs. For a vertex v of H and a positive integer t , we let H(v,t) be the r -graph obtained by adding t-1 copies of v to H . Further, we let H(v,F) obtained by adding v(F)-1 copies of v to H , which together with v induce a copy of F . Definition 1 . Let G and F be r -graphs. We say G is an F -iterated blowup if (1) G=F ; or (2) G=H(v,F) where H is an F -iterated blowup. Figure 1: The iterated blowup H(v,F) when H=F=K_{3}^{3} . When G=K^{3}_{3} and F is a subgraph of a K^{3}_{3} -iterated blowup, Erdős and Hajnal [ 9 ] showed that f_{K^{3}_{3},F}(n)\geq n^{c} for some constant c (see also [ 6 , 11 ] ). We extend this result, showing that if G is a subgraph of an F -iterated blowup, then f_{F,G}(n) has a polynomial lower bound. Theorem 1.1 (Proof is in Section 2 ) . Let r\geq 2 and let G and F be r -graphs. If G is a subgraph of an F -iterated blowup, then there exists a constant c>0 depending only on F,G such that, for large enough n , f_{F,G}(n)\geq n^{c}. Theorem 1.1 is a straightforward generalization of a supersaturation argument that was known to Erdős (see [ 11 ] ), but we include a proof for completeness. Note that in the case of graphs, starting from any nonempty graph F , one can obtain F -iterated blowups with arbitrarily large clique number. Thus, every graph G is a subgraph of an F -iterated blowup. Hence Theorem 1.1 reproduces the fact that f_{F,G}(n) is polynomial for graphs. More interesting phenomena appear in hypergraphs, as seen in recent work of Conlon-Fox-Gunby-He-Mubayi-Suk-Verstraëte-Yu [ 5 ] , where they prove that if G is tightly connected and not tripartite, then f_{K_{3},G}(n)=O((\log n)^{3/2}). (1) Our second result generalizes ( 1 ) to the Erdős-Rogers setting. We say an r -graph F is k -tightly connected if its edges can be ordered as e_{1},~e_{2}\dots,~e_{t} such that for each 2\leq i\leq t there exists 1\leq j\leq i-1 such that |e_{i}\cap e_{j}|\geq k . In particular, (r-1) -tight connectivity is the usual notion of tightly connectivity. For any set X , we use \binom{X}{k} to denote the family of all subsets of X of size k . The k -shadow of an r -graph H , denoted \partial_{k}H:=\bigcup_{e\in E(H)}\binom{e}{k} , is the k -graph whose edges are k -subsets of edges of H . We use e(H) and v(H) to denote the numbers of edges and vertices in H respectively. Theorem 1.2 (Proof is in Section 3 ) . Let r\geq 3 and let G and F be r -graphs such that G is 2-tightly connected and is not homomorphic to F . Then there exists a constant c depending only on F such that, for large enough n , f_{F,G}(n)\leq c(\log n)^{\alpha_{F}}, where \alpha_{F}=\max_{\emptyset\not=F^{\prime}\subseteq\partial_{2}F}\left\{\frac{e(F^{\prime})+1}{v(F^{\prime})-1}\right\}. It would be very interesting to characterize pairs F and G such that f_{F,G}(n) is polynomial. In [ 5 ] , the following conjecture is proposed. Conjecture 1.3 (Conjecture 1.1, [ 5 ] ) . For a 3-graph G , there exists a constant c=c(G) such that f_{K^{3}_{3},G}(n)\geq n^{c} if and only if G is a subgraph of a K_{3}^{3} -iterated blowup. Extending Conjecture 1.3 , we propose the following. Conjecture 1.4 . For any r -graphs F and G , there exists a constant c=c(F,G) such that f_{F,G}(n)\geq n^{c} if and only if G is a subgraph of an F -iterated blowup. Indeed Theorem 1.2 confirms Conjecture 1.4 when G is 2-tightly connected, since it is easy to check that if G is 2-tightly connected and is not homomorphic to F , then G is not a subgraph of any F -iterated blowup. Note that when F=K^{3}_{3} , Theorem 1.2 only gives f_{K^{3}_{3},G}(n)\leq c(\log n)^{2} , which is worse than ( 1 ). This is because our proof of Theorem 1.2 is essentially different from that of ( 1 ), in that we sacrifice the exponent to handle a more general class of F and G . In particular, when G and F are cliques, say G=K^{r}_{s} and F=K^{r}_{s+1} where s\geq r\geq 3 , Theorem 1.2 implies