{"id":"65e59fc2-1283-4675-bf4c-e7f6292d5a14","arxiv_id":"2608.01525","paper_version":1,"verdict":"UNVERDICTED","confidence":"HIGH","novelty_score":1.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A survey of recent progress and open problems on combinatorial theorems relative to sparse random, pseudorandom, and extremal sets.","lead":"The paper is a survey of how classical combinatorial theorems (Ramsey, Turán, Szemerédi, removal lemmas) behave when the ambient structure is a sparse random, pseudorandom, or extremal set. It summarizes recent advances and lists open problems that could guide future research in extremal combinatorics.","discovery_kind":"review","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.3 omits the required k≥3 restriction and is false for k=2, so the survey's theorem statements are not fully accurate.","rationale":"The paper is an expository survey; its central claim is that it accurately reports recent progress and open problems. The most load-bearing assumption, as the reader notes, is that the cited theorems are stated correctly. I checked the extremal section and found a concrete violation: Theorem 4.3 is false for k=2. This is not an attack on the authors; published theorems often assume k≥3 implicitly, but the survey does not say so. The incidence graph of a projective plane is a standard counterexample, so the check is unambiguous. This is a minor error in the sense that the broader survey remains valuable, but it is a real inaccuracy in a stated theorem. Therefore I recommend a conditional verdict: the survey should be considered accurate only after Theorem 4.3 is corrected to restrict k≥3 (or to exclude k=2). This moves the reader's 'UNVERDICTED' to 'CONDITIONAL' pending that correction.","tokens_in":13570,"tokens_out":22854,"duration_ms":257645,"concrete_test":"Look up the theorem in CFSZ21 (Conlon-Fox-Sudakov-Zhao, J. London Math. Soc. 104 (2021)); if it states 'k≥3', the survey omitted it. Independently, instantiate Theorem 4.3 at k=2 with the incidence graph of PG(2,q): the graph has girth 6 and Θ(n^{3/2}) edges, so the o(n^{3/2}) conclusion fails. This settles whether the statement is accurate as written.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The survey's central value is reliable statements of external theorems. Theorem 4.3 states: 'Every k-uniform hypergraph on n vertices of girth greater than 5 has o(n^{3/2}) edges.' As written this includes k=2, i.e., graphs. But the incidence graph of a projective plane of order q has n=2(q^2+q+1) vertices, (q+1)(q^2+q+1)=Θ(n^{3/2}) edges, and girth 6. Hence it is a 2-uniform hypergraph with girth >5 whose edge count is not o(n^{3/2}). The theorem is therefore false unless restricted to k≥3 (the likely original statement). This is exactly the kind of misstated hypothesis that would mislead a reader applying the survey's results. The rest of the survey is not affected, but this theorem statement needs a correction.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":13801,"tokens_out":12556,"duration_ms":123174,"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":[{"comment":"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.","section":"Theorem 4.3"}],"minor_comments":[{"comment":"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.","section":"Theorem 2.8"},{"comment":"Typo: 'who may ask' should be 'one may ask'.","section":"Section 3"},{"comment":"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.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"This is a survey by a leading expert, and I do not see circularity or internal inconsistency beyond the flagged theorem statement. My recommendation of major revision is driven by the fact that the survey's value lies precisely in the fidelity of its quoted results; the k=2 counterexample to Theorem 4.3 suggests that all displayed statements should be checked against their sources before acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is exactly what it says it is: a survey, not a research announcement. That's fine. It does its job well, collecting the recent progress on combinatorial theorems relative to random, pseudorandom, and extremal sets, with a good list of open problems. The attributions look right to me, and the author has no obligation to prove everything from scratch in a survey. The section on C4-free graphs and Sidon sets is a nice distillation of work that is otherwise scattered across several papers. If you want a quick entry point into this area, this is probably the best current one. The soft spots are real but localized. The stress-test note lands: Theorem 4.3 states that every k-uniform hypergraph on n vertices of girth greater than 5 has o(n^{3/2}) edges. As written, that includes k=2, and it's false for k=2: the incidence graph of a projective plane of order q has girth 6 and Θ(n^{3/2}) edges. The theorem needs the restriction k≥3 (which is presumably the original statement). There is also a typo in Theorem 2.8 where the colouring is said to be of G_{n,p} rather than G_{N,p}. These errors matter because the survey's value lies in reliable statements of external theorems. They don't undermine the rest of the survey, but they should be fixed before the paper is used as a reference. One more minor point: the paper lists several prior surveys and doesn't claim comprehensive coverage, so the low novelty score is not a criticism. A survey can be useful without containing new theorems. I'd recommend engaging with this through regular peer review rather than desk rejection. The errors are easily correctable, and the field would benefit from having a careful, up-to-date survey available. I'd bring it to a reading group, and I'd cite it in my own writing on extremal combinatorics. If I were refereeing, I'd ask for the two fixes and then accept.","headline":"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.","tokens_in":668,"tokens_out":859,"would_cite":true,"duration_ms":22195,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05C55","05C35","05D10","05D40","11B30"],"pacs":[],"model":"deepseek-v4-flash","headline":"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","keywords":["sparse random graphs","Ramsey theory","Turán property","removal lemma","pseudorandom graphs","Szemerédi theorem","Sidon sets","combinatorial transference"],"falsifier":"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$.","tokens_in":13497,"feed_emoji":"🧩","tokens_out":11949,"duration_ms":90477,"temperature":0.7,"pith_summary":"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.","feed_headline":"One graph parameter sets the thresholds for Ramsey, Turán, and removal","feed_subtitle":"The same threshold exponent governs random, pseudorandom, and extremal sparse settings; remaining gaps are listed.","key_machinery":"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.","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the 0-statement and 1-statement of the random Ramsey theorem, the benchmark for all later sparse-set transfer results.","marker":"[RR93, RR95]"},{"why":"Develops the transference method for sparse random sets, proving the Turán property and removal lemmas down to the $m_2(H)$ threshold.","marker":"[CG16]"},{"why":"Independently proves the same transfer theorems for random sets, giving a second method.","marker":"[S16]"},{"why":"Introduces the hypergraph container method, another route to these thresholds and a resolution of the KLR conjecture.","marker":"[BMS15]"},{"why":"Independently establishes hypergraph containers, extending the approach.","marker":"[ST15]"},{"why":"Introduces densification for pseudorandom graphs, proving removal and Ramsey analogues for jumbled graphs.","marker":"[CFZ14a]"},{"why":"Proves removal lemmas relative to $C_4$-free graphs, yielding the hypergraph girth and Sidon-set corollaries.","marker":"[CFSZ21]"},{"why":"Establishes the Green–Tao theorem on primes in arithmetic progression, the motivating target for relative Szemerédi theorems under pseudorandomness.","marker":"[GT08]"}],"fun_headline_variants":["One graph invariant sets Ramsey, Turán, removal thresholds","One exponent drives thresholds for Ramsey, Turán, removal","Ramsey, Turán, removal: same graph parameter sets threshold","Same critical exponent underpins sparse Ramsey, Turán, removal","One graph parameter dictates sparse Ramsey, Turán, removal thresholds"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["One graph invariant sets Ramsey, Turán, removal thresholds","One exponent drives thresholds for Ramsey, Turán, removal","Ramsey, Turán, removal: same graph parameter sets threshold","Same critical exponent underpins sparse Ramsey, Turán, removal","One graph parameter dictates sparse Ramsey, Turán, removal thresholds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000631,"raw_usage":{"total_tokens":2668,"prompt_tokens":578,"completion_tokens":2090,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":322,"completion_tokens_details":{"reasoning_tokens":2005}},"tokens_in":322,"tokens_out":2090,"duration_ms":14877,"temperature":1.0,"reasoning_tokens":2005,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T00:02:44.545635+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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$.","supporting_citations":[],"review_version":1}