Pith. sign in

REVIEW 5 minor 36 references

This paper proves that for every fixed s≥4, the 4-uniform Erdős–Rogers function f^{(4)}_{s,s+1}(n) is (log n)^{o(1)}, resolving a problem from the literature.

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-02 07:25 UTC pith:7XF5XFYZ

load-bearing objection Resolves the Conlon–Fox–Sudakov 4-uniform problem with a subpower bound via a new 3-uniform log/log-log estimate; the main proofs are sound and the only caveat is an external lemma for the higher-uniform corollary.

arxiv 2607.10111 v2 pith:7XF5XFYZ submitted 2026-07-11 math.CO

Hypergraph ErdH{o}s--Rogers functions with consecutive clique sizes

Qizhong Lin , Lin Niu This is my paper
classification math.CO MSC 05C6505C5505D40
keywords Erdős–Rogers functionhypergraph Ramsey theoryhypergraph containersstepping-up constructionclique-free induced subgraphsprobabilistic method3-uniform hypergraphs4-uniform hypergraphs
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 Erdős–Rogers function f^{(k)}_{s,t}(n) measures the largest guaranteed size of a vertex set that spans no K_s^{(k)} inside any n-vertex K_t^{(k)}-free k-uniform hypergraph. The paper proves that for every fixed s≥4, f^{(4)}_{s,s+1}(n) ≤ exp(O(log log n / log log log n)), which is (log n)^{o(1)}; this settles the 4-uniform problem posed in the earlier literature. The engine is a new 3-uniform estimate: f^{(3)}_{s,s+1}(n) ≤ C_s log n / log log n, improving the previous logarithmic upper bound by a factor of log log n. The proof builds a random 3-graph by coloring pairs with a robust clique-free palette, encodes local bad colorings as independent sets of an auxiliary hypergraph, and counts them with hypergraph containers. A monotone stepping-up argument then lifts the 3-uniform bound to 4-uniformity, and known recursions push it to higher uniformities.

Core claim

The central claim is that, for every fixed s≥4, the 4-uniform Erdős–Rogers function f^{(4)}_{s,s+1}(n) is bounded by exp(O(log log n / log log log n)), hence is (log n)^{o(1)}. This means one can construct n-vertex 4-uniform hypergraphs with no K_{s+1}^{(4)} in which every K_s^{(4)}-free set has size at most that quantity. The key input is a new 3-uniform bound: f^{(3)}_{s,s+1}(n) ≤ C_s log n / log log n for every fixed s≥3. A further consequence is that for every fixed k≥5, f^{(k)}_{k+1,k+2}(n) = (log_{(k-3)} n)^{o(1)}, bringing the problem within one logarithmic iteration of the iterated-logarithm scale conjectured in the literature.

What carries the argument

The proof combines three mechanisms. First, a robust auxiliary palette: a K_s-free graph F on q vertices such that every collection of at most s−1 sufficiently large vertex subsets contains a transversal clique; this palette is used to color pairs of a base set randomly, producing a 3-graph that is K_{s+1}^{(3)}-free by construction. Second, an auxiliary hypergraph Γ whose vertices are pairs (pair, color) and whose edges encode admissible color patterns that would force a K_s^{(3)}; a local coloring yields a K_s^{(3)}-free 3-graph exactly when its vertex set is independent in Γ. Third, a recursive application of a standard hypergraph container lemma counts the terminal containers and shows t

Load-bearing premise

The argument needs a standard hypergraph container lemma to apply at every recursive step to the auxiliary hypergraph, which requires a specific numerical balance between the palette size and the codegrees; the choice a = 1/(10h) leaves a margin of t^{-4/5}, and if that balance failed, the terminal container family would grow too large and the exponential saving over bad local colorings would disappear.

What would settle it

Enumerate, for a small concrete case such as s=3 and t around a few hundred, the number of local pair-colorings that produce a K_3^{(3)}-free 3-graph. If that count is not at most q^{(1−η)m} with η>0, or if the auxiliary palette F cannot be built with the claimed robust transversal property at q = t^a, then Lemma 3.5 fails and the main theorem collapses.

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

