arxiv: 2605.04105 · v2 · submitted 2026-05-04 · 🧮 math.CO

Recognition: no theorem link

An improved double-exponential lower bound for r₄(5,n)

Chunchao Fan , Qizhong Lin , Bo Ning

Authors on Pith no claims yet

Pith reviewed 2026-05-12 03:08 UTC · model grok-4.3

classification 🧮 math.CO

keywords Ramsey numbershypergraph Ramsey theorylower boundsErdős-Hajnal conjecture4-uniform hypergraphsdouble-exponential boundsgreedy constructions

0 comments

The pith

This paper proves that the Ramsey number r_4(5,n) is at least 2^{2^{Omega(n^{1/5})}}.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper improves the known lower bound on the 4-uniform Ramsey number r_4(5,n). The authors show there exist 4-uniform hypergraphs on 2^{2^{Omega(n^{1/5})}} vertices with neither a complete 5-vertex subgraph nor an independent set of size n. They achieve the improvement by modifying a recent construction and reducing the greedy selection of local maxima from seven layers to five. Readers would care because this narrows the remaining gap in one of the last open cases of the Erdős-Hajnal conjecture, which predicts a stronger bound of 2^{2^{Omega(n)}}.

Core claim

The central claim is that a modified construction using only five layers of greedy local-maxima selection produces 4-uniform hypergraphs without a K_5^{(4)} and with independence number less than n on 2^{2^{Omega(n^{1/5})}} vertices, proving the improved lower bound r_4(5,n) >= 2^{2^{Omega(n^{1/5})}}.

What carries the argument

The five-layer version of the iterated greedy local-maxima selection used to construct the 4-uniform hypergraph that avoids both the forbidden clique and a small independent set.

If this is right

This raises the previous lower bound exponent from n^{1/7} to n^{1/5}.
The reduction to five layers preserves the avoidance of K_5^{(4)} and the small independence number.
The result advances the Erdős-Hajnal conjecture by improving the double-exponential tower lower bound for this specific case.
The method shows that fewer layers in the greedy selection can still deliver the required properties.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If five layers suffice, attempts to drop to four layers might produce a still-better exponent.
The same layer-reduction idea could be tried on the open case r_4(6,n).
The explicit construction may permit direct verification of the properties for moderate values of n.
The approach may connect to other problems in hypergraph extremal theory that use iterated local-maxima selections.

Load-bearing premise

The five-layer version of the modified construction still avoids both a K_5^{(4)} and an independent set of size n at the claimed scale.

What would settle it

An explicit check or calculation showing that the five-layer hypergraph on 2^{2^{c n^{1/5}}} vertices contains either a K_5^{(4)} or an independent set of size n would disprove the claimed lower bound.

read the original abstract

The Ramsey number $r_k(s,n)$ is the smallest integer $N$ such that every $N$-vertex $k$-graph contains either a copy of $K_s^{(k)}$ or an independent set of size $n$. A well-known conjecture of Erd\H{o}s and Hajnal states that for any fixed $4\le k<s$, $r_k(s,n)\ge \operatorname{twr}_{k-1}(\Omega(n)).$ At present, only the last two cases of this conjecture remain open, namely $r_4(5,n)\ge2^{2^{\Omega(n)}}$ and $r_4(6,n)\ge2^{2^{\Omega(n)}}$. Recently, Du, Hu, Liu, and Wang achieved a breakthrough by proving $r_4(5,n)\ge 2^{2^{\Omega(n^{1/7})}}$, which is the first double-exponential lower bound for $r_4(5,n)$. In this note, we improve this to $2^{2^{\Omega(n^{1/5})}}$ by modifying their construction and reducing the greedy selection of local maxima from seven layers to five, thereby making further progress towards the Erd\H{o}s-Hajnal conjecture.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This note trims the Du-Hu-Liu-Wang construction from seven greedy layers to five and thereby lifts the exponent in the double-exponential lower bound for r_4(5,n) from 1/7 to 1/5.

read the letter

