Pith. sign in

REVIEW 1 major objections 3 minor 15 references

Combinatorial theorems relative to sparse sets

T0 review · 1 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read The paper is a survey establishing that classical combinatorial theorems—Ramsey, Turán, Szemerédi, and removal lemmas—transfer to sparse random, pseudorandom, and extremal sets down to precisely identified thresholds, and it poses the open

desk verdict A useful, expert survey with two statement-level errors (Theorem 4.3 is false as written for k=2) that need correcting before it can be fully trusted as a reference. read the letter →

arxiv 2608.01525 v1 pith:HSFRLJGS submitted 2026-08-02 math.CO

David Conlon This is my paper · ORCID
classification math.CO MSC 05C8005C5505C3505D1005D4011B30
keywords sparserandomgraphsRamseytheoryTuránpropertyremovallemmapseudorandomSzemeréditheoremSidonsetscombinatorialtransference
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

The paper is a survey of the recent program that asks when classical combinatorial theorems—Ramsey's theorem, Turán's theorem, Szemerédi's theorem, and various removal lemmas—continue to hold when the ambient complete structure is replaced by a sparse subset. It claims that this program has matured into a coherent theory with three regimes: random sets, pseudorandom sets, and extremal sets. In the random regime the thresholds are governed by the parameter $m_2(H)$; in the pseudorandom regime by the jumbledness parameter and the linear-forms condition; and in the extremal regime by structural sparsity such as having no 4-cycles. The survey also collects the open problems that remain, including asymmetric Ramsey thresholds, sharp thresholds for the triangle Ramsey property, and counting lemmas relative to $C_4$-free graphs.

What carries the argument

The organising device is a family of threshold parameters: $m_2(H) = \max\{(e(H')-1)/(v(H')-2) : H'\subseteq H, v(H')\ge 3\}$, its asymmetric generalisation $m_2(H_1,H_2)$, the jumbledness parameter $\beta$ for pseudorandom graphs, and the $H$-linear forms condition for hypergraphs. These parameters carry the argument by locating the density below which the sparse set is too poor to support the relevant copies, and above which transference techniques (containers, densification, or random algebraic constructions) succeed.

What would settle it

Verify Theorem 2.2 by checking the four source papers for the asymmetric Ramsey theorem; if their combined results do not yield the stated threshold $n^{-1/m_2(H_1,H_2)}$ for all $m_2(H_2)>1$, the survey's account is wrong. Alternatively, find a counterexample to Theorem 4.5 by constructing a Sidon set of size $\omega(\sqrt{n})$ with no distinct-variable solution to $x_1+x_2+x_3+x_4=4x_5$.

Watch

Extended reading notes

Core claim

