pith. sign in

arxiv: 2512.17718 · v2 · pith:FAYJ5MLYnew · submitted 2025-12-19 · 🧮 math.CO

Gaussian random graphs and Ramsey numbers

Zach Hunter , Aleksa Milojevi\'c , Benny Sudakov This is my paper

Pith reviewed 2026-05-21 16:48 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C55
keywords Ramsey numbersGaussian random graphslower boundsprobabilistic methodextremal graph theorycombinatorial constructionsrandom graphs
0
0 comments X

The pith

Gaussian random graphs provide a simpler proof and stronger quantitative bounds for Ramsey lower bounds.

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

The paper seeks to establish that an alternative construction using Gaussian random graphs yields a markedly simpler proof of exponential improvements in lower bounds for diagonal Ramsey numbers. A sympathetic reader would care because these bounds clarify how large a graph must be before it is forced to contain a large clique or independent set, directly affecting the limits of what can be avoided in large combinatorial structures. The authors replace prior models with Gaussian edge weights to reduce the technical overhead in concentration and deletion arguments. This change not only clarifies the reasoning but also produces improved constants in the resulting exponential bounds.

Core claim

The central claim is that basing the construction on Gaussian random graphs instead of more complex alternatives allows the probabilistic deletion method to be analyzed with far less technical machinery, thereby proving the recent exponential improvement in Ramsey lower bounds while also delivering better quantitative constants than the original argument.

What carries the argument

Gaussian random graphs, in which potential edges receive independent Gaussian weights, which supply the concentration and independence needed to run the probabilistic counting and deletion steps cleanly.

If this is right

  • The lower bounds on diagonal Ramsey numbers improve by a constant factor in the exponent.
  • The proof of the exponential improvement becomes accessible using only standard probabilistic tools.
  • The same Gaussian construction can be reused for related extremal problems that rely on similar deletion arguments.

Where Pith is reading between the lines

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

  • The Gaussian model may extend naturally to hypergraph Ramsey numbers or off-diagonal variants.
  • Similar simplifications could appear when Gaussian weights replace other random models in extremal graph theory.
  • The concentration properties might support explicit or algorithmic constructions that avoid full randomness.

Load-bearing premise

The Gaussian random graph model supplies sufficiently strong concentration or independence properties to carry the probabilistic deletion or counting arguments through without the technical overhead present in prior constructions.

What would settle it

A calculation showing that the new bounds are not quantitatively stronger than those obtained by Ma, Shen and Xie, or a failure of the required concentration inequalities under the Gaussian model for the relevant parameters.

read the original abstract

We give a simple proof of the recent remarkable exponential improvement for Ramsey lower bounds, obtained by Ma, Shen and Xie. Our key ingredient is an alternative construction based on Gaussian random graphs, which allows us to simplify their analysis significantly. As a consequence of this simpler analysis, we also obtain better quantitative bounds.

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.

Referee Report

1 major / 2 minor

Summary. The manuscript claims to give a simple proof of the recent exponential improvement for Ramsey lower bounds obtained by Ma, Shen and Xie. The key ingredient is an alternative construction based on Gaussian random graphs, which simplifies their analysis significantly and yields better quantitative bounds as a consequence.

Significance. If the Gaussian construction supplies the required concentration and independence properties for the probabilistic deletion arguments, the work would be a useful contribution by providing a cleaner route to the exponential Ramsey improvement and by sharpening the constants. The simplification itself is a strength that could aid further research in probabilistic Ramsey theory.

major comments (1)
  1. [§3] §3, the analysis following the definition of the Gaussian edge indicators: the claimed simplification rests on applying elementary tail bounds directly to the number of monochromatic cliques, but the non-zero correlations induced by shared underlying Gaussians are not shown to be negligible in the variance or higher-moment calculations at the scale where the exponential gain appears. This step is load-bearing for both the simplification claim and the improved quantitative bounds.
minor comments (2)
  1. [Introduction] The precise statement of the improved constants relative to Ma-Shen-Xie should be stated explicitly in the introduction or in a dedicated comparison subsection.
  2. Notation for the Gaussian random variables and the resulting edge indicators could be made uniform across the construction and the counting arguments.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for recognizing the potential value of the Gaussian construction in simplifying the exponential Ramsey lower bound. We address the single major comment below.