The main point is a straightforward modification of the recent seven-layer greedy construction that yields 2^{2^{Omega(n^{1/5})}} instead of 2^{2^{Omega(n^{1/7})}} for the 4-uniform Ramsey number r_4(5,n). The authors adjust the iterative selection of local maxima so that five layers still produce a K_5^{(4)}-free 4-graph whose independence number is O(N^{1/5}). They track the parameters through the layers to show that the clique-avoidance conditions continue to hold while the final independent-set bound improves because fewer layers are needed before the process terminates. This is a clean, incremental advance within the existing program of explicit constructions; it does not introduce new machinery but demonstrates that the earlier depth was not optimal. The calculations appear careful and the exponent gain is real. The soft spot is the verification that the five-layer version does not allow a K_5^{(4)} to form at any intermediate step or inflate the independence number beyond the claimed size. The abstract is short on these checks, so the full proof must confirm that the adjusted greedy thresholds preserve both properties without hidden constant blow-ups. If those steps are solid, the result stands; if a layer fails to block a potential clique, the exponent would drop back. This is specialized reading for people already following hypergraph Ramsey lower bounds and the Erdős-Hajnal conjecture for 4-graphs. A reader who wants the current best explicit double-exponential bound will get value from it. I would send it to peer review; the improvement is modest but clearly stated and worth recording after the details are checked.

Referee Report

1 major / 2 minor

Summary. The paper claims to improve the known lower bound on the 4-uniform Ramsey number r_4(5,n) from 2^{2^{Ω(n^{1/7})}} to 2^{2^{Ω(n^{1/5})}} by modifying the explicit construction of Du-Hu-Liu-Wang. The improvement is obtained by reducing the number of layers in the greedy selection of local maxima from seven to five while asserting that the resulting 4-uniform hypergraph remains K_5^{(4)}-free and has independence number O(N^{1/5}).

Significance. If the modified construction works, the result advances the Erdős-Hajnal conjecture for r_4(5,n) by improving the exponent in the double-exponential lower bound from 1/7 to 1/5. The explicit combinatorial nature of the construction is a strength, as it supplies a concrete hypergraph family rather than a non-constructive existence argument.

major comments (1)

[§3] §3 (five-layer construction): the central claim that reducing the greedy local-maxima selection from seven to five layers preserves K_5^{(4)}-freeness while yielding the n^{1/5} independence-number bound is asserted via adjusted iterative parameters, but the verification that no 5-clique can form across the reduced layers (and that the independence number does not inflate) is only sketched. This step is load-bearing for the improved exponent and requires an explicit check that the new depth suffices to control clique formation at each layer.

minor comments (2)

The comparison with the Du-Hu-Liu-Wang bound could be stated more explicitly in the introduction, including the precise form of the previous exponent.
[§3] Notation for the layer depths and selection thresholds is introduced late; defining the key parameters (e.g., the size of each greedy layer) at the beginning of the construction section would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for recognizing the significance of improving the exponent in the double-exponential lower bound for r_4(5,n). We address the major comment below and will incorporate the requested clarification in the revision.

read point-by-point responses

Referee: [§3] §3 (five-layer construction): the central claim that reducing the greedy local-maxima selection from seven to five layers preserves K_5^{(4)}-freeness while yielding the n^{1/5} independence-number bound is asserted via adjusted iterative parameters, but the verification that no 5-clique can form across the reduced layers (and that the independence number does not inflate) is only sketched. This step is load-bearing for the improved exponent and requires an explicit check that the new depth suffices to control clique formation at each layer.