The survey's central assertion is that combinatorial theorems can be meaningfully transferred from dense settings to sparse ones, and that the thresholds for such transfer can often be identified exactly. In the random case, the critical probability is $n^{-1/m_2(H)}$, where $m_2(H)$ is the maximum of $(e(H')-1)/(v(H')-2)$ over subgraphs $H'$ of $H$; the same exponent governs Ramsey, Turán, and removal properties, and an asymmetric variant $m_2(H_1,H_2)$ now settles the Kohayakawa–Kreuter conjecture. For pseudorandom graphs, the paper describes a densification method that proves analogues under a jumbledness condition $\beta \le c p^t n$, and for hypergraphs under an $H$-linear forms conditi

Load-bearing premise

The survey's usefulness rests on the accuracy and correct attribution of the theorems it cites from the literature, especially the recently aggregated asymmetric Ramsey theorem and the removal lemmas for $C_4$-free graphs; if any summary misstates hypotheses or thresholds, the survey would mislead.

Editorial extensions

If this is right

  • The Kohayakawa–Kreuter conjecture is now a theorem, giving the sharp threshold for asymmetric Ramsey properties of random graphs in terms of $m_2(H_1,H_2)$.
  • The transference program for bounded-size objects to random sets is effectively complete: Turán, Szemerédi, and removal theorems all hold down to the $m_2(H)$ threshold, so the open frontier moves to large objects and hypergraphs.
  • Pseudorandom relative removal lemmas hold under a linear forms condition, providing a clean route to results such as polynomial progressions in the primes.
  • The extremal removal theorems imply that every $k$-uniform hypergraph of girth greater than 5 has $o(n^{3/2})$ edges, and that Sidon sets avoiding distinct-variable solutions to $x_1+x_2+x_3+x_4=4x_5$ have size at most $o(\sqrt{n})$ and at least $n^{1/2-o(1)}$.
  • The paper's open problems—sharp threshold at $C/\sqrt{n}$ for the $(K_3,2)$-Ramsey property, the pseudorandom triangle removal gap, and counting lemmas relative to $C_6$-free graphs—define concrete targets for the next phase of the field.

Reading between the lines

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

  • The recurrence of the same exponent $m_2(H)$ across Ramsey, Turán, and removal statements hints that a single underlying obstruction—the density of the densest subgraph—may control all transfer phenomena, suggesting a design principle for new transfer theorems.
  • If the pseudorandom triangle removal lemma held at $\beta \le c p^2 n$ (Problem 3.3), removal would work as soon as triangles are abundant in a pseudorandom graph, likely also settling the open stability problem for triangle-free subgraphs of pseudorandom graphs.
  • The Sidon-set result suggests a broader additivity phenomenon: jointly forbidding two independent linear equations can sharply reduce the maximum set size, and other pairs of equations may exhibit similar drops.
  • A positive resolution of the conjecture that 3-uniform hypergraphs of girth 6 can have $n^{3/2-o(1)}$ edges would show that girth constraints alone do not force sparser hypergraphs, paralleling the $C_4$-free graph case.
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

1 major / 3 minor

Summary. This is a survey by David Conlon on combinatorial theorems that hold relative to sparse subsets of their natural settings. The paper is organized into three themes: random sets (Rödl–Ruciński Ramsey thresholds, asymmetric Ramsey/Kohayakawa–Kreuter progress, Turán and Szemerédi transference, sparse removal lemmas, size-Ramsey numbers), pseudorandom sets (jumbled graphs, removal lemmas, relative hypergraph removal and consequences for Green–Tao), and extremal sets (C4-free graphs, C5-removal, Sidon sets). It is written as an expert overview without proofs; the statements are cited to the literature. The paper explicitly disclaims comprehensiveness and highlights open problems, several of which are concrete and recent.

Significance. The survey fills a useful role as a concise, up-to-date guide to an active area. Its main value is the reliable aggregation of theorems and open problems, especially the recent asymmetric Ramsey theorem and the extremal-set results. The author is a leading contributor, and many open problems (e.g., Problems 2.4, 3.1, 4.7) are well posed and likely to be influential. However, because the survey does not contain proofs, its correctness rests entirely on the accuracy of the cited statements; the error in Theorem 4.3 shows that a careful proofreading pass against the sources is needed.

major comments (1)
  1. [Theorem 4.3] The theorem is stated for every k-uniform hypergraph with girth greater than 5. As written it includes k=2, i.e., graphs, and is false in that case: the incidence graph of a projective plane of order q has n=2(q^2+q+1) vertices, Θ(n^{3/2}) edges, and girth 6. The statement should be restricted to k≥3, presumably matching the original source. Since the survey's purpose is to give reliable theorem statements, this correction is necessary.
minor comments (3)
  1. [Theorem 2.8] In the conclusion, 'every r-colouring of the edges of G_{n,p}' should read 'G_{N,p}'; as written, n in G_{n,p} is not the vertex count of the random graph under discussion.
  2. [Section 3] Typo: 'who may ask' should be 'one may ask'.
  3. [General] Given the survey's reliance on citations, a sentence in the introduction stating that all displayed theorems are quoted from the cited sources, and that any errors of transcription are the author's, would help set expectations.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: survey attributes external published theorems; no derivation reduces to its inputs.

full rationale

This is a survey article. Its claims are attributions to published theorems (Rödl–Ruciński, Conlon–Gowers, Schacht, Green–Tao, Conlon–Fox–Sudakov–Zhao, etc.), not derivations from assumptions introduced in this paper. No parameter is fitted to data and then reported as a prediction; no quantity is defined in terms of the result it is supposed to establish; no uniqueness claim is imported from the author's own prior work to force a choice; no known pattern is merely renamed. Heavy self-citation occurs (e.g., Theorems 2.5, 3.2, 4.1–4.5), but the cited works are published with proofs and are externally checkable, so they do not constitute circularity. The possible misstatement of Theorem 4.3 (missing k≥3, contradicted by incidence graphs of projective planes for k=2) is an accuracy/correctness concern, not a circular one: it does not make the theorem's conclusion an input to its own proof. Therefore no significant circularity.

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

The survey does not prove its central theorems; it relies on the correctness of the cited literature. The most load-bearing of these are listed below.

assumptions (4)
  • domain assumption The Rödl–Ruciński theorem (Theorem 2.1) correctly determines the threshold for the Ramsey property of random graphs.
    The survey relies on this cited theorem without proof.
  • domain assumption The transference theorems of Conlon–Gowers and Schacht (Theorem 2.5 and related) are correct.
    The survey cites these as establishing sparse analogues of Turán's and Szemerédi's theorems.
  • domain assumption The resolution of the Kohayakawa–Kreuter conjecture (Theorem 2.2) by multiple groups is correct.
    The survey summarizes this result from four cited papers without proof.
  • domain assumption The extremal removal lemmas of Conlon–Fox–Sudakov–Zhao (Theorems 4.1-4.3, 4.5) are correct.
    The survey presents these results relative to C4-free graphs and Sidon sets.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Combinatorial theorems relative to sparse sets." pith.science (2026). https://pith.science/paper/HSFRLJGS

@misc{pith2026260801525,
  author       = {Pith},
  title        = {Pith review of: Combinatorial theorems relative to sparse sets},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HSFRLJGS}},
  note         = {Machine review of arXiv:2608.01525}
}
read the original abstract

