Pith. sign in

REVIEW 2 major objections 4 minor 37 references

A note on pseudorandom Ramsey graphs

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read Optimal clique-free pseudorandom graphs would pin the Ramsey exponent to $t^{s-1+o(1)}$; a related counting argument improves the lower bounds for cycle Ramsey numbers.

desk verdict A clean conditional theorem and a real C5 exponent improvement are undercut by an overreaching C7 claim that relies on sparse Ree–Tits octagons. read the letter →

arxiv 1909.01461 v2 pith:IVHCRMZK submitted 2019-09-03 math.CO cs.DM

Dhruv Mubayi , Jacques Verstraete This is my paper · ORCID
classification math.COcs.DM MSC 05D1005C5505B25
keywords Ramseynumberspseudorandomgraphs(ndλ)-graphsindependentsetsoddcyclesrandomgraphprocessgeneralizedhexagonsexponents
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 note proves that pseudorandom graphs are sufficient to determine the asymptotic exponents of classical Ramsey numbers. If $K_s$-free $(n,d,\lambda)$-graphs with near-optimal degree $d=\Omega(n^{1-1/(2s-3)})$ and $\lambda=O(\sqrt{d})$ exist, then $r(s,t)=t^{s-1+o(1)}$, matching the known upper bound up to subpolynomial factors. Unconditionally, it gives new lower bounds for cycle-complete Ramsey numbers: $r(C_5,t)\ge (1+o(1))t^{11/8}$ and $r(C_7,t)\ge (1+o(1))t^{11/9}$, improving the exponent over the bounds from the random $C_\ell$-free process. It also improves $r(C_\ell,t)$ by polylogarithmic factors for all odd $\ell\ge 5$ and for $\ell\in\{6,10\}$. The engine is a short counting lemma for independent sets in pseudorandom graphs, plus a random block construction over high-girth incidence graphs.

What carries the argument

The central object is the family of $(n,d,\lambda)$-graphs: $d$-regular graphs on $n$ vertices whose nontrivial adjacency eigenvalues are at most $\lambda$ in absolute value. The load-bearing tool is a counting lemma stating that, for $t\ge 2n\log^2 n/d$, the number of independent $t$-sets in such a graph is at most $(2e^2\lambda/\log_2 n)^t$. A random-sampling step then keeps each vertex with probability about $\log^2 n/(2e^2\lambda)$ and deletes one vertex from every independent $t$-set, producing an $F$-free graph with no independent set of size $t$ and order roughly $n/(\lambda\log n)$. For the cycle results, the machinery is a random block construction: take a high-girth bipartite graph $G$ with parts $U,V$, split each $U$-neighborhood randomly into two parts, and put a complete bipartite graph between them; the resulting graph $H$ on $V$ is $F$-free because of the girth, and its independent-set count is controlled by the part sizes and degrees.

What would settle it

For the C5 bound, check whether the needed bipartite incidence graphs with parts of sizes $(q+1)(q^8+q^4+1)$ and $(q^3+1)(q^8+q^4+1)$, degrees $q+1$ and $q^3+1$, and girth at least 12 exist for every large $q$; if they exist only sparsely, the $(1+o(1))$ form can fail. For the conditional claim, exhibiting an $s\ge 4$ for which every $K_s$-free $(n,d,\lambda)$-graph with $d=\Omega(n^{1-1/(2s-3)})$ has $\lambda=\omega(\sqrt{d})$ would remove the hypothesis of Corollary 2.

Watch

Extended reading notes

Core claim