Authors: We agree that the verification in §3 is currently sketched and would benefit from an explicit, self-contained check. The five-layer parameters are obtained by rescaling the original seven-layer iteration counts and probability bounds of Du-Hu-Liu-Wang so that the same inductive control on clique formation (via the expected number of potential K_5^{(4)}'s at each greedy step) and the O(N^{1/5}) independence-number bound (via the union-bound argument on the final independent set) continue to hold; the reduced depth is still sufficient because the per-layer failure probabilities remain exponentially small in the adjusted exponents. In the revised manuscript we will expand §3 with a detailed, layer-by-layer verification: we will restate the parameter choices, recompute the relevant expectations and union bounds explicitly for the five-layer case, and confirm that no 5-clique can span the layers. This addition will not change the stated theorems or the overall proof strategy. revision: yes

Circularity Check

0 steps flagged

Explicit combinatorial construction with no circular reduction

full rationale

The paper derives the improved lower bound r_4(5,n) >= 2^{2^{Omega(n^{1/5})}} via an explicit modification of the Du-Hu-Liu-Wang hypergraph construction, reducing the greedy local-maxima selection from seven layers to five while preserving K_5^{(4)}-freeness and controlling the independence number through direct combinatorial arguments on the iterative selection process. No parameters are fitted to data, no target quantity is redefined in terms of itself, and the cited prior result serves only as the base construction rather than a load-bearing uniqueness theorem or self-referential ansatz. The exponent improvement follows from the reduced depth in the layer analysis, which is verified independently of the final bound.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the validity of the five-layer modification of the prior construction; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)

standard math Standard combinatorial properties of hypergraph constructions and greedy selection algorithms in Ramsey theory
The argument modifies an existing construction using known avoidance techniques.

pith-pipeline@v0.9.0 · 5525 in / 1430 out tokens · 70488 ms · 2026-05-12T03:08:17.461983+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages · 2 internal anchors

[1]

Ajtai, J

M. Ajtai, J. Koml´ os, and E. Szemer´ edi, A note on Ramsey numbers,J. Combin. Theory Ser. A29 (1980), 354–360

work page 1980
[2]

Bohman, The triangle-free process,Adv

T. Bohman, The triangle-free process,Adv. Math.221 (2009), 1653–1677

work page 2009
[3]

Bohman and P

T. Bohman and P. Keevash, The early evolution of theH-free process,Invent. Math.181 (2010), 291–336

work page 2010
[4]

Campos, S

M. Campos, S. Griffiths, R. Morris, and J. Sahasrabudhe, An exponential improvement for diagonal Ramsey,Ann. of Math.203 (2026), 869–932

work page 2026
[5]

Campos, M

M. Campos, M. Jenssen, M. Michelen, and J. Sahasrabudhe, A new lower bound for the Ramsey numbersR(3, k), arXiv:2505.13371, 2025

work page arXiv 2025
[6]

F. R. K. Chung and R. L. Graham, Erd˝ os on Graphs: His Legacy of Unsolved Problems, A. K. Peters Ltd., Wellesley, MA, 1998

work page 1998
[7]

Conlon, A new upper bound for diagonal Ramsey numbers,Ann

D. Conlon, A new upper bound for diagonal Ramsey numbers,Ann. of Math.170 (2009), 941–960. 7

work page 2009
[8]

Conlon, J

D. Conlon, J. Fox, and B. Sudakov, Hypergraph Ramsey numbers,J. Amer. Math. Soc.23 (2010), 247–266

work page 2010
[9]

Conlon, J

D. Conlon, J. Fox, and B. Sudakov, An improved bound for the stepping-up lemma,Discrete Appl. Math.161 (2013), 1191–1196

work page 2013
[10]

L. Du, X. Hu, R. Liu, and G. Wang, A double-exponential lower bound forr 4(5, n), arXiv:2604.23986, 2026

work page internal anchor Pith review Pith/arXiv arXiv 2026
[11]

L. Du, X. Hu, R. Liu, and G. Wang, A note on generalized Erd˝ os-Rogers problems, arXiv:2604.02835, 2026

work page internal anchor Pith review Pith/arXiv arXiv 2026
[12]

Erd˝ os, Some remarks on the theory of graphs,Bull

P. Erd˝ os, Some remarks on the theory of graphs,Bull. Amer. Math. Soc.53 (1947), 292–294

work page 1947
[13]

Erd˝ os and A

P. Erd˝ os and A. Hajnal, On Ramsey like theorems, problems and results, Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972), 123–140, Inst. Math. Appl., Southhend-on-Sea, 1972

work page 1972
[14]

Erd˝ os, A

P. Erd˝ os, A. Hajnal, and R. Rado, Partition relations for cardinal numbers,Acta Math. Acad. Sci. Hungar.16 (1965), 93–196

work page 1965
[15]

Erd˝ os and H

