pith. machine review for the scientific record. sign in

arxiv: 2604.02835 · v2 · submitted 2026-04-03 · 🧮 math.CO

Recognition: no theorem link

A Note on Generalized ErdH{o}s-Rogers Problems

Longma Du , Xinyu Hu , Ruilong Liu , Guanghui Wang
Authors on Pith no claims yet

Pith reviewed 2026-05-13 19:02 UTC · model grok-4.3

classification 🧮 math.CO
keywords generalized Erdős-Rogers functionshypergraph Ramsey numbersstepping-up constructions4-uniform hypergraphsforbidden subhypergraphsRamsey lower bounds
0
0 comments X

The pith

The generalized Erdős-Rogers function for the 4-graph obtained by deleting one edge from K_5 equals (log log N) to the power Theta(1).

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

The paper establishes that f^{(4)}_{5^{-},6}(N) equals (log log N) raised to a constant power Theta(1). This holds for the 4-uniform hypergraph formed by removing one edge from the complete 5-vertex 4-graph. A reader would care because the result nearly resolves the corresponding conjecture for the full complete case and produces new lower bounds on hypergraph Ramsey numbers. The proof starts from a probabilistic 2-coloring of pairs, steps it up to 4-graphs, and tracks multi-layer local extremum structures to control induced subgraphs.

Core claim

We prove that f^{(4)}_{5^{-},6}(N) = (log log N)^{Theta(1)}, where 5^{-} is the 4-graph obtained from K_5^{(4)} by deleting one edge. The proof combines a probabilistic construction of a 2-coloring of pairs with a stepping-up construction and an analysis of multi-layer local extremum structures. This also yields an upper bound for a more general Erdős-Rogers function, which implies the lower bound r_4(6,n) ≥ 2^{2^{c n^{1/2}}}, and a slight improvement on the lower bound for r_k(k+2,n) via a variant of the Erdős-Hajnal stepping-up lemma.

What carries the argument

Stepping-up construction from a probabilistic 2-coloring of pairs together with multi-layer local extremum structures.

If this is right

  • The matching bounds for the one-edge-deleted case support the conjecture that the same asymptotic holds for the full K_5 case.
  • The construction supplies the explicit lower bound r_4(6,n) ≥ 2^{2^{c n^{1/2}}}.
  • A modest improvement follows for the lower bound on r_k(k+2,n) for general k.
  • An upper bound is obtained for a broader family of generalized Erdős-Rogers functions.

Where Pith is reading between the lines

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

  • The same stepping-up analysis may carry over directly to the full K_5 forbidden subgraph.
  • The method could be adapted to produce explicit constructions for other near-complete forbidden hypergraphs at higher uniformity.
  • These Ramsey lower bounds may guide computer searches for large explicit examples in small-N regimes.

Load-bearing premise

The multi-layer local extremum structures arising in the stepping-up construction from the probabilistic 2-coloring behave as analyzed without hidden dependencies on the specific choice of the deleted edge.

What would settle it

A K_6^{(4)}-free 4-graph on N vertices in which some induced subgraph on m vertices with m much larger than (log log N)^C is free of 5^- would falsify the claimed upper bound.

read the original abstract

For a $k$-uniform hypergraph $F$ and positive integers $s$ and $N$, the generalized Erd\H{o}s-Rogers function $f^{(k)}_{F,s}(N)$ denotes the largest integer $m$ such that every $K_s^{(k)}$-free $k$-graph on $N$ vertices contains an $F$-free induced subgraph on $m$ vertices. In particular, if $F = K^{(k)}_t$, then we write $f^{(k)}_{t,s}(N)$ for $f^{(k)}_{F,s}(N)$. Mubayi and Suk (\emph{J. London. Math. Soc. 2018}) conjectured that $f^{(4)}_{5,6}(N)=(\log \log N)^{\Theta(1)}$. Motivated by this conjecture, we prove that $f^{(4)}_{5^{-},6}(N)=(\log\log N)^{\Theta(1)}$, where $5^{-}$ denotes the $4$-graph obtained from $K_5^{(4)}$ by deleting one edge. Our proof combines a probabilistic construction of a $2$-coloring of pairs with a stepping-up construction and an analysis of multi-layer local extremum structures. Furthermore, we derive an upper bound for a more general Erd\H{o}s-Rogers function, which implies the lower bound $r_4(6,n)\ge 2^{2^{cn^{1/2}}}$. By applying a variant of the Erd\H{o}s-Hajnal stepping-up lemma due to Mubayi and Suk, we also slightly improve the lower bound for $r_k(k+2,n)$.

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