If this is right

  • For every fixed s≥4, the 4-uniform Erdős–Rogers function f^{(4)}_{s,s+1}(n) is (log n)^{o(1)}, resolving the open 4-uniform problem.
  • The new 3-uniform estimate f^{(3)}_{s,s+1}(n) ≤ C_s log n / log log n improves the previous logarithmic upper bound by a factor of log log n.
  • For every fixed k≥5, f^{(k)}_{k+1,k+2}(n) ≤ exp(O_k(log_{(k-2)} n / log_{(k-1)} n)) = (log_{(k-3)} n)^{o(1)}, putting the iterated-logarithm conjecture within one logarithmic iteration.
  • In the case s=3, the 3-uniform estimate yields the inverse Ramsey bound r(K_4^{(3)}, K_m^{(3)}) ≥ 2^{Ω(m log m)}.

Where Pith is reading between the lines

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

  • Editorial inference: the same palette-and-container counting strategy may extend to non-adjacent clique sizes t ≥ s+2, where the scales and local configuration hypergraphs change; the paper does not claim this extension.
  • Editorial inference: the exponential loss in the monotone stepping-up lemma suggests that a direct 4-uniform construction would be needed to reach the (log log n)^{O(1)} scale, which is a natural next target.
  • Editorial inference: if the q^{o(m)} factor in the container count could be removed or sharpened, the 3-uniform bound might yield better explicit constants or a stronger sub-logarithmic estimate.
  • Editorial inference: the robust-clique palette construction is likely reusable as a general tool for other hypergraph Ramsey-type counting problems, though no such reuse is explored here.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 5 minor

Summary. The paper studies the hypergraph Erdős–Rogers function f^{(k)}_{s,t}. The main results are: (i) Theorem 1.3, f^{(3)}_{s,s+1}(n) ≤ C_s log n / log log n for every fixed s ≥ 3; (ii) Theorem 1.5, f^{(4)}_{s,s+1}(n) ≤ exp(C_s log log n / log log log n) for every fixed s ≥ 4, which resolves Problem 1.1 of Conlon–Fox–Sudakov; and (iii) Corollary 1.6, f^{(k)}_{k+1,k+2}(n) ≤ exp(C_k log_{(k-2)} n / log_{(k-1)} n) for every fixed k ≥ 5. The 3-uniform proof constructs a random pair-coloring using a K_s-free palette graph F, encodes K_s-free local colorings as independent sets in an auxiliary h-graph Γ, and counts them via recursive hypergraph containers. The 4-uniform result is obtained from the 3-uniform one by a monotone stepping-up construction over binary sequences using δ-chains.

Significance. If correct, Theorem 1.5 is a substantial advance: it gives the first general subpower-in-log n upper bound for f^{(4)}_{s,s+1}(n), resolving a problem stated by Conlon, Fox and Sudakov. Theorem 1.3 also improves the logarithmic Dudek–Mubayi bound by a log log n factor. I checked the load-bearing steps in detail: the probabilistic construction of the palette graph in Lemma 3.1, the co-degree bound in Lemma 3.4, the container applicability calculation in Section 3.4 Step 1 (the exponent a(h+ℓ−1)−1 ≤ −(8h+1)/(10h) < −4/5 gives the required margin), the recursive container count |C| = q^{o(m)}, and the δ-chain/Erdős–Szekeres argument in Lemma 4.3. These all cohere, and the proof of the main theorem is essentially self-contained apart from standard external tools. The main caveat is Corollary 1.6, which depends on Lemma 4.4 imported from [19]; this does not affect the resolution of Problem 1.1.