P. Erd˝ os and H. Hanani, On a limit theorem in combinatorial analysis,Publ. Math. Debrecen 10 (1963), 10–13

work page 1963
[16]

Erd˝ os and R

P. Erd˝ os and R. Rado, Combinatorial theorems on classifications of subsets of a given set, Proc. Lond. Math. Soc.2 (1952), 417–439

work page 1952
[17]

Erd˝ os and G

P. Erd˝ os and G. Szekeres, A combinatorial problem in geometry,Compos. Math.2 (1935), 463–470

work page 1935
[18]

C. Fan, X. Hu, Q. Lin, and X. Lu, New bounds of two hypergraph Ramsey problems, arXiv:2410.22019, 2024

work page arXiv 2024
[19]

Fiz Pontiveros, S

G. Fiz Pontiveros, S. Griffiths, and R. Morris, The triangle-free process and the Ramsey numberR(3, k),Mem. Amer. Math. Soc.263 (2020), 125pp

work page 2020
[20]

R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey theory, 2nd edn (Wiley, New York, 1990)

work page 1990
[21]

Gupta, N

P. Gupta, N. Ndiaye, S. Norin, and L. Wei, Optimizing the CGMS upper bound on Ramsey numbers, arXiv:2407.19026, 2024

work page arXiv 2024
[22]

Hefty, P

Z. Hefty, P. Horn, D. King, and F. Pfender, ImprovingR(3, k) in just two bites, arXiv:2510.19718, 2025

work page arXiv 2025
[23]

X. Hu, Q. Lin, X. Lu, and G. Wang, Phase transitions of the Erd˝ os-Gy´ arf´ as function, arXiv:2504.05647, 2025

work page arXiv 2025
[24]

Hunter, A

Z. Hunter, A. Milojevi´ c, and B. Sudakov, Gaussian random graphs and Ramsey numbers, arXiv:2512.17718, 2025

work page arXiv 2025
[25]

J. H. Kim, The Ramsey numberR(3, t) has order of magnitudet 2/logt,Random Structures Algorithms7 (1995), 173–207. 8

work page 1995
[26]

Y. Li, C. C. Rousseau, and W. Zang, Asymptotic upper bounds for Ramsey functions, Graphs Combin.17 (2001), 123–128

work page 2001
[27]

J. Ma, W. Shen, and S. Xie, An exponential improvement for Ramsey lower bounds,Invent. Math., to appear

work page
[28]

Mattheus and J

S. Mattheus and J. Verstra¨ ete, The asymptotics ofr(4, t),Ann. of Math.199 (2024), 919– 941

work page 2024
[29]

Mubayi and A

D. Mubayi and A. Suk, Off-diagonal hypergraph Ramsey numbers,J. Combin. Theory Ser. B.125 (2017), 168–177

work page 2017
[30]

Mubayi and A

D. Mubayi and A. Suk, Constructions in Ramsey theory,J. Lond. Math. Soc.97 (2018), 247–257

work page 2018
[31]

Mubayi and A

D. Mubayi and A. Suk, New lower bounds for hypergraph Ramsey numbers,Bull. Lond. Math. Soc.50 (2018), 189–201

work page 2018
[32]

Sah, Diagonal Ramsey via effective quasirandomness,Duke Math

A. Sah, Diagonal Ramsey via effective quasirandomness,Duke Math. J.172 (2023), 545– 567

work page 2023
[33]

Sahasrabudhe, Revisiting the Ma–Shen–Xie bound, unpublished manuscript

J. Sahasrabudhe, Revisiting the Ma–Shen–Xie bound, unpublished manuscript

work page
[34]

J. B. Shearer, A note on the independence number of triangle-free graphs,Discrete Math. 46 (1983), 83–87

work page 1983
[35]

Spencer, Ramsey’s theorem-a new lower bound,J

J. Spencer, Ramsey’s theorem-a new lower bound,J. Combin. Theory Ser. A18 (1975), 108–115

work page 1975
[36]

Thomason, An upper bound for some Ramsey numbers,J

A. Thomason, An upper bound for some Ramsey numbers,J. Graph Theory12 (1988), 509–517. 9

work page 1988