Pith. sign in

REVIEW 2 major objections 6 minor 21 references

Off-Diagonal Ramsey Numbers for Linear Hypergraphs

T0 review · 2 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For every uniformity k≥3, some linear k-graph makes r(H,K_n^{(k)}) a tower of height k−2.

desk verdict New lower bounds for off-diagonal Ramsey numbers of linear hypergraphs in uniformity k≥4, built on a shared-author preprint for the k=3 base; the new stepping-up framework is the real contribution. read the letter →

arxiv 2507.05641 v2 pith:LAA75EDP submitted 2025-07-08 math.CO

Xiaoyu He , Jiaxi Nie , Yuval Wigderson , Hung-Hsun Hans Yu This is my paper · ORCID
classification math.CO MSC 05D1005C6505D05
keywords off-diagonalRamseynumberslinearhypergraphshypergraphstepping-upconstructiontowerfunctionbinarystructuresindependencenumbertower-heightseparation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper proves that off-diagonal Ramsey numbers $r(H,K_n^{(k)})$ for fixed linear $k$-uniform hypergraphs can be enormous: for every $k\ge 3$ and every constant $C>1$, there exists a linear $k$-graph $H$ with $r(H,K_n^{(k)})\ge \mathrm{twr}_{k-2}(2^{(\log n)^C})$. The height-$k-2$ tower is nearly the largest allowed by the classical stepping-down upper bound $r(H,K_n^{(k)})\le \mathrm{twr}_{k-1}(n^{O_H(1)})$, so linear hypergraphs are not as tame as the old folklore conjecture suggested. The proof is an induction on uniformity: a stepping-up construction takes a linear $(k-1)$-graph with large off-diagonal Ramsey number and produces a linear $k$-graph whose Ramsey number is exponential in it, with the recent $k=3$ result as the base case. If correct, the same $H$ has polynomial $r(H,K_{n,\ldots,n}^{(k)})$, separating the clique and complete-$k$-partite targets dramatically.

What carries the argument

The argument runs through a reformulation of the classical stepping-up construction. Vertices are integers; the top splitting level $\ell(S)$ and left/right subsets of a set $S$ organize any $k$-set into a binary structure $b(S)$, whose internal-node levels supply the $\delta$-sequence that determines whether the $k$-set is an edge. The new machinery defines left/right stepping-ups of a $(k-1)$-graph $G$ using increasing/decreasing binary structures, plus edge families of prescribed binary-structure type $T$, and an auxiliary independence bound $f(n_1,n_2,\mathcal T)$ bounding how large a set can be without unwanted structures. Lemma 2.9 gives a linear bound on $f$ when $\mathcal T$ contains two-leaf types $T_{a,b}$, and Lemma 2.10 gives a polynomial bound by depth. The hard part, Theorem 3.1, constructs the target linear $k$-graph $H'$ from an ordered expansion $H^+$ of $H$ via a randomized oriented $s$-graph (Lemma 3.3): any dyadic partition, two-coloring, and ordering contains a monochromatic order-respecting transversal copy of $H^+$, and this copy is used to embed $H$ into $G$, forcing the stepped-up graph to be $H'$-free.

What would settle it

Compute r(H,$K_n^{{(3)}}$) for the specific linear 3-graphs produced by [4, Theorem 1.4]: if for some C>1 and some such H the value is bounded by a polynomial in n for infinitely many n, the base case (and hence Theorem 1.2 for all k≥4) is false. Alternatively, rerun the code in Proposition 4.1 to verify the claimed partition obstruction showing that the seven-vertex projective-plane 3-graph is absent from the recursive construction, which grounds the explicit exponential example.

Watch

Extended reading notes

Core claim

The central claim, Theorem 1.2, is that for every constant $C>1$ and every uniformity $k\ge 3$ there is a linear $k$-uniform hypergraph $H$ for which $r(H,K_n^{(k)})\ge \mathrm{twr}_{k-2}(2^{(\log n)^C})$ for all sufficiently large $n$. The authors establish this by proving Proposition 1.3, a stepping-up lemma: given a linear $(k-1)$-graph $H$, they construct a linear $k$-graph $H'$ with $r(H',K_{2n+2k}^{(k)})>2^{r(H,K_n^{(k-1)})-1}$, so one exponential step lifts the bound from uniformity $k-1$ to $k$. Starting from the $k=3$ theorem of the recent preprint [4], the induction gives tower height $k-2$. The construction avoids the polynomial upper bound for iterated $k$-partite hypergraphs, and it implies that $r(H,K_n^{(k)})$ and $r(H,K_{n,\ldots,n}^{(k)})$ can be respectively tower-height and polynomial for the same linear $H$.