The paper's central claim is that an $F$-free $(n,d,\lambda)$-graph forces a lower bound on the Ramsey number $r(F,t)$: whenever such a graph exists, $r(F,t)>n/(20\lambda\log_2 n)$ for $t=\lceil 2n\log^2 n/d\rceil$. For $F=K_s$, optimal pseudorandom graphs with $d=\Omega(n^{1-1/(2s-3)})$ and $\lambda=O(\sqrt{d})$ then give $r(s,t)=\Omega(t^{s-1}/\log^{2s-4}t)$, which combines with the known upper bound to yield $r(s,t)=t^{s-1+o(1)}$. For odd cycles, applying the same theorem to existing pseudorandom $C_\ell$-free graphs yields $r(C_\ell,t)=\Omega(t^{(\ell-1)/(\ell-2)}/\log^{2/(\ell-2)}t)$ for odd $\ell\ge 5$, and for $\ell=6,10$ it gives $r(C_6,t)=\Omega(t^{5/4}/\sqrt{\log t})$ and $r(C_{10},t)=\Omega(t^{9/8}/\log^{1/4}t)$. The random block construction, starting from incidence graphs of generalized hexagons and octagons, proves $r(C_5,t)\ge (1+o(1))t^{11/8}$ and $r(C_7,t)\ge (1+o(1))t^{11/9}$; the paper notes these are the first graphs $F$ containing cycles for which the lower-bound exponent for $r(F,t)$ surpasses the random $F$-free process bound.

Load-bearing premise

The C5 and C7 bounds assume that the required high-girth bipartite incidence graphs with the stated part sizes and degrees exist for all large q; the conditional Ramsey-exponent result assumes optimal $K_s$-free pseudorandom graphs exist, a major open problem.

Editorial extensions

If this is right

  • If optimal $K_s$-free pseudorandom graphs exist for every fixed $s\ge 4$, then the classical Ramsey exponent is determined: $r(s,t)=t^{s-1+o(1)}$.
  • For every odd $\ell\ge 5$, the lower bound $r(C_\ell,t)=\Omega(t^{(\ell-1)/(\ell-2)}/\log^{2/(\ell-2)}t)$ improves the random $C_\ell$-free process bound by a polylogarithmic factor.
  • For $\ell=6$ and $\ell=10$, the new bounds $r(C_6,t)=\Omega(t^{5/4}/\sqrt{\log t})$ and $r(C_{10},t)=\Omega(t^{9/8}/\log^{1/4}t)$ exceed the previous best lower bounds.
  • The block construction proves $r(C_5,t)\ge (1+o(1))t^{11/8}$ and $r(C_7,t)\ge (1+o(1))t^{11/9}$, raising the exponent in these cycle-complete Ramsey lower bounds.
  • The generalized random block theorem converts any sufficiently dense $L(F)$-free bipartite graph into a lower bound on $r(F,t)$, so better such graphs would immediately improve Ramsey exponents.

Reading between the lines

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

  • One consequence the paper leaves implicit: if $r(s,t)$ turned out to be smaller than $t^{s-1+o(1)}$ for some $s\ge 4$, then optimal $K_s$-free pseudorandom graphs would be impossible, making the construction problem as hard as the Ramsey exponent itself.
  • The incidence-graph ingredient for the cycle bounds is limited to the few girths realized by generalized polygons; extending the exponent improvements to longer odd cycles would require new high-girth bipartite graphs with comparably tight degree ratios.
  • Because the random-sampling proof uses only a small number of random bits, an explicit construction of optimal $K_s$-free pseudorandom graphs would likely translate, after derandomization, into explicit Ramsey graphs with the same exponent; this is suggested by the paper's remark that its construction uses fewer random bits than the random process.
  • The exponents $11/8$ and $11/9$ are not proven optimal; the block method is a template, and any high-girth bipartite graph with parameters satisfying the expected-count inequality would push these exponents upward.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper is a short note connecting pseudorandom (n,d,lambda)-graphs to Ramsey lower bounds. Theorem 1 gives a general lower bound on r(F,t) from any F-free (n,d,lambda)-graph, via an Alon-Rodl count of independent sets followed by a random-subset argument; Corollary 2 turns this into a conditional statement that optimal K_s-free pseudorandom graphs would imply r(s,t)=t^{s-1+o(1)}. Corollaries 3 and 4 apply the same theorem to odd cycles and to C6 and C10, giving polylogarithmic improvements over the random C_l-free-process bounds. Theorem 5 uses a different random block construction on incidence graphs of generalized hexagons and Ree-Tits octagons to obtain r(C5,t) >= (1+o(1))t^{11/8} and r(C7,t) >= (1+o(1))t^{11/9}.