A key theme in modern extremal combinatorics is the study of classical combinatorial theorems relative to sparse subsets of their natural settings. Here we describe some of the recent progress in this area and state a number of problems that remain open and pressing.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 12 canonical work pages

  1. [1]

    Partition universality for graphs of bounded degeneracy and degree

    [AB25+] P. Allen and J. B¨ ottcher,Partition universality for graphs of bounded degeneracy and degree,preprint available at arXiv:2211.15819 [math.CO]. [ABHKP25] P. Allen, J. B¨ ottcher, H. H` an, Y. Kohayakawa and Y. Person,Blow- up lemmas for sparse graphs, Discrete Anal.2025, Paper No. 8, 141 pp. [ABSS20] P. Allen, J. B¨ ottcher, J. Skokan and M. Stein...

    work page Pith review arXiv 2025

  2. [11]

    R¨ odl and J

    [RS04] V. R¨ odl and J. Skokan,Regularity lemma for uniform hypergraphs,Ran- dom Structures Algorithms25(2004), 1–42. [RSz00] V. R¨ odl and E. Szemer´ edi,On size Ramsey numbers of graphs with bounded degree, Combinatorica20(2000), 257–262. [R53] K. F. Roth,On certain sets of integers, J. London Math. Soc.28(1953), 104–109. [RSz78] I. Z. Ruzsa and E. Szem...

    work page 2004

  3. [13]

    Tao and T

    [TZ18] T. Tao and T. Ziegler,Polynomial patterns in the primes, Forum Math. Pi6(2018), e1, 60 pp. [T87a] A. G. Thomason,Pseudorandom graphs, Random graphs ’85 (Pozna´ n, 1985), North-Holland Math. Stud., Vol. 144, 307–331, North-Holland, Am- sterdam,

    work page 2018

  4. [15]

    Tikhomirov,On bounded degree graphs with large size-Ramsey numbers, Combinatorica44(2024), 9–14

    [T24] K. Tikhomirov,On bounded degree graphs with large size-Ramsey numbers, Combinatorica44(2024), 9–14. Department of Mathematics, California Institute of Technology Pasadena, CA 91125, USA. E-mail address:dconlon@caltech.edu

    work page 2024

  5. [320]

    Lee and B

    [LS12] C. Lee and B. Sudakov,Dirac’s theorem for random graphs, Random Struc- tures Algorithms41(2012), 293–305. [LPY25+] S. Letzter, A. Pokrovskiy and L. Yepremyan,Size-Ramsey numbers of powers of hypergraph trees and long subdivisions, preprint available at arXiv:2103.01942 [math.CO]. [MP22] S. Mattheus and F. Pavese,A clique-free pseudorandom subgraph ...

    arXiv 2012

  6. [1978]

    Samotij,Stability results for random discrete structures, Random Struc- tures Algorithms44(2014), 269–289

    [S14] W. Samotij,Stability results for random discrete structures, Random Struc- tures Algorithms44(2014), 269–289. [ST15] D. Saxton and A. Thomason,Hypergraph containers, Invent. Math.201 (2015), 925–992. [S16] M. Schacht,Extremal results for discrete random structures,Ann. of Math. 184(2016), 333–365. [SS18] M. Schacht and F. Schulenburg,Sharp threshold...

    work page 2014

  7. [1987]

    [T87b] A. G. Thomason,Random graphs, strongly regular graphs and pseudo- random graphs, Surveys in Combinatorics 1987, London Math. Soc. Lecture Note Ser., Vol. 123, 173–195, Cambridge University Press, Cambridge,

    work page 1987

  8. [1993]

    R¨ odl and A

    16 David Conlon [RR95] V. R¨ odl and A. Ruci´ nski,Threshold functions for Ramsey properties, J. Amer. Math. Soc.8(1995), 917–942. [RS13] V. R¨ odl and M. Schacht,Extremal results in random graphs, Erd˝ os centen- nial, 535–583, Bolyai Soc. Math. Stud., Vol. 25, J´ anos Bolyai Math. Soc., Budapest,

    work page 1995

Show all 15 references
  1. [2005]

    [G07] W. T. Gowers,Hypergraph regularity and the multidimensional Szemer´ edi theorem, Ann. of Math.166(2007), 897–946. [GT08] B. Green and T. Tao,The primes contain arbitrarily long arithmetic pro- gressions, Ann. of Math.167(2008), 481–547. [GNPSST17] L. Gugelmann, R. Nenado...

    2007

  2. [2006]

    Kuperwasser, W

    [KSW25] E. Kuperwasser, W. Samotij and Y. Wigderson,On the Kohayakawa– Kreuter conjecture, Math. Proc. Cambridge Philos. Soc.178(2025), 293–

    2025

  3. [2010]

    Kohayakawa, V

    [KRSS11] Y. Kohayakawa, V. R¨ odl, M. Schacht and E. Szemer´ edi,Sparse partition universal graphs for graphs of bounded degree, Adv. Math.226(2011), 5041–

    2011

  4. [2011]

    K˝ ov´ ari, V

    [KST54] T. K˝ ov´ ari, V. T. S´ os and P. Tur´ an,On a problem of K. Zarankiewicz, Colloq. Math.3(1954), 50–57. [KS06] M. Krivelevich and B. Sudakov,Pseudo-random graphs, More sets, graphs and numbers, Bolyai Soc. Math. Stud., Vol. 15, 199–262, Springer, Berlin,

    1954

  5. [2013]

    Gerke and A

    [GS05] S. Gerke and A. Steger,The sparse regularity lemma and its applications, Surveys in Combinatorics 2005, London Math. Soc. Lecture Note Ser., Vol. 327, 227–258, Cambridge University Press, Cambridge,

    2005

  6. [2014]

    Conlon,A sequence of triangle-free pseudorandom graphs, Combin

    [C17] D. Conlon,A sequence of triangle-free pseudorandom graphs, Combin. Probab. Comput.26(2017), 195–200. [C19] D. Conlon,Graphs with few paths of prescribed length between any two ver- tices,Bull. Lond. Math. Soc.51(2019), 1015–1021. [CFSZ21] D. Conlon, J. Fox, B. Sudakov an...

    2017

  7. [2017]

    Bowtell, R

    [BHH25+] C. Bowtell, R. Hancock and J. Hyde,Proof of the Kohayakawa–Kreuter conjecture for the majority of cases, preprint available at arXiv:2307.16760 [math.CO]. [B15] B. Bukh,Random algebraic construction of extremal graphs, Bull. Lond. Math. Soc.47(2015), 939–945. [BC18] B...

    2015

Pith tools

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