K 4 − K_{4}^{-} -free triple systems without large stars in the complement

Dhruv Mubayi, Nicholas Spanier · 2025

Read K 4 − K_{4}^{-} -free triple systems without large stars in the complement by Dhruv Mubayi, Nicholas Spanier (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-06076.txt.

Introduction

Dhruv Mubayi and Nicholas Spanier pin down a Ramsey number for triple systems, confirming a conjecture posed by six researchers. Ramsey numbers measure how large a structure must be before a chosen pattern or its complement's pattern becomes unavoidable. Here the pattern is a small four-vertex triple system with three edges, and the complement pattern is a star: many triples sharing one common vertex.

The team proves the Ramsey number grows like the square of the star's size divided by its logarithm. The result generalizes a famous bound for the graph Ramsey number of a triangle against a star. That link is structural: fixing one vertex in a triple system avoiding the small pattern leaves a triangle-free graph. The proof adapts a pseudorandom refinement of the classic graph argument, following a route opened by Guo and Warnke.

Catalog record

CREATORDhruv Mubayi, Nicholas Spanier
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE88 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-06076

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

K 4 − K_{4}^{-} -free triple systems without large stars in the complement Dhruv Mubayi, Nicholas Spanier Abstract The n n -star S n S_{n} is the n n -vertex triple system with ( n − 1 2 ) {n-1\choose 2} edges all of which contain a fixed vertex, and K 4 − K_{4}^{-} is the unique triple system with four vertices and three edges. We prove that the Ramsey number r ⁡ ( K 4 − , S n ) r(K_{4}^{-},S_{n}) has order of magnitude n 2 / log ⁡ n n^{2}/\log n . This confirms a conjecture of Conlon, Fox, He, Suk, Verstraëte and the first author. It also generalizes the well-known bound of Kim for the graph Ramsey number r ⁡ ( 3 , n ) r(3,n) , as the link of any vertex in a K 4 − K_{4}^{-} -free triple system is a triangle-free graph. Our method builds on the approach of Guo and Warnke who adapted Kim’s lower bound for r ⁡ ( 3 , n ) r(3,n) to the pseudorandom setting. 1 Introduction A k -uniform hypergraph H (henceforth k -graph) is a pair (V(H),E(H)) where E(H) is a collection of k -element subsets of V(H) . We often associate H with its edge set E(H) , when V(H) is obvious from context. Write K_{n}^{k} for the complete k -graph on n vertices. Given k -graphs G and H , the Ramsey number r(G,H) is the minimum N such that every red/blue coloring of E(K_{N}^{k}) has a monochromatic red copy of G or a monochromatic blue copy of H ; when H=K_{n}^{k} , we simply write r(G,n) . When G is fixed and n\rightarrow\infty , we often refer to this class of parameters as off-diagonal Ramsey numbers. The off-diagonal graph Ramsey numbers r(s,n)=r(K_{s},K_{n}) have been intensively studied for many decades. Erdős conjectured that for fixed s\geq 3 , we have r(s,n)=n^{s-1+o(1)} and this was reiterated recently by the first author and Verstraëte [ 12 ] . Only the first two cases, s=3,4 have been proved. The order of magnitude of r(3,n) is n^{2}/\log n , where the upper bound was obtained by Ajtai-Komlós-Szemerédi [ 1 ] and the lower bound was proved by Kim [ 7 ] and later by Bohman [ 3 ] using a different method. More recently, Mattheus and Verstraëte proved that r(4,n)=n^{3-o(1)} with the order of magnitude still undetermined. In this paper we consider an analogous parameter to r(3,n) in the hypergraph setting. It is well-known that for each s\geq 4 , the hypergraph Ramsey number r(K_{4}^{3},K_{n}^{3})>2^{cn} for some positive constant c . On the other hand, there is a well-known large class \mathcal{C} of 3-graphs G for which it is known that r(G,n) is polynomial in n . Recently, it was conjectured [ 4 ] that r(G,n) is at most polynomial in n if and only if G\in\mathcal{C} . On the other hand, it is not clear whether G\not\in\mathcal{C} implies that r(G,n) is exponential in n . In fact, the following result from [ 5 ] showed an intermediate growth rate for the following related problem. The link graph of a vertex v in a 3-graph H is the graph whose vertex set is V(H)\setminus\{v\} and edge set is \{yz:vyz\in E(H)\} . Write S_{n} for the n -vertex star: this is the 3-graph with vertex set [n]:=\{1,\ldots,n\} and edge set \{e\in{[n]\choose 3}:1\in e\} . Alternatively, S_{n} is the 3-graph for which there is a vertex whose link graph is isomorphic to K_{n-1} . The 3-graph S_{n} is a natural way to generalize K_{n} to hypergraphs. It is proved in [ 5 ] that there are positive constants c,c^{\prime} such that 2^{c\log^{2}n}<r(K_{4}^{3},S_{n})<2^{c^{\prime}n^{2/3}\log n}. (1) This shows that r(K_{4}^{3},S_{n}) is already superpolynomial in n . Therefore, one needs to consider sparser 3-graphs G to detect polynomial growth rates for r(G,S_{n}) . The smallest such nontrivial 3-graph G is K_{4}^{-} , the unique 3-graph with four vertices and three edges (if G is the 3-graph on four vertices and two edges, then it is trivial to see that r(G,S_{n})=\Theta(n) ). The link graph L of a vertex in an N -vertex K_{4}^{-} -free 3-graph H is a triangle-free graph on N-1 vertices, and hence by the result r(3,n)=O(n^{2}/\log n) of [ 1 ] , the independence number of L is at least \Omega(\sqrt{N\log N}) . Consequently, the complement of every K_{4}^{-} -free 3-graph on N vertices contains an n -vertex star with n=\Omega(\sqrt{N\log N}) . This shows r(K_{4}^{-},S_{n})=O\left(\frac{n^{2}}{\log n}\right). In the other direction, it was proved in [ 5 ] using the local lemma that r(K_{4}^{-},S_{n})=\Omega(n^{2}/\log^{2}n) . This led the authors of [ 5 ] to conjecture that r(K_{4}^{-},S_{n})=\Theta\left(\frac{n^{2}}{\log n}\right). (2) A similar state of affairs existed for the graph case r(3,n) prior to Kim’s improved lower bound. Note, however, that ( 2 ) is substantially stronger than Kim’s result r(3,n)=\Omega(n^{2}/\log n) as it posits the existence of a triple system such that every link graph is an optimal (in order of magnitude) r(3,n) graph. Also, as indicated in ( 1 ), hypergraph problems sometimes display novel phenomena compared to what we typically witness for graphs, so it was by no means a forgone conclusion that ( 2 ) should hold similar to the graph result r(3,n)=\Theta(n^{2}/\log n) . In this paper, we prove ( 2 ). Theorem 1 . There is an absolute constant c such that for all sufficiently large N , there is a K_{4}^{-} -free 3-graph on N vertices whose complement contains no copy of S_{n} , where n=c\sqrt{N\log N} . In other words, r(K_{4}^{-},S_{n})=\Omega(n^{2}/\log n) . Our theorem follows from the following stronger result, which guarantees not only that for every vertex x and every n -set A omitting x , there is an edge of the form xyz , where yz\in{A\choose 2} , but in fact that there are many such edges. It is more convenient to consider the bipartite setting as follows. Given a 3 -graph H , disjoint sets A,B\subseteq V(H) , and x\in V(H)\setminus(A\cup B) , let e_{H,x}(A,B) be the number of edges in H of the form xab where a\in A and b\in B . The following theorem is our main result. Theorem 2 ( Main result). There exists \beta_{0},D_{0} such that for all \delta\in(0,1],\beta\in(0,\beta_{0}) , C>\frac{D_{0}}{\delta^{2}\sqrt{\beta}} and N>N_{0}(\delta,\beta,C) , there exists a K_{4}^{-} free 3 -graph H on N vertices such that for every two disjoint n -vertex subsets A,B with n:=C\sqrt{N\log N} and for every vertex x\not\in A\cup B , e_{H,x}(A,B)=(1\pm\delta)\rho n^{2} where \rho:=\sqrt{\frac{\beta\log N}{3N}} . There are two general approaches to obtain graphs or hypergraphs that have good Ramsey properties of the type sought in Theorems 1 and 2 : the nibble method pioneered by Ajtai-Komlós-Szemerédi [ 1 , 2 ] and Rödl [ 13 ] , and the differential equations method developed by Wormald [ 16 ] for combinatorial settings. We prove Theorem 2 using the nibble method. This was the approach used by Kim [ 7 ] in his proof of r(3,n)=\Omega(n^{2}/\log n) . More recently, Guo and Warnke [ 6 ] established a stronger result than r(3,n)=\Omega(n^{2}/\log n) in two ways. First, they not only found one triangle-free graph on N vertices with independence number

Read the complete text