Pith. sign in

REVIEW 2 cited by

For every s ≥ 2, the Erdős–Rogers function satisfies f_s(n) = Θ(√(n log n)), settling its order up to constants.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-01 21:17 UTC pith:565IYPRA

load-bearing objection The main theorem looks right and the construction is original, but the paper must fix an ambiguous citation of Mubayi–Verstraëte before the novelty claim is credible.

arxiv 2607.16118 v1 pith:565IYPRA submitted 2026-07-17 math.CO

On the ErdH{o}s-Rogers function

Robert Morris , Julian Sahasrabudhe , Jacques Verstra\"ete This is my paper
classification math.CO MSC 05C5505C8005C3505D40
keywords Erdős–Rogers functionRamsey theoryK_s-free subgraphsrandom graph constructionclique chromatic numberprobabilistic combinatoricsextremal graph theoryblow-up graphs
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper establishes that the Erdős–Rogers function f_s(n)—the largest K_s-free subset guaranteed in every K_{s+1}-free graph on n vertices—grows as Θ(√(n log n)) for every s ≥ 2. The upper bound comes from an explicit probabilistic construction: a K_{s+1}-free graph in which every set of at least C(s)√(n log n) vertices contains a copy of K_s. This determines the exponent of log n to be exactly 1/2, refuting a conjecture in the literature that the exponent was 1−o(1). The lower bound is not proved here but is imported from a known theorem on clique chromatic numbers. The same construction extends to show that for any K_s-free graph H, the generalised function f_{H,K_s}(n) is O(√(n log n)).

Core claim

The central claim is Theorem 1.1: for every s ≥ 2, f_s(n) = Θ(√(n log n)). The paper proves the upper bound by constructing, for each s and large n, a K_{s+1}-free graph G on n vertices in which every set of at least C(s)√(n log n) vertices spans a copy of K_s. The construction takes two independent random unions of m copies of the balanced complete s-partite graph with ℓ/r vertices, blows each copy up by a factor r, overlays them on the same vertex set, and then deletes edges in two steps: first removing any edge lying in the vertex sets of two different blow-ups, then deleting one edge from every triangle that is not contained in a single blow-up. The resulting graph is K_{s+1}-free. The p

What carries the argument

The key machinery is a random overlay of two r-blow-ups of the balanced complete s-partite graph, followed by two edge-deletion steps. The first deletion removes any edge lying in the vertex sets of at least two random blow-ups; the second deletes one edge from every triangle not contained in a single blow-up, choosing an edge of the minority colour. This produces a K_{s+1}-free graph. The proof tracks 'closed edges'—pairs of vertices connected by a path of length at most two—because an edge can be deleted only if it is closed with respect to either the other colour or earlier-revealed blow-ups. The two central lemmas bound the number of closed edges in any k-set and show that, conditional o

Load-bearing premise

The matching lower bound rests entirely on an external theorem asserting that every graph on n vertices can be vertex-coloured with O(√(n/log n)) colours so that no maximal clique is monochromatic; if that theorem fails, the paper only proves an upper bound and the Θ statement collapses.

What would settle it

For a fixed s (say s=3) and moderately large n, simulate the paper's random construction with the stated parameters and check whether a random k-set of size k = C(s)√(n log n) contains a copy of K_s with probability at least 1 − e^{−Ω(m)}, as Lemma 3.4 predicts. A violation would indicate a flaw in the closed-edge argument. Alternatively, find an infinite family of K_{s+1}-free graphs on n vertices in which the largest K_s-free subset has size o(√(n log n)); such graphs would contradict the claimed lower bound.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • The exponent of log n in f_s(n) is exactly 1/2 for all s ≥ 2, so the function is now determined up to a constant factor; the conjecture that the exponent was 1−o(1) is false.
  • For any K_s-free graph H, the generalised Erdős–Rogers function f_{H,K_s}(n) is O(√(n log n)); when H contains K_{s−1}, it is Θ(√(n log n)).
  • The construction avoids algebraic objects entirely, using only random blow-ups and edge deletions, suggesting a broader template for forcing subgraphs into large sets of F-free graphs.
  • The lower bound's constant is independent of s, while the upper bound's constant is a polynomial in s; the paper sketches an improved constant O(s^{3/2}√(log s)) with more work.
  • A natural barrier of k = Θ(s √(log s) √(n log n)) is identified for constructions of this type, indicating where new ideas would be needed.