minor comments (5)
  1. [Section 3.4, Step 2] The bound e(Γ)/(ζt^s) ≤ q^h/ζ drops a factor of 1/s! from (t choose s)/t^s. The resulting O(log q) number of refinement steps is unaffected, but the displayed inequality should be corrected or qualified with an absolute constant.
  2. [Section 4.3, proof of Corollary 1.6] The sentence 'iterating the second inequality in Lemma 4.4 k−5 times and then applying the first inequality once' states the order of application backwards: the first (4→5) inequality must be used before iterating the second. The displayed final bound is correct, but the sentence should be rephrased. Also, the monotonicity step used to pass from 2^{n_i} to n_{i−1} is implicit and should be stated explicitly.
  3. [Lemma 4.2] The induction uses a monotonicity property of binomial coefficients (that binom(x+y, x) increases under the componentwise bounds x ≤ I(A)−1, y ≤ D(A), and x ≤ I(A), y ≤ D(A)−1) that is not stated. The step is valid, but a one-sentence justification would improve readability.
  4. [Section 4.3, Lemma 4.4] Corollary 1.6 is entirely contingent on Lemma 4.4, which is quoted from [19] without proof. If [19] is not yet published, the authors should either provide a proof or clearly flag the dependence. This does not affect Theorems 1.3 and 1.5.
  5. [Throughout] There are minor typographical and formatting issues, including inconsistent superscript notation for hypergraph cliques (e.g., K_s^3 vs K_s^{(3)}) and some OCR artefacts in the header. These should be cleaned up.

Circularity Check

0 steps flagged

No circularity: the main 3-uniform and 4-uniform bounds are derived self-containedly; the only self-citation, Lemma 4.4 from [19], is an independent stepping-up recursion used only for Corollary 1.6 and is not load-bearing for the resolution of Problem 1.1.

full rationale

I walked the proof chain. Theorem 1.3 is built from a random palette graph F (Lemma 3.1), a random pair-coloring G_chi, the auxiliary hypergraph Gamma whose independent sets encode K_s^{(3)}-free local colorings (Lemma 3.3), and a recursive application of the hypergraph container theorem (Lemma 2.3). In Lemma 3.5, Step 1, the container applicability condition is checked explicitly: for e(Gamma[C]) >= zeta t^s, the average degree satisfies d(H) >= c t^{s-2}/q, and Lemma 3.4 gives Delta_l(H)/(d(H) tau^{l-1}) <= C t^{a(h+l-1)-1} = O(t^{-4/5}) with tau = t^{-2a}. Thus Lemma 2.3 applies. The recursive container count gives |C| = q^{o(m)}, Claim 3.6 yields the q^{-eta m} saving, and the final expectation calculation is < 1, forcing alpha_s(G_chi) < t and hence f^{(3)}_{s,s+1}(n) <= C log n / log log n. No parameter is fitted to the target result; the constants are chosen a priori and the asymptotic savings are derived. Theorem 1.5 follows from the in-paper monotone stepping-up Lemma 4.3, using Theorem 1.3 with s-1 as the input; again the reduction is explicit and self-contained. The only overlap with the authors' own prior work is Lemma 4.4 of [19] (Lin is a co-author), used solely in Corollary 1.6. That lemma is a separate, previously stated stepping-up recursion and is not equivalent to the corollary being proved; it is also not used in the proof of Theorem 1.5 or in the resolution of Problem 1.1. The omission of a proof of Lemma 4.4 is a citation dependency, not a circular step. Therefore the central derivation is self-contained and there is no circularity to report.

Axiom & Free-Parameter Ledger

5 free parameters · 5 axioms · 0 invented entities

The free parameters are fixed functions of s (proof-design constants), not empirical fits; the bounds hold for all large n. The auxiliary palette F and auxiliary hypergraph Γ are internal proof constructions, not physically posited entities.