Significance. If the C7 part is corrected, the paper's significance is real: the C5 lower bound is the first unconditional exponent improvement for a cycle-complete Ramsey number over the random C_l-free process, and the conditional result on K_s-free pseudorandom graphs gives a clean reduction of a classical problem. The C5 computation is explicit and sound, and the random-subset application of the Alon-Rodl bound is elegant and likely reusable. The paper also correctly identifies that the C7 exponent 11/9 still exceeds the random-process exponent 6/5, so the central novelty survives even after the leading-constant issue in the C7 statement is fixed.

major comments (2)
  1. [Section 2, Eq. (5)] The displayed bound in Eq. (5) is r(F,t) > n/(20 lambda log^2 n), but the proof gives r(F,t) >= pn - 1 with p = log^2 n/(2 e^2 lambda), hence r(F,t) = Omega(n log^2 n / lambda). The reciprocal placement of log^2 n is a typo: the intended bound is r(F,t) > n log^2 n/(20 lambda). This is load-bearing because Corollaries 2-4 use the stronger form; for example, substituting the printed (5) into the Alon-Kahale parameters in Corollary 3 gives a denominator log^{(4l-6)/(l-2)} t rather than the claimed log^{2/(l-2)} t, while the corrected bound gives exactly the stated corollaries.
  2. [Section 3, Theorem 5 (second statement)] The C7 half of Theorem 5 is not supported as stated. The construction uses Ree-Tits octagons, which exist only for q = 2^{2n+1}, as in the cited Van Maldeghem reference. The construction gives n ~ q^{11} and t ~ q^9 only along this sparse geometric progression. Since r(C7,t) is monotone, filling the gaps for arbitrary t yields at best r(C7,t) >= c t^{11/9} with a constant of order 4^{-11}, not (1+o(1)) t^{11/9}. The sentence 'We omit the details for this case' hides exactly the calculation that controls the leading constant. The theorem and abstract should be corrected, either by restricting the asymptotic to t of the form q^9 with q = 2^{2n+1}, or by weakening the conclusion to r(C7,t) = Omega(t^{11/9}). The C5 half is not affected, because generalized hexagons of order (q,q^3) exist for all prime powers q.
minor comments (4)
  1. [Section 3, Eqs. (9)-(10)] For t_u = 0, the probability that I intersects N_G(u) spans no edge in H is 1, while 2^{1-t_u} = 2. The displayed equality in (9) and (10) should be an inequality P(e(I cap N_G(u)) = 0) <= 2^{1-t_u} and similarly for the product; the subsequent expectation bound is unaffected because the inequality is the needed upper bound.
  2. [Section 3, proof of Theorem 5] The phrase 'we may take t = (1+o(1))q^8' is too terse. To make the exponent m - (q+1)t tend to -infinity, one must take t = (1+epsilon)q^8 with epsilon q^9 -> infinity; the authors should state this explicitly rather than leaving the o(1) unspecified.
  3. [Section 4, Theorem 7] The assertion that H is automatically F-free when G is L(F)-free is stated without proof. A short justification is needed, because the correspondence between a copy of F in H and a copy of some member of L(F) in G is not immediate.
  4. [Abstract and Corollary 3] The remark that for l=3 the bound 'matches the lower bound of Spencer' should specify that this is Spencer's local-lemma bound r(3,t) = Omega(t^2/log^2 t), not the later Kim bound, to avoid ambiguity.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity; the paper's bounds follow from external pseudorandom constructions and a self-contained counting argument, with only a non-load-bearing self-citation for the random-block idea.

full rationale