Where Pith is reading between the lines

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

  • The closed-edge statistic may be a reusable tool for other graph-removal problems: any deletion rule that only removes edges with a short witness path can be analysed by the same two-lemma structure.
  • The external lower bound is a soft dependency: a self-contained proof of the matching lower bound would make the Θ result internal, and the paper's framework suggests that the clique-chromatic-number theorem might be provable by similar probabilistic blow-up methods.
  • A natural testable extension is to vary the deletion rules (e.g., deleting edges with dependent probabilities) to see whether the √(n log n) threshold is robust or an artifact of the specific two-step deletion.
  • The s-dependence of the upper bound constant is likely not optimal; the paper's own remarks indicate a possible improvement to O(s^{3/2}√(log s)), and one could attempt to push the construction to O(s) or even O(1) by changing the overlay scheme.

Editorial analysis

A structured set of objections, weighed in public.

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

Circularity Check

0 steps flagged

No significant circularity: the upper bound is proved from a first-principles random construction and the lower bound is an imported external theorem.

full rationale

The derivation of Theorem 1.1 is self-contained on the upper-bound side. The graph G is defined in Section 2 from random blow-ups of the Turán graph; Lemma 2.3 derives K_{s+1}-freeness directly from the deletion rules; Lemmas 3.4 and 3.5 are proved via Chernoff bounds, union bounds, and pseudorandom properties of the random family (Lemmas 4.1, 5.2–5.6), with no lemma invoking the target f_s(n) = Θ(√(n log n)). The lower bound is not derived in this paper but imported from Joret–Micek–Reed–Smid [28, Corollary 2], an external published theorem; the paper explicitly credits Huy Pham for pointing it out. The self-citations appearing in the introduction (e.g., [3,10–12,22,26,34,42]) are historical/motivational and none is used in the proof. The only notable issue is the text's description of [36] as having proved f_s(n) ≤ C(s)√(n log n) while simultaneously attributing to [36] the conjecture f_s(n)=√n (log n)^{1−o(1)}; if read literally this is internally inconsistent and raises a novelty/crediting question, but it is not a circularity in the derivation chain. No fitted quantity is relabelled as a prediction, and no uniqueness theorem is imported from the authors' own prior work.

Axiom & Free-Parameter Ledger

5 free parameters · 3 axioms · 0 invented entities

The central claim depends on the cited theorem [28] for the lower bound and on carefully chosen constants for the probabilistic construction; no new physical or mathematical entities are postulated.

free parameters (5)
  • r (blow-up size) = n^{1/8}
    Each vertex of A and B is blown up to an independent set of size r; chosen so that r^3 k/n ≪ 1 in Observation 3.2 and to satisfy inequalities in Section 5.
  • m (number of random copies) = 2^{44} s^3 √n (log n)^{3/2}
    Number of independent copies of J in A and B; set so that m = 16 k log n, giving the final union bound in Theorem 3.1.
  • ℓ (size of blow-up J*) = 2^{-37} s^{-1} r n / log n
    Size of each J* after r-blow-up; chosen so that kℓ/n ≥ 8s log s in Lemma 4.1 and for other estimates.
  • β (closed-edge threshold) = 2^{-7} s^{-2}
    Threshold in event E_β(S); chosen so that β s^2 = 2^{-7} in (16), yielding the e^{-m/12} probability bound.
  • k (target set size) = 2^{40} s^3 √(n log n)
    Standing threshold for cliques; this value appears in (13) and drives the union bound over k-sets.
axioms (3)
  • domain assumption Joret, Micek, Reed and Smid [28, Corollary 2]: every graph on n vertices has a vertex-colouring with O(√(n/log n)) colours such that no maximal clique is monochromatic.
    Used in Section 1 (and abstract) to derive the lower bound f_s(n) ≥ c√(n log n); not proved in this paper.
  • standard math Standard probabilistic inequalities (Chernoff, union bounds, binomial tail bounds) and the random graph model R(n,m,J) defined in Section 2.
    Throughout Sections 3–5.
  • domain assumption The two random partitions U_i and W_i in (10) are independent uniform random partitions of V(G) into sets of size r.
    Independence is essential for Observation 3.2 and Lemma 3.5; the construction assumes this by definition.

pith-pipeline@v1.3.0-alltime-deepseek · 18393 in / 24205 out tokens · 183203 ms · 2026-08-01T21:17:28.560074+00:00 · methodology

0 comments
read the original abstract

We show that the Erd\H{o}s-Rogers function $f_{s,s+1}(n)$ satisfies $$f_{s,s+1}(n) = \Theta( \sqrt{n \log n} )$$ for every $s \ge 2$. More precisely, we construct a $K_{s+1}$-free graph on $n$ vertices in which every set of at least $C(s)\sqrt{n \log n}$ vertices contains a copy of $K_s$ for some constant $C(s)$, which implies the upper bound. The matching lower bound follows from a theorem of Joret, Micek, Reed and Smid on the clique chromatic number of a graph.