free parameters (5)
  • a = 1/(10h)
    Exponent of the palette size q = Θ(t^a); chosen so the container co-degree condition holds with margin t^{-4/5} (Section 3.4, Step 1).
  • ρ = 1/(2(s-1))
    Supersaturation margin in Claim 3.6; fixed fraction of pairs forced to be small in each terminal container.
  • λ = 1/(4s)
    Threshold exponent for 'large' lists L_xy in the robust palette lemma; balances Lemma 3.1's transversal property with the product count.
  • η = λρ/2
    Saving exponent in Lemma 3.5; absorbs the q^{o(m)} container factor into the q^{-ηm} bound.
  • τ = t^{-2a}
    Container theorem parameter; set to make m q τ log t log q = o(m log q).
axioms (5)
  • standard math Janson's inequality for transversal cliques (Lemma 2.1)
    Used to guarantee transversal K_ℓ in random palette graph; proved in Section 2.
  • standard math Erdős–Simonovits supersaturation for complete graphs (Lemma 2.2)
    Used in Claim 3.6 to get κt^s K_s-copies from a graph with e ≥ (1-ρ)m edges.
  • standard math Hypergraph container theorem (Lemma 2.3, Balogh–Morris–Samotij; Saxton–Thomason)
    Used recursively in Section 3.4 to cover independent sets of Γ by few terminal containers; the paper derives the stated form from [35, Cor. 3.6].
  • domain assumption Stepping-up recursions of Fan, Hu, Lin and Lu (Lemma 4.4)
    Cited from arXiv:2410.22019, used only in Corollary 1.6; not proved in this paper and co-authored by one of the present authors.
  • domain assumption Monotonicity of f^{(k)}_{s,t} under induced subgraphs
    Used implicitly in Theorems 1.5 and Corollary 1.6 to pass from 2^{n_i} to n_{i-1} vertices; standard and stated in Section 4.3.

pith-pipeline@v1.3.0-alltime-deepseek · 16628 in / 40789 out tokens · 350751 ms · 2026-08-02T07:25:26.230704+00:00 · methodology

0 comments
read the original abstract

For integers \(k\le s<t\), the hypergraph Erd\H{o}s--Rogers function \(f^{(k)}_{s,t}(n)\) is the largest integer \(m\) such that every \(n\)-vertex \(K_t^{(k)}\)-free \(k\)-graph contains a set of \(m\) vertices spanning no copy of \(K_s^{(k)}\). We prove that, for every fixed \(s\ge4\), \[ f^{(4)}_{s,s+1}(n)=(\log n)^{o(1)}, \] thereby resolving a problem posed by Conlon, Fox and Sudakov. The key input is a new \(3\)-uniform estimate: for every fixed \(s\ge3\), \(f^{(3)}_{s,s+1}(n)=O(\frac{\log n}{\log\log n})\), which improves the logarithmic upper bound of Dudek and Mubayi. The proof develops a probabilistic pair-coloring construction based on a robust auxiliary palette and hypergraph containers. As a further consequence, we obtain \(f^{(k)}_{k+1,k+2}(n)=(\log_{(k-3)} n)^{o(1)}\) for every fixed \(k\ge5\), making substantial progress towards a conjecture of Mubayi and Suk.

Review history (2 revisions) →

discussion (0)

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

Reference graph

Works this paper leans on