2 major / 2 minor

Summary. The paper proves that the generalized Erdős-Rogers function satisfies f^{(4)}_{5^{-},6}(N) = (log log N)^{Theta(1)}, where 5^- denotes K_5^{(4)} minus one edge. The argument combines a probabilistic 2-coloring of pairs, a stepping-up lift to 4-uniform hypergraphs, and an analysis of multi-layer local extremum structures to obtain the matching lower bound; an upper bound on a more general function is also derived, implying r_4(6,n) ≥ 2^{2^{c n^{1/2}}}, together with a modest improvement to lower bounds on r_k(k+2,n) via a variant of the Erdős-Hajnal stepping-up lemma.

Significance. If the asymptotic holds, the result supplies concrete evidence toward the Mubayi-Suk conjecture for the full f^{(4)}_{5,6}(N) by settling the nearly complete case 5^-. The explicit probabilistic construction plus stepping-up yields a matching lower bound of the conjectured order, while the derived Ramsey-number lower bound and the stepping-up variant constitute independent contributions of interest to extremal hypergraph theory.

major comments (2)
  1. [Stepping-up construction and multi-layer analysis] Stepping-up construction and multi-layer analysis: the claim that every multi-layer local extremum structure induced by the lifted coloring is 5^--free beyond size (log log N)^{O(1)} must explicitly rule out new admissible configurations created by the single deleted edge. The argument is stated to be local to the random coloring and the missing edge; a uniform check or explicit enumeration of potential extra configurations (e.g., those using the deleted edge to bypass a forbidden substructure) is required to confirm the exponent remains Theta(1) rather than larger.
  2. [Upper-bound derivation] Upper-bound derivation for the general Erdős-Rogers function: the parameter choices that convert the general upper bound into the concrete Ramsey lower bound r_4(6,n) ≥ 2^{2^{c n^{1/2}}} should be written with explicit constants and the precise dependence on the deleted edge, so that the exponent 1/2 can be verified directly from the equations.
minor comments (2)
  1. [Abstract and introduction] In the abstract and introduction, the notation f^{(4)}_{5^{-},6}(N) and the definition of 5^- should be repeated once for self-contained reading; a short sentence contrasting the new result with the still-open case of the full K_5^{(4)} would help readers.
  2. [Probabilistic construction] Figure captions (if any) and the statement of the probabilistic coloring lemma should include the precise probability space and the range of N for which the (log log N) bound holds.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major point below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Stepping-up construction and multi-layer analysis] Stepping-up construction and multi-layer analysis: the claim that every multi-layer local extremum structure induced by the lifted coloring is 5^--free beyond size (log log N)^{O(1)} must explicitly rule out new admissible configurations created by the single deleted edge. The argument is stated to be local to the random coloring and the missing edge; a uniform check or explicit enumeration of potential extra configurations (e.g., those using the deleted edge to bypass a forbidden substructure) is required to confirm the exponent remains Theta(1) rather than larger.

    Authors: We agree that an explicit enumeration strengthens the argument. The locality claim in the manuscript already ensures that any configuration using the deleted edge reduces to a forbidden substructure in the base random 2-coloring of pairs (which is K_5^{(4)}-free with high probability). In the revision we will add a short paragraph enumerating the finitely many ways the missing edge can appear in a multi-layer local extremum and verifying that each either creates a K_5^{(4)} or remains inside the (log log N)^{O(1)} size bound. This confirms the exponent stays Theta(1). revision: yes

  2. Referee: [Upper-bound derivation] Upper-bound derivation for the general Erdős-Rogers function: the parameter choices that convert the general upper bound into the concrete Ramsey lower bound r_4(6,n) ≥ 2^{2^{c n^{1/2}}} should be written with explicit constants and the precise dependence on the deleted edge, so that the exponent 1/2 can be verified directly from the equations.

    Authors: We will revise the derivation section to display all parameter choices explicitly, including the precise probability adjustment arising from the single deleted edge (a fixed multiplicative factor of 4/5 in the relevant density). The optimization yielding the square-root exponent is unchanged by this constant factor, which is absorbed into the leading constant c. The revised text will contain the full chain of inequalities with numerical placeholders for c so that the exponent 1/2 can be read off directly. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation uses independent probabilistic construction and stepping-up