discussion (0)

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

Forward citations

Cited by 2 Pith papers

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

  1. Hypergraph Erd\H{o}s--Rogers functions with consecutive clique sizes

    math.CO 2026-07 accept novelty 7.0

    For fixed s≥4, every n-vertex K_{s+1}^{(4)}-free 4-graph has a K_s^{(4)}-free set of size (log n)^{o(1)}, via a new O(log n / log log n) bound for 3-graphs.

  2. Hypergraph Erd\H{o}s--Rogers functions with consecutive clique sizes

    math.CO 2026-07 conditional novelty 7.0

    For every fixed s ≥ 4, f^{(4)}_{s,s+1}(n) = (log n)^{o(1)}, from a new 3-uniform bound f^{(3)}_{s,s+1}(n) = O(log n/log log n).

Reference graph

Works this paper leans on

43 extracted references · 4 linked inside Pith · cited by 1 Pith paper

  1. [1]

    Ajtai, J

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

    1980

  2. [2]

    Alon and V

    N. Alon and V. R¨ odl, Sharp bounds for some multicolour Ramsey numbers,Combinatorica,25(2005), 125–141

    2005

  3. [3]

    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,J. Amer. Math. Soc.,39(2026), 765–780

    2026

  4. [4]

    Balogh, C

    J. Balogh, C. Chen and H. Luo, On the maximumF-free induced subgraphs inK t-free graphs,Random Structures Algorithms,66(2025), e21273

    2025

  5. [5]

    Behrend, On the sets of integers which contain no three in arithmetic progression,Proc

    F.A. Behrend, On the sets of integers which contain no three in arithmetic progression,Proc. Nat. Acad. Sci.,23(1946), 331–332

    1946

  6. [6]

    Bollob´ as and H.R

    B. Bollob´ as and H.R. Hind, Graphs without large triangle-free subgraphs,Discrete Math.,87(1991), 119–131

    1991

  7. [7]

    Bohman, The triangle-free process,Adv

    T. Bohman, The triangle-free process,Adv. Math.,221(2009), 1653–1677

    2009

  8. [8]

    Bohman and P

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

    2021

  9. [9]

    Bradaˇ c, Nearly tight exponents for off-diagonal Ramsey numbers, arXiv:2605.28793

    D. Bradaˇ c, Nearly tight exponents for off-diagonal Ramsey numbers, arXiv:2605.28793

    Pith/arXiv arXiv

  10. [10]

    Campos, S

    M. Campos, S. Griffiths, R. Morris and J. Sahasrabudhe, An exponential improvement for diagonal Ramsey,Ann. Math.,203(2026), 869–932

    2026

  11. [11]

    Campos, M

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

    Pith/arXiv arXiv

  12. [12]

    Campos, M

    M. Campos, M. Jenssen, M. Michelen, F. Pfender and J. Sahasrabudhe, A polynomial improvement for the odd cycle-complete Ramsey numbers, arXiv:2511.10641

    Pith/arXiv arXiv

  13. [13]

    Dudek and D

    A. Dudek and D. Mubayi, On generalized Ramsey numbers for 3-uniform hypergraphs,J. Graph Theory, 76(2014), 217–223

    2014

  14. [14]

    Dudek and V

    A. Dudek and V. R¨ odl, OnKs-free subgraphs inK s+k-free graphs and vertex Folkman numbers,Com- binatorica,31(2011), 39–53

    2011

  15. [15]

    Dudek, T

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

    2014

  16. [16]

    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

    1947

  17. [17]

    Erd˝ os, Graph theory and probability,Canad

    P. Erd˝ os, Graph theory and probability,Canad. J. Math.,11(1959), 34–38

    1959

  18. [18]

    Erd˝ os, Graph theory and probability II,Canad

    P. Erd˝ os, Graph theory and probability II,Canad. J. Math.,13(1961), 346–352

    1961

  19. [19]

    Erd˝ os, P

    P. Erd˝ os, P. Frankl and V. R¨ odl, The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent,Graphs Combin.,2(1986), 113–121

    1986

  20. [20]

    Erd˝ os and C.A

    P. Erd˝ os and C.A. Rogers, The construction of certain graphs,Canad. J. Math.,14(1962), 702–707

    1962

  21. [21]

    Erd˝ os and G

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

    1935

  22. [22]

    Fiz Pontiveros, S

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

    2020

  23. [23]

    Fox and B

    J. Fox and B. Sudakov, Dependent random choice,Random Structures Algorithms,38(2011), 68–99

    2011

  24. [24]

    Gishboliner, O

    L. Gishboliner, O. Janzer and B. Sudakov, Induced subgraphs ofK r-free graphs and the Erd˝ os–Rogers problem,Combinatorica,45(2025), Article 23

    2025

  25. [25]

    Gowers and O

    W.T. Gowers and O. Janzer, Improved bounds for the Erd˝ os–Rogers function,Adv. Combin.,2020 (2020), Paper No. 3, 27pp

    2020

  26. [26]

    Hefty, P

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

    arXiv

  27. [27]

    Janzer and B

    O. Janzer and B. Sudakov, Improved bounds for the Erd˝ os–Rogers (s, s+2)-problem,Random Structures Algorithms,66(2025), e21280

    2025

  28. [28]

    Joret, P

    G. Joret, P. Micek, B. Reed and M. Smid, Tight bounds on the clique chromatic number,Electron. J. Combin.,28(2021), #P3.51

    2021

  29. [29]

    Kim, The Ramsey numberR(3, t) has order of magnitudet 2/logt,Random Structures Algorithms, 7(1995), 173–207

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

    1995

  30. [30]

    Krivelevich,K s-free graphs without largeK r-free subgraphs,Combin

    M. Krivelevich,K s-free graphs without largeK r-free subgraphs,Combin. Probab. Comput.,3(1994), 349–354

    1994

  31. [31]

    Krivelevich, Bounding Ramsey numbers through large deviation inequalities,Random Structures Algorithms,7(1995), 145–155

    M. Krivelevich, Bounding Ramsey numbers through large deviation inequalities,Random Structures Algorithms,7(1995), 145–155

    1995

  32. [32]

    Mattheus and J

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

    2024

  33. [33]

    Molloy, The list chromatic number of graphs with small clique number,J

    M. Molloy, The list chromatic number of graphs with small clique number,J. Combin. Theory Ser. B, 134(2019), 264–284

    2019

  34. [34]

    Morris, Some recent results in Ramsey theory, to appear inProceedings of the International Congress of Mathematicians, Philadelphia, 2026, arXiv:2601.05221

    R. Morris, Some recent results in Ramsey theory, to appear inProceedings of the International Congress of Mathematicians, Philadelphia, 2026, arXiv:2601.05221

    arXiv 2026

  35. [35]

    Mubayi and J

    D. Mubayi and J. Verstra¨ ete, Erd˝ os–Rogers functions for arbitrary pairs of graphs, arXiv:2407.03121

    Pith/arXiv arXiv

  36. [36]

    Mubayi and J

    D. Mubayi and J. Verstra¨ ete, On the order of the classical Erd˝ os–Rogers functions,Bull. London Math. Soc.,57(2025), 582–598

    2025

  37. [37]

    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

    1930

  38. [38]

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

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

    1983

  39. [39]

    Shearer, On the independence number of sparse graphs,Random Structures Algorithms,7(1995), 269–271

    J.B. Shearer, On the independence number of sparse graphs,Random Structures Algorithms,7(1995), 269–271

    1995

  40. [40]

    Sudakov, A new lower bound for a Ramsey-type problem,Combinatorica,25(2005), 487–498

    B. Sudakov, A new lower bound for a Ramsey-type problem,Combinatorica,25(2005), 487–498

    2005

  41. [41]

    Sudakov, LargeK r-free subgraphs inK s-free graphs and some other Ramsey-type problems,Random Structures Algorithms,26(2005), 253–265

    B. Sudakov, LargeK r-free subgraphs inK s-free graphs and some other Ramsey-type problems,Random Structures Algorithms,26(2005), 253–265

    2005

  42. [42]

    Verstra¨ ete, Recent Progress in Ramsey Theory, in: G.O.H

    J. Verstra¨ ete, Recent Progress in Ramsey Theory, in: G.O.H. Katona, B. Patk´ os and C. Tompkins (eds.),Sum(m)it280: Surveys in Extremal Combinatorics and Combinatorial Geometry, Bolyai Society Mathematical Studies, vol. 32, pp. 413–435, Springer, Cham, 2026

    2026

  43. [43]

    Wolfovitz,K 4-free graphs without large induced triangle-free subgraphs,Combinatorica,33(2013), 623–631

    G. Wolfovitz,K 4-free graphs without large induced triangle-free subgraphs,Combinatorica,33(2013), 623–631. IMPA, Estrada Dona Castorina 110, Jardim Botˆanico, Rio de Janeiro, 22460-320, Brasil Email address:rob@impa.br Department of Pure Mathematics and Mathematical Statistics, Wilberforce Road, Cam- bridge, CB3 0W A, UK Email address:jdrs2@cam.ac.uk Dep...

    2013