Load-bearing premise

The tower-height result for k≥4 rests entirely on the k=3 base case from the recent preprint [4]; if that base case is wrong, the induction has no starting point.

Editorial extensions

If this is right

  • For every $k\ge 3$ there is a linear $k$-graph $H$ whose off-diagonal Ramsey number $r(H,K_n^{(k)})$ grows like a tower of height $k-2$, nearly matching the classical upper bound (1.1) of height $k-1$.
  • The same $H$ satisfies $r(H,K_{n,\ldots,n}^{(k)})\le n^{O_H(1)}$, so the Ramsey number against a single clique can be dramatically larger than against the complete $k$-partite hypergraph.
  • The folklore conjecture that every linear $3$-graph has polynomial $r(H,K_n^{(3)})$ is false, and this paper extends that failure to all uniformities.
  • An improved base case with $r(H,K_n^{(3)})\ge 2^{n^c}$ would, by the same induction, give a linear $k$-graph with $r(H,K_n^{(k)})\ge \mathrm{twr}_{k-1}(n^c)$, matching the upper bound up to constants.
  • The fully explicit linear $4$-graph given by the lines of PG(2,3) yields an exponential lower bound and can seed an explicit tower construction of height $k-2$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • One could try to push the base case: replacing the $k=3$ construction's $2^{(\log n)^C}$ with $2^{n^c}$ is the bottleneck; the induction in Proposition 1.3 is a clean exponential amplifier that would then yield height $k-1$ towers.
  • The dyadic-partition machinery is robust enough that Lemma 3.3 should hold for linear $s$-graphs of any fixed Berge girth, so the same stepping-up might produce linear $k$-graphs with large girth and tower Ramsey numbers; the paper notes the girth version in passing.
  • The separation between $r(H,K_n^{(k)})$ and $r(H,K_{n,\ldots,n}^{(k)})$ suggests that the iterated-$k$-partite conjecture of [5] cannot be rescued by any linearity assumption; linearity alone does not force polynomial growth.
  • A concrete open target is the seven-vertex projective-plane $3$-graph: if one could prove super-polynomial $r(H,K_n^{(3)})$ for it, it would be the smallest linear hypergraph witnessing the failure of polynomial growth, and the present methods do not yet reach it.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. The paper studies off-diagonal Ramsey numbers r(H, K_n^{(k)}) for linear k-uniform hypergraphs H. The main theorem (Theorem 1.2) asserts that for every C>1 and every k≥3, there exists a linear k-graph H with r(H, K_n^{(k)}) ≥ twr_{k-2}(2^{(\log n)^C}) for all sufficiently large n, nearly matching the Erdős–Rado upper bound. The proof introduces a binary-tree reformulation of the stepping-up construction (Section 2), defines a linear hypergraph with a strong transversal property (Lemma 3.3), and proves an induction step (Proposition 1.3) that turns a lower bound for a linear (k−1)-graph into an exponential lower bound for a linear k-graph. The induction is based on the k=3 case imported from Conlon et al. [4, Theorem 1.4]. The paper also notes a separation between r(H, K_n^{(k)}) and r(H, K_{n,\ldots,n}^{(k)}), and discusses explicit examples such as the Fano plane and its 4-uniform analogue.

Significance. If the results hold, this is a significant advance: it extends the recent k=3 breakthrough of Conlon et al. to all uniformities, showing that linearity of H does not force polynomial growth in r(H, K_n^{(k)}), and it gives a tower-type separation from the complete k-partite target. The paper's own contribution—the binary-tree stepping-up framework, the dynamic-programming bounds on the auxiliary function f, and the randomized construction of a linear hypergraph with the transversal property (Lemma 3.7)—is carefully developed and appears internally consistent. The proofs of the main construction are detailed and, apart from the issues below, reproducible, including a union bound and FKG argument in Lemma 3.7. However, the tower-height statement for all k≥4 is conditional on the correctness of the k=3 base case from the unpublished shared-author preprint [4], which is not proved in this manuscript.