The paper's derivation chain is not circular. Theorem 1 is a direct application of the external Alon–Rodl independent-set bound, and Corollary 2 simply instantiates Theorem 1 under an explicitly stated existence assumption on optimal pseudorandom K_s-free graphs; the conclusion is not used to define or justify the assumed graphs. The cycle lower bounds in Corollaries 3 and 4 use prior constructions of Alon–Kahale and polarity graphs of generalized quadrangles/hexagons, all of which are external to the paper. Theorem 5's C5 bound is proved in full by the random-block argument: the graph H is defined from an incidence graph of generalized hexagons, and the expected number of large independent sets is calculated and shown to be o(1); the result is not equivalent to an input. The C7 case is explicitly summarized as 'We omit the details for this case, which are almost identical to the above,' so it is an omitted proof rather than a circular reduction; any concern that Ree–Tits octagons exist only for a sparse set of q is a correctness/density issue, not circularity. The only self-citation is [24] for the random-block idea, but the paper reproduces the argument and also cites independent sources [15] and [13]; this self-citation is not load-bearing. No fitted parameter is renamed as a prediction, and no uniqueness theorem is imported from the authors' prior work. Accordingly, the appropriate finding is no significant circularity.

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

The results rely on prior constructions of pseudorandom and incidence graphs, listed as domain assumptions. No free parameters are fitted to data (q is a construction parameter ranging over prime powers). No new entities are introduced.

assumptions (6)
  • standard math Theorem 6 (Alon-Rodl): the number of independent sets of size t in an (n,d,lambda)-graph is at most (2e^2 lambda / log^2 n)^t.
    Proved in [5]; the paper gives a proof sketch in Section 2.
  • domain assumption Existence of Alon-Kahale C_l-free (n,d,lambda)-graphs for odd l with d = Theta(n^{2/l}) and lambda = O(sqrt(d)).
    Used for Corollary 3; construction from [3].
  • domain assumption Existence of polarity graphs of projective planes with n = q^2+q+1, d = q+1, lambda = sqrt(q).
    Used to match the r(C4,t) bound from the C4-free process; from [29].
  • domain assumption Existence of polarity graphs of generalized quadrangles and hexagons with the stated parameters (n, d, lambda).
    Used for Corollary 4; from [10,27].
  • domain assumption Existence of incidence graphs of generalized hexagons of order (q,q^3) with girth at least twelve, part sizes m = (q+1)(q^8+q^4+1) and n = (q^3+1)(q^8+q^4+1), and degrees q+1 and q^3+1.
    Used in Theorem 5 for the C5 bound; from [18,36,6].
  • domain assumption Existence of Ree-Tits octagons with part sizes and girth at least sixteen for the C7 case.
    Assumed in Section 3 for the C7 bound; details omitted in the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A note on pseudorandom Ramsey graphs." pith.science (2026). https://pith.science/paper/IVHCRMZK

@misc{pith2026190901461,
  author       = {Pith},
  title        = {Pith review of: A note on pseudorandom Ramsey graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IVHCRMZK}},
  note         = {Machine review of arXiv:1909.01461}
}
abstract

For fixed $s \ge 3$, we prove that if optimal $K_s$-free pseudorandom graphs exist, then the Ramsey number $r(s,t) = t^{s-1+o(1)}$ as $t \rightarrow \infty$. Our method also improves the best lower bounds for $r(C_{\ell},t)$ obtained by Bohman and Keevash from the random $C_{\ell}$-free process by polylogarithmic factors for all odd $\ell \geq 5$ and $\ell \in \{6,10\}$. For $\ell = 4$ it matches their lower bound from the $C_4$-free process. We also prove, via a different approach, that $r(C_5, t)> (1+o(1))t^{11/8}$ and $r(C_7, t)> (1+o(1))t^{11/9}$. These improve the exponent of $t$ in the previous best results and appear to be the first examples of graphs $F$ with cycles for which such an improvement of the exponent for $r(F, t)$ is shown over the bounds given by the random $F$-free process and random graphs.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