read point-by-point responses

  1. Referee: [§3] §3, the analysis following the definition of the Gaussian edge indicators: the claimed simplification rests on applying elementary tail bounds directly to the number of monochromatic cliques, but the non-zero correlations induced by shared underlying Gaussians are not shown to be negligible in the variance or higher-moment calculations at the scale where the exponential gain appears. This step is load-bearing for both the simplification claim and the improved quantitative bounds.

    Authors: We agree that an explicit treatment of the correlations is necessary to justify both the simplification and the improved constants. In the Gaussian model the edge indicators are threshold functions of jointly Gaussian random variables whose pairwise correlations are determined by the number of shared vertices. For the variance of the number of monochromatic cliques, the covariance terms arising from pairs of cliques that share an edge can be bounded using the Gaussian correlation inequality and the fact that such pairs occur with probability O(1/n) relative to the main term. At the scale where the exponential improvement appears, these covariance contributions are o(1) times the variance of the independent case, so the elementary Chernoff-type tail bounds remain valid up to lower-order factors that do not affect the leading exponential gain. We will add a short lemma in the revised §3 that records this calculation explicitly, thereby making the argument self-contained while preserving the claimed simplification. revision: yes

Circularity Check

0 steps flagged

No circularity: independent Gaussian construction yields self-contained probabilistic proof

full rationale

The paper introduces an alternative Gaussian random graph model as the key ingredient for a simplified proof of the exponential Ramsey lower bound improvement first obtained by Ma, Shen and Xie. The derivation proceeds via direct probabilistic deletion and counting arguments applied to this new model, without fitting parameters from prior data, without renaming known results, and without load-bearing self-citations that reduce the central claim to an unverified premise. The quantitative improvements are presented as consequences of the simpler analysis rather than tautological re-expressions of the input bounds. The construction and its concentration properties are developed from first principles within the paper, rendering the overall argument self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard properties of Gaussian random variables and the probabilistic method in graph theory; no new free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Gaussian random variables induce edge probabilities that satisfy the necessary concentration bounds for the Ramsey avoidance argument.
    Invoked when the paper replaces the prior construction with the Gaussian model.