major comments (2)
  1. [Section 1, Theorem 1.2 and the proof of Proposition 1.3] The proof of Theorem 1.2 for k≥4 rests entirely on Theorem 1.1, which is imported from [4, Theorem 1.4]. This is an unpublished preprint sharing an author with the present paper, and its correctness is not established within this manuscript. If [4, Theorem 1.4] has an error or an unverified hypothesis, the claimed tower-height result for every k≥4 collapses. The authors should either include a self-contained proof of the k=3 base case, or explicitly state Theorem 1.2 as conditional on the correctness of [4] (and, if appropriate, cite a published version once it appears). As written, the abstract and introduction present the result unconditionally, which is not justified by the evidence in this paper.
  2. [Section 3, Theorem 3.1 and Proposition 1.3] Theorem 3.1 requires the input (k−1)-graph H to have no isolated vertices, but Proposition 1.3 is stated for an arbitrary linear (k−1)-graph H. The proof of Proposition 1.3 applies Theorem 3.1 directly without explaining how to handle isolated vertices. This is fixable by deleting isolated vertices (which does not change r(H, K_n^{(k-1)}) up to the stated bound), but the reduction is not stated. Please add this argument or adjust the hypotheses of Proposition 1.3 so that the proof is complete.
minor comments (6)
  1. [Abstract] The abstract says "for any constant C>0" but Theorem 1.2 requires C>1. Please align the statement.
  2. [Section 2, Definitions 2.5 and 2.6] The vertex set of the stepping-up is written as "{0, . . . , 2N − 1}", which appears to conflict with the earlier description of vertices as binary strings of length N (which would give 2^N vertices). If the intended set is {0, . . . , 2^N − 1}, the typesetting should be corrected; if the intended size is 2N, the construction does not match the classical stepping-up and the proof of Proposition 1.3 would need rechecking.
  3. [Section 2, proof of Lemma 2.9] The sentence "We will proof by induction" should read "We will prove by induction".
  4. [Section 3.2, proof of Lemma 3.7] In the definition of the random s-graph, the text says "on k vertices" but it should be "on n vertices".
  5. [Section 3.2, proof of Lemma 3.7] When applying Lemma 3.6 to a set I of size m < s−1, the paper does not explicitly note that I can be extended to a set of size s−1. Please add this clarification, as Lemma 3.6 is stated only for |I| = s−1.
  6. [Section 4, Proposition 4.1] The SageMath code included in the proof is nonstandard for a journal article; if kept, it should be moved to a footnote or appendix, and the text should summarize the output more explicitly (the code prints only the empty set and the whole ground set).

Circularity Check

1 steps flagged · score 4.0 of 10

Tower-height result for k≥4 rests on a same-author preprint for the k=3 base case; the induction step itself is self-contained.

  1. self citation load bearing [Section 1, Theorem 1.1 and the paragraph after Proposition 1.3]
    "Theorem 1.1 ([4, Theorem 1.4]). For every C > 1, there exists a linear 3-graph H such that r(H, K_n^{(3)}) ≥ 2^{(log n)^C} for all sufficiently large n. ... Note that Proposition 1.3 immediately implies Theorem 1.2 by induction on k, with Theorem 1.1 serving as the base case."

    The proof of Theorem 1.2 for all k ≥ 3 is an induction whose base case k = 3 is imported verbatim from [4, Theorem 1.4]. The present paper contains no proof of this base case, and [4] is an unpublished preprint sharing coauthor X. He with the present paper. For k = 3, Theorem 1.2 is exactly the cited theorem, so that instance is not newly derived here. For k ≥ 4, the entire tower-height conclusion reduces to the unverified-in-this-paper same-author base plus an internally proved induction step (Proposition 1.3). Thus the k ≥ 4 result is load-bearing on a self-citation, even though the stepping-up construction and the transversal-copy lemma are derived independently within the paper.

full rationale