37 extracted references · 36 canonical work pages

  1. [1]

    Ajtai, J

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

    work page 1980

  2. [2]

    Alon, Explicit Ramsey graphs and orthonormal labelin gs, Electron

    N. Alon, Explicit Ramsey graphs and orthonormal labelin gs, Electron. J. Combin. 1 (1994), Research Paper 12, approx. 8 pp

    work page 1994

  3. [3]

    N. Alon, N. Kahale, Approximating the independence numb er via the θ-function, Math. Pro- gramming 80 (1998), 253–264

    work page 1998

  4. [4]

    N. Alon, M. Krivelevich, Constructive bounds for a Ramse y-type problem, Graphs Combin. 13 (1997), no. 3, 217–225

    work page 1997

  5. [5]

    N. Alon, V. R¨ odl, Sharp bounds for some multicolor Ramse y numbers, Combinatorica 25 (2005), no. 2, 125–141

    work page 2005

  6. [6]

    De Bruyn, An introduction to incidence geometry, Fron tiers in Mathematics

    B. De Bruyn, An introduction to incidence geometry, Fron tiers in Mathematics. Birkhuser/Springer, Cham, 2016. xii+372 pp

    work page 2016

  7. [7]

    A construction for clique-free pseudorandom graphs

    A.Bishnoi, F. Ihringer, V. Pepe, A construction for cliq ue-free pseudorandom graphs, https://arxiv.org/abs/1905.04677

    work page Pith review arXiv 1905

  8. [8]

    Bohman, P

    T. Bohman, P. Keevash, Dynamic concentration of the tria ngle-free process, The Seventh Eu- ropean Conference on Combinatorics, Graph Theory and Appli cations, 489–495, CRM Series, 16, Ed. Norm., Pisa, 2013

    work page 2013