pith-pipeline@v0.9.0 · 5560 in / 1122 out tokens · 40950 ms · 2026-05-21T16:48:19.515366+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. A double-exponential lower bound for $r_4(5,n)$

    math.CO 2026-04 unverdicted novelty 8.0

    r_4(5,n) is at least 2^{2^{c n^{1/7}}}, determining the tower growth rate of r_k(k+1,n) for hypergraph Ramsey numbers.

  2. A Note on Generalized Erd\H{o}s-Rogers Problems

    math.CO 2026-04 unverdicted novelty 7.0

    f^{(4)}_{5^{-},6}(N) equals (log log N) to the Theta(1) power, with improved lower bounds r_4(6,n) >= 2^{2^{c sqrt(n)}} and r_k(k+2,n).

  3. An improved double-exponential lower bound for $r_4(5,n)$

    math.CO 2026-05 unverdicted novelty 5.0

    The Ramsey number r_4(5,n) is at least 2^{2^{Omega(n^{1/5})}}, an improvement over the prior 2^{2^{Omega(n^{1/7})}} achieved by reducing greedy layers in the construction from seven to five.

  4. An improved double-exponential lower bound for $r_4(5,n)$

    math.CO 2026-05 unverdicted novelty 4.0

    The paper establishes the improved lower bound r_4(5,n) >= 2^{2^{Omega(n^{1/5})}} for the 4-uniform 5-clique Ramsey number by reducing greedy local-maxima selection from seven layers to five in a modified construction.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages · cited by 3 Pith papers · 1 internal anchor

  1. [1]

    Balister, B

    P. Balister, B. Bollob´ as, M. Campos, S. Griffiths, E. Hurley, R. Morris, J. Sahasrabudhe and M. Tiba.Upper bounds for multicolour Ramsey numbers.arXiv:2410.17197

    work page arXiv

  2. [2]

    Barreto, O

    M. Barreto, O. Marchal, and J. Arbel.Optimal sub-Gaussian variance proxy for truncated Gaussian and exponential random variablesarXiv:2403.08628

    work page arXiv

  3. [3]

    Bubeck, J

    S. Bubeck, J. Ding, R. Eldan and M.Z. R´ acz.Testing for high-dimensional geometry in random graphs.Random Structures Algorithms, 49 (2016), 503–532

    work page 2016

  4. [4]

    Campos, S

    M. Campos, S. Griffiths, R. Morris and J. Sahasrabudhe.An exponential improvement for diagonal Ramsey.to appear in Ann. of Math

    work page

  5. [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

    work page arXiv

  6. [6]

    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

    work page 2009

  7. [7]

    Conlon and A

    D. Conlon and A. Ferber.Lower bounds for multicolour Ramsey numbers.Adv. Math., 378 (2021), Paper No. 107528, 5 pp

    work page 2021

  8. [8]

    Devroye, A

    L. Devroye, A. Gy¨ orgy, G. Lugosi and F. Udina.High-dimensional random geometric graphs and their clique number. Electron. J. Probab., 16 (2011), Paper no. 90, 2481–2508

    work page 2011

  9. [9]

    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

  10. [10]

    Erd˝ os and G

    P. Erd˝ os and G. Szekeres.A combinatorial problem in geometry.Compos. Math., 2 (1935), 463–470. GAUSSIAN RANDOM GRAPHS AND RAMSEY NUMBERS 15

    work page 1935

  11. [11]

    Gordon.Values of Mills’ ratio of area to bounding ordinate and of the normal probability integral for large values of the argument.Ann

    R.D. Gordon.Values of Mills’ ratio of area to bounding ordinate and of the normal probability integral for large values of the argument.Ann. Math. Statist., 12 (1941), 364–366

    work page 1941

  12. [12]

    Gupta, N

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

    work page arXiv

  13. [13]

    Hefty, P

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

    work page arXiv

  14. [14]

    Laurent and P

    B. Laurent and P. Massart.Adaptive estimation of a quadratic functional by model selectionAnn. Stat., 28 (2000): 1302–1338

    work page 2000

  15. [15]

    J. Ma, W. Shen and S. Xie.An exponential improvement for Ramsey lower bounds.arXiv:2507.12926

    work page internal anchor Pith review Pith/arXiv arXiv

  16. [16]

    Mattheus and J

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

    work page 2024

  17. [17]

    Mubayi and J

    D. Mubayi and J. Verstra¨ ete.A note on pseudorandom Ramsey graphs.J. Eur. Math. Soc., 26 (2024) 153–161

    work page 2024

  18. [18]

    Penrose.Random Geometric Graphs.Oxford Studies in Probability, 5, Oxford University Press, 2003

    M. Penrose.Random Geometric Graphs.Oxford Studies in Probability, 5, Oxford University Press, 2003

    work page 2003

  19. [19]

    Ramsey.On a Problem of Formal Logic.Proc

    F.P. Ramsey.On a Problem of Formal Logic.Proc. London Math. Soc., 30 (1930), 264–286

    work page 1930

  20. [20]

    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

  21. [21]

    Spencer.Ramsey’s theorem—A new lower bound.J

    J. Spencer.Ramsey’s theorem—A new lower bound.J. Combin. Theory Ser. A, 18 (1975), 108–115

    work page 1975

  22. [22]

    Thomason.An upper bound for some Ramsey numbers.J

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

    work page 1988

  23. [23]

    R. Vershynin.High-Dimensional Probability: An Introduction with Applications in Data Science.Cambridge Series in Statistical and Probabilistic Mathematics, 47, Cambridge University Press, 2018. AppendixA.Proofs of Preliminaries Proof of Lemma 2.1.If∥x∥ 2 /∈(1−δ,1 +δ), then we also have∥x∥ 2 2 /∈(1−δ,1 +δ). As we have already observed, if we defineY=d∥x∥ 2...

    work page 2018