pith. sign in

arxiv: 2607.00732 · v1 · pith:K6BAIFWUnew · submitted 2026-07-01 · 🧮 math.CO

Generalized ErdH{o}s--Rogers problems for r-uniform hypergraphs

Lulu Dai , Qizhong Lin This is my paper

Pith reviewed 2026-07-02 10:53 UTC · model grok-4.3

classification 🧮 math.CO
keywords hypergraphsErdős-Rogers problemsRamsey numbersinduced subgraphshomomorphismstight connectivityshadows
0
0 comments X

The pith

For r-uniform hypergraphs with r at least 3, if G is 2-tightly connected and has no homomorphism to nonempty F, then every G-free n-vertex hypergraph has an induced F-free subgraph on at most C(log n) to the power β_F vertices.

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

The paper proves an upper bound on f_{F,G}(n), the largest m such that any n-vertex G-free r-graph contains an induced F-free subgraph on m vertices. Under the conditions that r is at least 3, F is nonempty, G is 2-tightly connected, and G admits no homomorphism to F, this m is at most C times (log n) raised to β_F, where β_F is the maximum of e(P) over (v(P)-1) for nonempty subhypergraphs P in the 2-shadow of F. This sharpens an earlier exponent that added 1 in the numerator for the r=3 case and recovers a known Ramsey lower bound when F is the complete r-uniform hypergraph on r vertices. A reader cares because the result controls the growth rate of guaranteed induced substructures in forbidden-subgraph problems for hypergraphs.

Core claim

The paper claims that if r ≥ 3, F is nonempty, G is 2-tightly connected, and there is no homomorphism from G to F, then f_{F,G}(n) ≤ C (log n)^{β_F} with β_F equal to the maximum of e(P)/(v(P)-1) over all nonempty P contained in the 2-shadow of F. For r=3 this confirms a conjecture of He and Nie on tightly connected 3-graphs while improving their exponent from (e(P)+1)/(v(P)-1) to the stated β_F. When F equals the complete r-uniform hypergraph K_r^r the bound implies the Ramsey statement that the r-uniform Ramsey number r(G, K_n^r) is at least 2 to the power Omega of n to the 2/r.

What carries the argument

The function f_{F,G}(n) measuring the guaranteed vertex count of an induced F-free subgraph inside any G-free n-vertex r-uniform hypergraph, together with the exponent β_F extracted as the maximum edge-to-(vertex-minus-one) ratio over nonempty pieces of the 2-shadow of F.

If this is right

  • The bound confirms the He-Nie conjecture for r=3 and all 2-tightly connected G.
  • The exponent improves from (e(P)+1)/(v(P)-1) to e(P)/(v(P)-1) for r=3.
  • When F is the complete r-uniform hypergraph on r vertices the result yields the Ramsey lower bound r(G, K_n^r) ≥ 2^Ω(n^{2/r}).
  • The same polylogarithmic control applies uniformly for all r ≥ 3 under the stated connectivity and homomorphism hypotheses.

Where Pith is reading between the lines

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

  • The result suggests that β_F captures the precise growth rate once the homomorphism obstruction is removed.
  • Similar shadow-ratio exponents may govern induced-subgraph problems in other uniformity or connectivity regimes.
  • The bound supplies a concrete obstruction to the existence of large induced F-free subgraphs that can be checked via the 2-shadow of F.

Load-bearing premise

G must be 2-tightly connected and admit no homomorphism to F; without both conditions the stated polylogarithmic upper bound need not hold.

What would settle it

Exhibit a 2-tightly connected G with no homomorphism to a given nonempty F together with a G-free n-vertex r-graph whose largest induced F-free subgraph has size larger than any fixed power of log n.

read the original abstract

Let \(F\) and \(G\) be \(r\)-uniform hypergraphs, and let \(f_{F,G}(n)\) be the largest integer \(m\) such that every \(n\)-vertex \(G\)-free \(r\)-graph contains an induced \(F\)-free subgraph on \(m\) vertices. We prove that, if \(r\ge3\), \(F\) is nonempty, \(G\) is \(2\)-tightly connected, and there is no homomorphism from \(G\) to \(F\), then \[ f_{F,G}(n)\le C(\log n)^{\beta_F}, \qquad \beta_F= \max_{\substack{\emptyset\ne P\subseteq\partial_2F}} \frac{e(P)}{v(P)-1}. \] For \(r=3\), this confirms a conjecture of He and Nie for tightly connected \(3\)-graphs, sharpening their earlier bound by replacing the exponent $ \max_{\substack{\emptyset\ne P\subseteq\partial_2F}} \frac{e(P)+1}{v(P)-1} $ with \(\beta_F\). When \(F=K_r^r\), our result recovers the Ramsey lower bound $r(G,K_n^r)\ge 2^{\Omega(n^{2/r})}$ whenever \(G\) is \(2\)-tightly connected and non-\(r\)-partite.

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