full rationale

The claimed equality f^{(4)}_{5^{-},6}(N)= (log log N)^{Theta(1)} is obtained from an explicit probabilistic 2-coloring of pairs, lifted via a stepping-up construction, followed by direct analysis of multi-layer local extremum structures in the resulting 4-uniform hypergraph. No equation in the derivation defines a quantity in terms of itself or renames a fitted parameter as a prediction. The upper-bound argument for the general Erdős-Rogers function is logically separate and does not reduce to the lower-bound construction. Citations to Mubayi-Suk supply the motivating conjecture and a standard stepping-up lemma; these are external to the present paper's equations and do not form a self-referential chain. The argument is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard probabilistic method and stepping-up lemmas from the literature; no new free parameters, axioms beyond domain-standard combinatorics, or invented entities are introduced.

axioms (2)
  • domain assumption Probabilistic method yields a 2-coloring of pairs with the required extremal properties
    Invoked to construct the base coloring that is then stepped up.
  • domain assumption Stepping-up lemma lifts 2-colorings to 4-uniform hypergraphs while preserving forbidden-subgraph freeness
    Used to obtain the 4-uniform construction from the pair coloring.

pith-pipeline@v0.9.0 · 5612 in / 1394 out tokens · 61216 ms · 2026-05-13T19:02:32.883076+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 3 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. 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.

  3. 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