36 extracted references · 6 linked inside Pith

  1. [1]

    Ajtai, J

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

    1980

  2. [2]

    Alon and M

    N. Alon and M. Krivelevich, Constructive bounds for a Ramsey-type problem,Graphs Combin. 13 (1997), 217–225

    1997

  3. [3]

    Alon and J

    N. Alon and J. H. Spencer,The Probabilistic Method, 4th ed., Wiley, Hoboken, 2016

    2016

  4. [4]

    Balogh, C

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

    2025

  5. [5]

    Balogh, R

    J. Balogh, R. Morris and W. Samotij, Independent sets in hypergraphs,J. Amer. Math. Soc. 28 (2015), 669–709

    2015

  6. [6]

    Bollob´ as and H

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

    1991

  7. [7]

    Conlon, J

    D. Conlon, J. Fox and B. Sudakov, Hypergraph Ramsey numbers,J. Amer. Math. Soc.23 (2010), 247–266

    2010

  8. [8]

    Conlon, J

    D. Conlon, J. Fox and B. Sudakov, Short proofs of some extremal results,Combin. Probab. Comput.23 (2014), 8–28

    2014

  9. [9]

    Conlon, J

    D. Conlon, J. Fox and B. Sudakov, Recent developments in graph Ramsey theory, inSurveys in Combinatorics 2015, London Math. Soc. Lecture Note Ser. 424, Cambridge Univ. Press, Cambridge, 2015, 49–118

    2015

  10. [10]

    Dai and Q

    L. Dai and Q. Lin, Generalized Erd˝ os–Rogers problems forr-uniform hypergraphs, arXiv:2607.00732, 2026

    Pith/arXiv arXiv 2026

  11. [11]

    L. Du, X. Hu, R. Liu and G. Wang, A double-exponential lower bound forr 4(5, n), arXiv:2604.23986, 2026

    Pith/arXiv arXiv 2026

  12. [12]

    L. Du, X. Hu, R. Liu and G. Wang, A note on generalized Erd˝ os–Rogers problems, arXiv:2604.02835, 2026

    Pith/arXiv arXiv 2026

  13. [13]

    L. Du, X. Hu, R. Liu and G. Wang, A step towards the Erd˝ os–Rogers problem, arXiv:2603.12610, 2026. 18

    arXiv 2026

  14. [14]

    Dudek and D

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

    2014

  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. B109 (2014), 213–227

    2014

  16. [16]

    Dudek and V

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

    2011

  17. [17]

    Erd˝ os and C

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

    1962

  18. [18]

    Erd˝ os and M

    P. Erd˝ os and M. Simonovits, A limit theorem in graph theory,Studia Sci. Math. Hungar.1 (1966), 51–57

    1966

  19. [19]

    C. Fan, X. Hu, Q. Lin and X. Lu, New bounds of two hypergraph Ramsey problems, arXiv:2410.22019, 2024

    Pith/arXiv arXiv 2024

  20. [20]

    C. Fan, M. Li, Q. Lin and B. Ning, An improved double-exponential lower bound forr 4(5, n), arXiv:2605.04105v2, 2026

    Pith/arXiv arXiv 2026

  21. [21]

    Gishboliner, O

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

    2025

  22. [22]

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

    2020

  23. [23]

    R. L. Graham, B. L. Rothschild and J. H. Spencer,Ramsey Theory, 2nd ed., Wiley, New York, 1990

    1990

  24. [24]

    He and J

    X. He and J. Nie, Generalized Erd˝ os–Rogers problems for hypergraphs,European J. Combin. 135 (2026), Paper No. 104372, 9 pp

    2026

  25. [25]

    Janson, T

    S. Janson, T. Luczak and A. Ruci´ nski,Random Graphs, Wiley, New York, 2000

    2000

  26. [26]

    Janzer and B

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

    2025

  27. [27]

    Joret, P

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

    2021

  28. [28]

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

    1995

  29. [29]

    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

  30. [30]

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

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

    1995

  31. [31]

    Morris, J

    R. Morris, J. Sahasrabudhe and J. Verstra¨ ete, On the Erd˝ os–Rogers function, arXiv:2607.16118, 2026

    Pith/arXiv arXiv 2026

  32. [32]

    Mubayi and A

    D. Mubayi and A. Suk, Constructions in Ramsey theory,J. London Math. Soc.97 (2018), 247–257. 19

    2018

  33. [33]

    Mubayi and J

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

    2025

  34. [34]

    Mubayi and J

    D. Mubayi and J. Verstra¨ ete, Erd˝ os–Rogers functions for arbitrary pairs of graphs,Random Structures Algorithms(2026), e70078

    2026

  35. [35]

    Saxton and A

    D. Saxton and A. Thomason, Hypergraph containers,Invent. Math.201 (2015), 925–992

    2015

  36. [36]

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

    G. Wolfovitz,K 4-free graphs without large induced triangle-free subgraphs,Combinatorica33 (2013), 623–631. 20

    2013