Show all 37 references
  1. [9]

    Bohman, P

    T. Bohman, P. Keevash, The early evolution of the H-free process, Invent. Math. 181 (2010), no. 2, 291–336

    2010

  2. [10]

    Brouwer, A

    A. Brouwer, A. Cohen, A. Neumaier, Distance-Regular Gr aphs, Springer-Verlag, Berlin, 1989

    1989

  3. [11]

    Y. Caro, Y. Li, C. Rousseau, Y. Zhang, Asymptotic bounds for some bipartite graph: complete graph Ramsey numbers, Discrete Math. 220 (2000), no. 1-3, 51 –56

    2000

  4. [12]

    Croot, V

    E. Croot, V. Lev, Open problems in additive combinatori cs, Additive combinatorics, 207–233, CRM Proc. Lecture Notes, 43, Amer. Math. Soc., Providence, R I, 2007

    2007

  5. [13]

    Conlon, A sequence of triangle-free pseudorandom gr aphs, Combin

    D. Conlon, A sequence of triangle-free pseudorandom gr aphs, Combin. Probab. Comput. 26 (2017), no. 2, 195–200

    2017

  6. [14]

    Conlon, J

    D. Conlon, J. Lee, On the extremal number of subdivision s, preprint: arXiv:1807.05008

    arXiv

  7. [15]

    Dudek, T

    A. Dudek, T. Retter, V. R¨ odl, On generalized Ramsey num bers of Erd˝ os and Rogers, J. Combin. Theory Ser. B 109 (2014), 213–227. Mubayi and Verstra ¨ ete: Ramsey numbers 9

    2014

  8. [16]

    Erd˝ os, G

    P. Erd˝ os, G. Szekeres, A combinatorial problem in geom etry, Compositio Math. 2 (1935), 463–470

    1935

  9. [17]

    Fiz Pontiveros, S

    G. Fiz Pontiveros, S. Griffiths, R. Morris, The triangle- free process and the Ramsey number R(3, k), Mem. Amer. Math. Soc., to appear

  10. [18]

    Govaert, H

    E. Govaert, H. Van Maldeghem, Some combinatorial and ge ometric characterizations of the finite dual classical generalized hexagons, J. Geom. 68 (200 0), no. 1-2, 87–95

  11. [19]

    Graham, C

    S. Graham, C. Ringrose, Lower bounds for least quadrati c nonresidues, Analytic number theory (Allerton Park, IL, 1989), 269–309, Progr. Math., 85, Birkh user Boston, Boston, MA, 1990

    1989

  12. [20]

    Hanson, G

    B. Hanson, G. Petridis, Refined Estimates Concerning Su msets Contained in the Roots of Unity, https://arxiv.org/abs/1905.09134

    1905 arXiv

  13. [21]

    Hoory, The Size of Bipartite Graphs with Given Girth, J

    S. Hoory, The Size of Bipartite Graphs with Given Girth, J. Combin. Theory, Ser. B 86 (2002), no. 2, 215–220

    2002

  14. [22]

    Janzer, Improved bounds for the extremal number of su bdivisions, preprint: arXiv:1809.00468

    O. Janzer, Improved bounds for the extremal number of su bdivisions, preprint: arXiv:1809.00468

    arXiv

  15. [23]

    J. H. Kim, The Ramsey number R(3, t) has order of magnitude t2/ log t, Random Structures Algorithms 7 (1995), no. 3, 173–207

    1995

  16. [24]

    Kostochka, D

    A. Kostochka, D. Mubayi, J. Verstra¨ ete, Hypergraph Ra msey numbers: triangles versus cliques, J. Combin. Theory Ser. A 120 (2013), no. 7, 1491–150 7

    2013

  17. [25]

    Kostochka, P

    A. Kostochka, P. Pudl´ ak, V. R¨ odl, Some constructive bounds on Ramsey numbers, J. Combin. Theory Ser. B 100 (2010), no. 5, 439–445

    2010

  18. [26]

    Krivelevich, B

    M. Krivelevich, B. Sudakov, Pseudo-random graphs, Mor e sets, graphs and numbers, 199–262, Bolyai Soc. Math. Stud., 15, Springer, Berlin, 2006

    2006

  19. [27]

    Lazebnik, V

    F. Lazebnik, V. Ustimenko, A. Woldar, Polarities and 2k -cycle-free graphs, Discrete Math. 197/198 (1999), 503–513

    1999

  20. [28]

    Montgomery, Topics in multiplicative number theory

    H. Montgomery, Topics in multiplicative number theory . Lecture Notes in Mathematics, Vol

  21. [29]

    Mubayi, J

    D. Mubayi, J. Williford, On the independence number of t he Erd˝ os-Rnyi and projective norm graphs and a related hypergraph, J. Graph Theory 56 (2007), n o. 2, 113–127

    2007

  22. [30]

    Nilli, On the second eigenvalue of a graph, Discrete M ath

    A. Nilli, On the second eigenvalue of a graph, Discrete M ath. 91 (1991), no. 2, 207–210

    1991

  23. [31]

    Nilli, Tight estimates for eigenvalues of regular gr aphs, Electron

    A. Nilli, Tight estimates for eigenvalues of regular gr aphs, Electron. J. Combin. 11 (2004), no. 1, Note 9, 4 pp. Mubayi and Verstra ¨ ete: Ramsey numbers 10

    2004

  24. [32]

    Shearer, A note on the independence number of triangl e-free graphs, Discrete Math

    J. Shearer, A note on the independence number of triangl e-free graphs, Discrete Math. 46 (1983), no. 1, 83–87

    1983

  25. [33]

    Spencer, Asymptotic lower bounds for Ramsey functio ns, Discrete Math

    J. Spencer, Asymptotic lower bounds for Ramsey functio ns, Discrete Math. 20 (1977/78), no. 1, 69–76

    1977

  26. [34]

    Sudakov, A note on odd cycle-complete graph Ramsey nu mbers, Electron

    B. Sudakov, A note on odd cycle-complete graph Ramsey nu mbers, Electron. J. Combin. 9 (2002), no. 1, Note 1, 4 pp

    2002

  27. [35]

    Sudakov, T

    B. Sudakov, T. Sza´ o, V. Vu, A generalization of Turn’s t heorem, J. Graph Theory 49 (2005), no. 3, 187–195

    2005

  28. [36]

    Van Maldeghem, Generalized polygons, Modern Birkh¨ auser Classics

    H. Van Maldeghem, Generalized polygons, Modern Birkh¨ auser Classics. Birkh¨ auser/Springer Basel AG, Basel, 1998

    1998

  29. [227]

    ix+178 pp

    Springer-Verlag, Berlin-New York, 1971. ix+178 pp

    1971

Pith tools

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