Ramsey numbers for 1 1 -degenerate 3 3 -graphs
Peter Allen, Simona Boyadzhiyska, Matías Pavez-Signé · 2025
Read Ramsey numbers for 1 1 -degenerate 3 3 -graphs by Peter Allen, Simona Boyadzhiyska, Matías Pavez-Signé (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-2507-23623.txt.
Introduction
Peter Allen, Simona Boyadzhiyska, and Matías Pavez-Signé settle open cases of a hypergraph conjecture, in a 2025 paper. Ramsey numbers measure how large a structure must be before a pattern is forced under two-coloring. The Burr-Erdős conjecture concerned such numbers for sparse hypergraphs. A few cases for three-part hypergraphs had stayed open. The team builds a sparse example whose Ramsey number is large.
Catalog record
| CREATOR | Peter Allen, Simona Boyadzhiyska, Matías Pavez-Signé |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 13 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-23623
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Ramsey numbers for 1 1 -degenerate 3 3 -graphs Peter Allen, Simona Boyadzhiyska, Matías Pavez-Signé Abstract . We construct a 3 3 -uniform 1 1 -degenerate hypergraph on n n vertices whose 2 2 -colour Ramsey number is Ω ( n 3 / 2 / log n ) \Omega\big(n^{3/2}/\log n\big) . This shows that all remaining open cases of the hypergraph Burr-Erdős conjecture are false. Our graph is a variant of the celebrated hedgehog graph. We additionally show near-sharp upper bounds, proving that all 3 3 -uniform generalised hedgehogs have 2 2 -colour Ramsey number O ( n 3 / 2 ) O\big(n^{3/2}\big) . 1. Introduction Given two r -uniform graphs ( r -graphs) G and H , the (2-colour) Ramsey number of G and H , denoted R(G,H) , is the smallest number n\in\mathbb{N} so that any blue/red-colouring of the edges the complete r -graph on n vertices contains a blue copy of G or a red copy of H . If G=H , then we simply write R(G)=R(G,H) and say that R(G) is the (2-colour) Ramsey number of G . Ramsey numbers for more colours are defined analogously: we seek a monochromatic copy of an r -graph G in a k -edge-coloured complete r -graph and refer to the corresponding parameter as the k -colour Ramsey number . As usual, the degree of a vertex in a hypergraph is the number of edges it is contained in. An r -graph G is said to be D -degenerate if any subhypergraph H of G has a vertex of degree at most D in H . An influential conjecture of Burr and Erdős [ 1 ] from the 70s, proved by Lee [ 6 ] in 2017, is that for any constants D and k there is a constant C such that any n -vertex D -degenerate 2 -graph has k -colour Ramsey number at most Cn . A natural question, the hypergraph Burr-Erdős conjecture , is then whether a similar statement holds for uniformity r\geq 3 . This is false: the first disproof was due to Kostochka and Rödl [ 5 ] who found a 4 -uniform 1 -degenerate counterexample in the 2-colour setting; it follows that the statement also fails for higher uniformities, degeneracies and number of colours. Uniformity three is less understood: Kostochka and Rödl found counterexamples in the 2-colour setting for sufficiently large degeneracy, and Conlon, Fox and Rödl [ 2 ] found a 1 -degenerate counterexample for three colours. Recently, Dubroff, Girão, Hurley and Yap [ 3 ] found a counterexample of degeneracy only eight in the 2-colour case. This leaves open (only) the situation for 3 -uniform hypergraphs with degeneracy at most seven in two colours. Figure 1. A generalised hedgehog with 6 vertices in its body and 9 spikes. In this note we settle the question completely by finding a 1 -degenerate 3-uniform hypergraph with non-linear 2-colour Ramsey number. This counterexample is a variant on the hedgehog , defined by Kostochka and Rödl [ 5 ] . A hedgehog is a 3-uniform hypergraph H defined on vertex set B\sqcup S , where B is referred to as the body of H while S is the set of spikes . The standard hedgehog has |S|=\binom{|B|}{2} and each pair of vertices in the body forms an edge with exactly one spike. In a (generalised) hedgehog , we only require that each spike vertex form an edge with exactly one pair of vertices in the body (see Figure 1 ). The standard hedgehog (and its higher uniformity generalisations) have been well studied and provide most of the constructions mentioned above. In addition, famously, the standard hedgehog is ‘not colour-blind’: Conlon, Fox and Rödl [ 2 ] showed that its k -colour Ramsey number varies from polynomial in the number of vertices when k=2 to exponential when k=4 , providing the first example of the number of colours making such a difference. Fox and Li [ 4 ] subsequently showed that the 2 -colour Ramsey number of the standard hedgehog on n vertices is actually almost linear: it is O(n\log n) . We use generalised hedgehogs to prove that there exist counterexamples with degeneracy one in the 2-colour setting. This is our main contribution. Theorem 1 . There exists a constant c>0 such that, for all sufficiently large n , there exists an n -vertex generalised hedgehog H^{*} with R(H^{*})\geq c\frac{n^{3/2}}{\log n}. We complement the above result with a near-sharp upper bound for the 2 -colour Ramsey numbers of generalised hedgehogs. In fact, the upper bound holds in the more general asymmetric setting. Theorem 2 . There exists a constant C>0 such that, for any sufficiently large n and any n -vertex generalised hedgehogs H,H^{\prime} , we have R(H,H^{\prime})\leq Cn^{3/2}\,. 2. The proof We need the following auxiliary result, which is proved using standard techniques for random graphs. Lemma 3 . For all sufficiently large n\in\mathbb{N} , there exists a graph G on {n^{3/2}}/({10^{6}\log n}) vertices such that (i) each vertex v\in V(G) has degree at most 3n/(2\cdot 10^{3}) ; (ii) G contains no clique on 10 vertices; (iii) G has no independent set of size \sqrt{n}/50 . Proof. Let N={n^{3/2}}/({10^{6}\log n}) and p=800n^{-1/2}\log n . Recall that G(N,p) denotes the N -vertex binomial random graph where possible each edge is included independently with probability p . Let G\sim G(N,p) . A standard application of the Chernoff bound yields that with high probability every vertex of G has degree at most 3pN/2=3n/(2\cdot 10^{6}) . It easily follows from a first moment argument that with high probability G contains no clique of order 10. Finally, another standard first moment argument implies that with high probability G contains no independent set of size 10p^{-1}\log N\leq\sqrt{n}/50 . Hence, there exists an instance satisfying all of (i) , (ii) and (iii) , which we take as our graph G . ∎ Our main contribution is the following construction, proving Theorem 1 . Proof of Theorem 1 . We first define H^{*} as follows. Let the body B of H^{*} have size \sqrt{n}/50 . To every pair in B attach one spike. In addition, to each pair among the first 10 vertices of B , attach a further n/100 spikes. So far the graph contains \tfrac{\sqrt{n}}{50}+\binom{\sqrt{n}/50}{2}+\binom{10}{2}\tfrac{n}{100}\leq\tfrac{n}{2} vertices. Add arbitrarily spikes to reach n vertices. Letting c=10^{-3} and N=c^{2}n^{3/2}/\log n , Lemma 3 gives an N -vertex graph \Gamma on vertex set V such that A1 each vertex in V has degree at most 3cn/2 ; A2 \Gamma contains no clique on 10 vertices; A3 G has no independent set of size \sqrt{n}/50 . We define a complete 2 -coloured 3 -graph G on V as follows. For a triple uvw , if one or more of uv,uw,vw is an edge of \Gamma , we colour uvw red, and, otherwise, we colour it blue. Figure 2. The possible configurations and corresponding coloured edge in the 3-graph G , where a dashed line represents a non-edge in the 2-graph \Gamma . Suppose now that G contains a blue copy of H^{*} , and let B^{\prime} be the image of the body of H^{*} in V . As each pair of B^{\prime}