The paper's original contribution is the linear hypergraph stepping-up machinery: Proposition 1.3, Theorem 3.1, and Lemma 3.3 are proved from scratch using probabilistic and tree-structure arguments, with no fitting of parameters and no prediction that is forced by construction. The only circularity is the base case of the induction proving Theorem 1.2. That base is Theorem 1.1 of Conlon et al. [4], a same-author preprint; the paper gives no proof of it, and the k = 3 case of the main theorem is literally that cited statement. Because [4] is not machine-checked, code-reproduced here, or otherwise independently verified within the manuscript, it does not qualify as non-circular independent support under the review criteria. This is a real, load-bearing self-citation, but it is confined to the starting point: the induction step itself is self-contained and does not assume the target result. The isolated-vertex hypothesis gap between Proposition 1.3 (arbitrary linear H) and Theorem 3.1 (H with no isolated vertices) is a correctness/intent issue, not a circularity, since deleting isolated vertices does not alter the Ramsey number and the paper's intended argument is clear. Overall, the central claim still has independent content for k ≥ 4 conditional on the cited base, so the circularity score is 4 rather than higher.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on the external base case Theorem 1.1 from [4] (overlapping authorship), on the classical Erdős-Hajnal-Rado stepping-up framework reformulated in Section 2, and on standard probabilistic tools used in Lemma 3.7. There are no free parameters fitted to data; C is quantified universally and c, n are existential proof constants. The new definitions (binary structures, types, dyadic partitions, ordered expansions) are mathematical content, not unverified postulates. One unflagged technical assumption: Theorem 3.1 requires H with no isolated vertices while Proposition 1.3 is stated for all linear H; this is fixable by deleting isolated vertices and should be stated.

assumptions (4)
  • domain assumption Theorem 1.1 of Conlon et al. [4] (k=3 base case)
    Used as the starting point of the induction proving Theorem 1.2; the paper does not prove the k=3 case and shares an author with [4].
  • standard math Erdős-Hajnal-Rado stepping-up construction and the Erdős-Rado upper bound (1.1)
    The stepping-up framework in Section 2 is a reformulation of the classical construction; the upper bound is cited to justify near-optimality.
  • standard math Probabilistic method, union bound, and FKG/Harris inequality in Lemma 3.7
    Used to show existence of a linear oriented s-graph with the ordered monochromatic transversal property; these tools are standard.
  • ad hoc to paper The hypergraph H in Proposition 1.3 has no isolated vertices (as required by Theorem 3.1)
    Theorem 3.1, the engine of Proposition 1.3, explicitly requires H with no isolated vertices; Proposition 1.3 omits this condition, creating a minor fixable gap.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Off-Diagonal Ramsey Numbers for Linear Hypergraphs." pith.science (2026). https://pith.science/paper/LAA75EDP

@misc{pith2026250705641,
  author       = {Pith},
  title        = {Pith review of: Off-Diagonal Ramsey Numbers for Linear Hypergraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LAA75EDP}},
  note         = {Machine review of arXiv:2507.05641}
}
abstract

We study off-diagonal Ramsey numbers $r(H, K_n^{(k)})$ of $k$-uniform hypergraphs, where $H$ is a fixed linear $k$-uniform hypergraph and $K_n^{(k)}$ is complete on $n$ vertices. Recently, Conlon et al.\ disproved the folklore conjecture that $r(H, K_n^{(3)})$ always grows polynomially in $n$. In this paper we show that much larger growth rates are possible in higher uniformity. In uniformity $k\ge 4$, we prove that for any constant $C>0$, there exists a linear $k$-uniform hypergraph $H$ for which $$r(H,K_n^{(k)}) \geq \textup{twr}_{k-2}(2^{(\log n)^C}).$$

Figures

Figures reproduced from arXiv: 2507.05641 by the authors.