49 extracted references · 49 canonical work pages · cited by 2 Pith papers · 1 internal anchor

  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

    work page 1980

  2. [2]

    Ajtai, J

    M. Ajtai, J. Koml´ os, and E. Szemer´ edi, A dense infinite Sidon sequence,European J. Combin.2 (1981), 1–11

    work page 1981

  3. [3]

    Alon and M

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

    work page 1997

  4. [4]

    Balogh, C

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

    work page 2025

  5. [5]

    Bohman and P

    T. Bohman and P. Keevash, The early evolution of theH-free process,Invent. Math.181 (2010), 291–336

    work page 2010

  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

    work page 1991

  7. [7]

    Campos, S

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

    work page

  8. [8]

    Campos, M

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

    work page arXiv 2025

  9. [9]

    F. R. K. Chung and R. L. Graham: Erd˝ os on Graphs: His Legacy of Unsolved Problems, A. K. Peters Ltd., Wellesley, MA, 1998

    work page 1998

  10. [10]

    Conlon, J

    D. Conlon, J. Fox and B. Sudakov, An improved bound for the stepping-up lemma,Discrete Appl. Math.161 (2013), 1191–1196

    work page 2013

  11. [11]

    Conlon, J

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

    work page 2010

  12. [12]

    Conlon, J

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

    work page 2014

  13. [13]

    Conlon, J

    D. Conlon, J. Fox, and B. Sudakov, Recent developments in graph Ramsey theory, inSur- veys in Combinatorics 2015, London Math. Soc. Lecture Note Ser., Cambridge University Press, Cambridge, 2015, pp. 49–118

    work page 2015

  14. [14]

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

    work page arXiv 2026

  15. [15]

    Dudek and D

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

    work page 2014

  16. [16]

    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. 12

    work page 2014

  17. [17]

    Dudek and V

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

    work page 2011

  18. [18]

    Erd˝ os and A

    P. Erd˝ os and A. Hajnal, On Ramsey like theorems, problems and results, Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972), 123–140, Inst. Math. Appl., Southend-on-Sea, 1972

    work page 1972

  19. [19]

    Erd˝ os and H

    P. Erd˝ os and H. Hanani, On a limit theorem in combinatorical analysis,Publ. Math Debrecen 10 (1963), 10–13

    work page 1963

  20. [20]

    Erd˝ os and R

    P. Erd˝ os and R. Rado, Combinatorial theorems on classifications of subsets of a given set, P. London Math. Soc.(3) 2 (1952), 417–439

    work page 1952

  21. [21]

    Erd˝ os and C

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

    work page 1962

  22. [22]

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

    work page arXiv 2024

  23. [23]

    Gishboliner, O

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

    work page 2025

  24. [24]

    W. T. Gowers and O. Janzer, Improved bounds for the Erd˝ os-Rogers function,Adv. Com- bin.3 (2020), 27pp

    work page 2020

  25. [25]

    R. L. Graham, B. L. Rothschild and J. H. Spencer, Ramsey Theory, 2nd edn,Wiley Inter- science Series in Discrete Mathematics and Optimization(Wiley, New York, 1990)

    work page 1990

  26. [26]

    Gupta, N

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

    work page arXiv 2024

  27. [27]

    He and J

    X. He and J. Nie, Generalized Erd˝ os–Rogers problems for hypergraphs,European J. Com- bin.135 (2026), 104372

    work page 2026

  28. [28]

    Hefty, P

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

    work page arXiv 2025

  29. [29]

    Hu and Q

    X. Hu and Q. Lin, Ramsey numbers and a general Erd˝ os-Rogers function,Discrete Math. 347 (2024), 114203

    work page 2024

  30. [30]

    X. Hu, Q. Lin, X. Lu and G. Wang, Phase transitions of the Erd˝ os-Gy´ arf´ as function, arXiv preprintarXiv:2504.05647, 2025

    work page arXiv 2025

  31. [31]

    Hunter, A

    Z. Hunter, A. Milojevi´ c and B. Sudakov, Gaussian random graphs and Ramsey numbers, arXiv preprintarXiv:2512.17718, 2025

    work page arXiv 2025

  32. [32]

    Janzer and B

    O. Janzer and B. Sudakov, Improved bounds for the Erd˝ os-Rogers (s, s+2)-problem,Ran- dom Struct. Algorithms.66 (2025), 5 pp

    work page 2025

  33. [33]

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

    work page 1995

  34. [34]

    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

    work page 1994

  35. [35]

    Krivelevich, Bounding Ramsey numbers through large deviation inequalities,Random Struct

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

    work page 1995

  36. [36]

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

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  37. [37]

    Mattheus and J

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

    work page 2024

  38. [38]

    Morris, Some recent results in Ramsey theory, arXiv preprintarXiv:2601.05221,2026

    R. Morris, Some recent results in Ramsey theory, arXiv preprintarXiv:2601.05221,2026

    work page arXiv 2026

  39. [39]

    Y. Li, C. C. Rousseau, W. Zang, An upper bound for Ramsey numbers,Appl. Math. Lett. 17 (2004), 663–665

    work page 2004

  40. [40]

    Mubayi and A

    D. Mubayi and A. Suk, A survey of hypergraph Ramsey problems,Discrete Mathematics and Applications(eds A. Raigorodskii and M. T. Rassias; Springer, Cham, 2020)

    work page 2020

  41. [41]

    Mubayi and A

    D. Mubayi and A. Suk, New lower bounds for hypergraph Ramsey numbers,Bull. London Math. Soc.50 (2018), 189–201

    work page 2018

  42. [42]

    Mubayi and A

    D. Mubayi and A. Suk, Off-diagonal hypergraph Ramsey numbers,J. Combin. Theory Ser. B125 (2017), 168–177

    work page 2017

  43. [43]

    Mubayi and A

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

    work page 2018

  44. [44]

    Mubayi and J

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

    work page arXiv 2024

  45. [45]

    F. P. Ramsey, On a problem of formal logic,Proc. London Math. Soc.30 (1929), 264–286

    work page 1929

  46. [46]

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

    work page 1983

  47. [47]

    Sudakov, LargeK r-free subgraphs inK s-free graphs and some other Ramsey-type prob- lems,Random Struct

    B. Sudakov, LargeK r-free subgraphs inK s-free graphs and some other Ramsey-type prob- lems,Random Struct. Algorithms.26 (2005), no. 3, 253–265

    work page 2005

  48. [48]

    Sudakov, A new lower bound for a Ramsey-type problem,Combinatorica25 (2005), no

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

    work page 2005

  49. [49]

    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. 14

    work page 2013