0 major / 2 minor

Summary. The paper studies the generalized Erdős–Rogers function f_{F,G}(n) for r-uniform hypergraphs: the largest m such that every n-vertex G-free r-graph contains an induced F-free subgraph on m vertices. Under the hypotheses r≥3, F nonempty, G 2-tightly connected and with no homomorphism to F, it proves the upper bound f_{F,G}(n) ≤ C (log n)^{β_F} with the explicit exponent β_F = max_{∅≠P⊆∂₂F} e(P)/(v(P)−1). The result sharpens the earlier exponent of He–Nie for r=3 and recovers the known Ramsey lower bound r(G,K_n^r) ≥ 2^{Ω(n^{2/r})} when F = K_r^r.

Significance. If the stated conditional upper bound holds, the work supplies a clean, parameter-free sharpening of the generalized Erdős–Rogers problem that confirms a conjecture for tightly connected 3-graphs and unifies it with classical Ramsey lower bounds. The explicit combinatorial definition of β_F (derived solely from the 2-shadow of F) is a notable strength, as is the recovery of the exponential Ramsey bound from the same argument.

minor comments (2)
  1. [Introduction] The abstract and introduction would benefit from a brief sentence clarifying the precise definition of “2-tightly connected” (currently referenced only by name) before the main theorem statement.
  2. [§2] Notation for the 2-shadow ∂₂F and the auxiliary quantity β_F is introduced in the abstract but should be restated once in §2 before the proof begins.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and accurate summary of the paper, as well as for the recommendation to accept. The report correctly identifies the main result, its sharpening of the He–Nie exponent for r=3, the explicit form of β_F, and the recovery of the classical Ramsey lower bound.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The central result is a conditional upper bound f_{F,G}(n) ≤ C (log n)^{β_F} where β_F is an explicit combinatorial quantity computed solely from the fixed hypergraph F via a maximum over its 2-shadow subhypergraphs. The manuscript supplies a direct proof of this statement under the stated hypotheses (r ≥ 3, F nonempty, G 2-tightly connected and non-homomorphic to F); the exponent sharpens a prior conjecture without any reduction of the claimed bound to a fitted parameter, self-citation chain, or definitional equivalence internal to the paper. When F = K_r^r the argument recovers a known Ramsey lower bound as a special case, confirming consistency rather than circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result is a combinatorial upper-bound theorem whose proof (not visible in the abstract) presumably rests on standard definitions and lemmas of hypergraph theory; no free parameters, invented entities, or ad-hoc axioms are visible in the statement itself.

axioms (1)
  • standard math Standard definitions of r-uniform hypergraphs, induced subgraphs, homomorphisms between hypergraphs, and 2-tight connectivity.
    Invoked throughout the statement of the main theorem in the abstract.

pith-pipeline@v0.9.1-grok · 5789 in / 1424 out tokens · 52637 ms · 2026-07-02T10:53:02.176228+00:00 · methodology

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

17 extracted references · 1 canonical work pages · 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. A29 (1980), 354–360. 9

    1980

  2. [2]

    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

  3. [3]

    Off-diagonal Ramsey numbers

    D. Bradaˇ c, Off-diagonal Ramsey numbers, arXiv preprint arXiv:2605.28793v3, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  4. [4]

    Conlon, J

    D. Conlon, J. Fox, B. Gunby, X. He, D. Mubayi, A. Suk, J. Verstra¨ ete and H.-H. Yu, When are off-diagonal hypergraph Ramsey numbers polynomial?,Proc. Amer. Math. Soc.153 (2025), 4605–4617

    2025

  5. [5]

    Dudek and D

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

    2014

  6. [6]

    Erd˝ os and C

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

    1962

  7. [7]

    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, 20 pp

    2025

  8. [8]

    He and J

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

    2026

  9. [9]

    Janson, New versions of Suen’s correlation inequality,Random Structures Algorithms13 (1998), 467–483

    S. Janson, New versions of Suen’s correlation inequality,Random Structures Algorithms13 (1998), 467–483

    1998

  10. [10]

    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

  11. [11]

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

    1995

  12. [12]

    Mattheus and J

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

    2024

  13. [13]

    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

  14. [14]

    Mubayi and J

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

    2026

  15. [15]

    Nenadov, Counting sparse induced subgraphs in locally dense graphs,European J

    R. Nenadov, Counting sparse induced subgraphs in locally dense graphs,European J. Com- bin.126 (2025), 104125

    2025

  16. [16]

    Sudakov, LargeK r-free subgraphs inK s-free graphs and some other Ramsey-type prob- lems,Random Structures Algorithms26 (2005), 253–265

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

    2005

  17. [17]

    W. C. S. Suen, A correlation inequality and a Poisson limit theorem for nonoverlapping balanced subgraphs of a random graph,Random Structures Algorithms1 (1990), 231–242. 10

    1990