Figure 1
Figure 1. Binary structure of S = {5, 6, 7, 8, 9} As mentioned earlier, the case where δ1, . . . , δk−1 is monotone is usually special. Rephrasing this in terms of binary structures gives the following definition. Definition 2.3. The binary structure b(S) is increasing if all right subtrees of internal nodes are singletons, and it is decreasing if all left subtrees of internal nodes are singletons. The binary structure is mon… view at source ↗
Figure 2
Figure 2. Binary structure of S = {1, 2, 4, 8, 16} Finally, instead of classifying k-tuples using the relative order of δ1, . . . , δk−1, we classify them based on types of their structures. Definition 2.4. A type of binary structure T is a weighted rooted ordered binary tree such that each leaf vertex has a positive integer weight, and each internal vertex has weight equal to the sum of the weights of its children. Its size … view at source ↗
Figure 3
Figure 3. Type T2,2 Our variant of stepping-up will also include two such conditions, which we now define in turn. We begin with the monotone edges. For our convenience later, we will actually “flip G” when we step up for the decreasing edges. Definition 2.5. Let G be a (k − 1)-graph on {0, 1, . . . , N − 1}. Its left stepping-up is the k￾graph on {0, . . . , 2 N − 1} consisting of all edges e with b(e) increasing and L(e) ∈ … view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Type T1,(2,1) and Type T(1,2),1 The following statement then follows easily from the definition. Lemma 2.8. Let G1, G2 be two (k − 1)-graphs on {0, 1, . . . , N − 1}, and let T be a family of types of binary structure of size k. Let G be the stepping up of (G1, G2, T )…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 16 canonical work pages

  1. [4]

    On off-diagonal hypergraph Ramsey numbers

    D. Conlon, J. Fox, B. Gunby, X. He, D. Mubayi, A. Suk, and J. Verstraëte, On off-diagonal hypergraph Ramsey numbers, 2024. Preprint available at arXiv:2404.02021

    work page Pith review arXiv 2024

  2. [1]

    Ajtai, J

    M. Ajtai, J. Komlós, and E. Szemerédi, A note on Ramsey numbers,J. Combin. Theory Ser. A 29 (1980), 354–360

    work page 1980

  3. [2]

    Bohman and P

    T. Bohman and P. Keevash, Dynamic concentration of the triangle-free process,Random Structures Algorithms58 (2021), 221–293

    work page 2021

  4. [3]

    Campos, M

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

    arXiv 2025

  5. [5]

    Conlon, J

    D. Conlon, J. Fox, B. Gunby, X. He, D. Mubayi, A. Suk, J. Verstraëte, and H.-H. H. Yu, When are off-diagonal hypergraph Ramsey numbers polynomial?, 2024. Preprint available at arXiv:2411.13812

    arXiv 2024

  6. [6]

    Conlon, J

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

    2010

  7. [7]

    Conlon, J

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

    2013

  8. [8]

    Erdős, Graph theory and probability

    P. Erdős, Graph theory and probability. II,Canadian J. Math.13 (1961), 346–352

    work page 1961

Show all 21 references
  1. [9]

    Erdős and A

    P. Erdős and A. Hajnal, On Ramsey like theorems. Problems and results, inCombinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972), Inst. Math. Appl., Southend-on-Sea, 1972, 123–140

    1972

  2. [10]

    Erdős, A

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

    1965

  3. [11]

    Erdős and R

    P. Erdős and R. Rado, Combinatorial theorems on classifications of subsets of a given set,Proc. London Math. Soc. (3)2 (1952), 417–439

    1952

  4. [12]

    Erdös and G

    P. Erdös and G. Szekeres, A combinatorial problem in geometry,Compositio Math.2 (1935), 463–470

    1935

  5. [13]

    Fiz Pontiveros, S

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

    2020

  6. [14]

    Fox and X

    J. Fox and X. He, Independent sets in hypergraphs with a forbidden link,Proc. Lond. Math. Soc. (3)123 (2021), 384–409

    2021

  7. [15]

    J. H. Kim, The Ramsey numberR(3, t) has order of magnitudet2/ log t, Random Structures Algorithms 7 (1995), 173–207

    1995

  8. [16]

    Mattheus and J

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

    2024

  9. [17]

    Mubayi and A

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

    2017

  10. [18]

    Mubayi and A

    D. Mubayi and A. Suk, New lower bounds for hypergraph Ramsey numbers,Bull. Lond. Math. Soc.50 (2018), 189–201. OFF-DIAGONAL RAMSEY NUMBERS FOR LINEAR HYPERGRAPHS 15

    2018

  11. [19]

    Reiher and V

    C. Reiher and V. Rödl, The girth Ramsey theorem, 2023. Preprint available at arXiv:2308.15589

    2023 arXiv

  12. [20]

    Reiher, V

    C. Reiher, V. Rödl, and M. Schacht, Unavoidable subgraphs in Ramsey graphs, 2025. Preprint available at arXiv:2502.09830

    2025 arXiv

  13. [21]

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

    1983

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.