pith. sign in

arxiv: 2604.05288 · v2 · submitted 2026-04-07 · 🧮 math.CO

Induced rational exponents near two

Tao Jiang , Sean Longbrake This is my paper

Pith reviewed 2026-05-10 20:06 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C35
keywords extremal graph theoryinduced subgraphsrational exponentsbipartite graphsforbidden subgraphsK_{s,s}-free graphs
0
0 comments X

The pith

For rationals r=2-a/b with b at least max of a and (a-1)^2, there exists bipartite H making ex*(n,H,s) equal to Theta(n^r) for large s.

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

This paper proves that the Dong-Gao-Li-Liu conjecture holds for all rationals r of the form 2 minus a over b where the denominator b is at least the maximum of a and (a-1) squared. The conjecture asserts that for every rational between 1 and 2, some bipartite graph H and large enough s exist so that the maximum edges in an n-vertex graph without a K_{s,s} or an induced copy of H grows like n to the power r. Establishing the result for these particular r shows that the induced version of the extremal problem can produce exactly the same polynomial growth rates as the ordinary extremal function. A sympathetic reader would care because the work supplies concrete infinite families of exponents near 2 that are achievable when an induced subgraph is forbidden, thereby supporting the broader claim that induced and non-induced extremal numbers often share the same order of magnitude.

Core claim

We prove that the latter conjecture holds for all rationals r=2-a/b, where a,b in natural numbers satisfy b greater than or equal to max of a and (a-1) squared. Our result extends a well-known result of Conlon and Janzer to the induced setting and adds more evidence to support the former conjecture.

What carries the argument

The ex*(n,H,s) function, which counts the maximum edges in an n-vertex graph that is K_{s,s}-free and contains no induced copy of a fixed bipartite graph H; the proof supplies an explicit construction of H for each admissible r and a counting argument that closes exactly when the denominator b meets the stated size condition.

If this is right

  • ex*(n,H,s) is Theta(n^r) for the constructed H and every s at least some fixed s0.
  • The same order of magnitude is achieved in the induced setting as in the ordinary extremal problem for these exponents.
  • The result holds uniformly once s is large enough, independent of n.
  • This supplies an infinite family of rationals near 2 that realize the conjectured growth rates.

Where Pith is reading between the lines

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

  • If the required lower bound on b can be relaxed by a different construction, the same approach might cover additional rationals closer to 1.
  • The technique may adapt to study how induced forbidden subgraphs affect extremal numbers in other ranges of exponents.
  • Direct verification of the edge counts for the smallest admissible a and b on moderate n could confirm the leading constants in the Theta notation.
  • Tighter comparisons between induced and non-induced versions of the same forbidden subgraph might hold for these parameter choices.

Load-bearing premise

The counting argument that bounds the number of edges succeeds without extra terms only when the denominator b is at least the maximum of a and (a-1) squared.

What would settle it

An explicit computation or construction for some a and b meeting the size condition on b that shows the maximum number of edges grows faster or slower than n to the power r for all large n.

read the original abstract

Given a bipartite graph $H$ and a natural number $s$, let $\mathrm{ex}^*(n,H,s)$ denote the maximum number of edges in an $n$-vertex graph that contains neither $K_{s,s}$ nor an induced copy of $H$. Hunter, Milojevi\'c, Sudakov, and Tomon conjectured that $\mathrm{ex}^*(n,H,s)=O_{H,s}(\mathrm{ex}(n,H))$ whenever $H$ is connected. Motivated by this conjecture and the rational exponents conjecture, Dong, Gao, Li, and Liu conjectured that for every rational $r\in (1,2)$ there is a bipartite graph $H$ and an $s_0$ such that $\mathrm{ex}^*(n,H,s)=\Theta(n^r)$ for all $s\geq s_0$. We prove that the latter conjecture holds for all rationals $r=2-a/b$, where $a,b\in\mathbb{N}$ satisfy $b\geq \max\{a,(a-1)^2\}$. Our result extends a well-known result of Conlon and Janzer to the induced setting and adds more evidence to support the former conjecture.

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 manuscript proves that the Dong-Gao-Li-Liu conjecture holds for every rational r = 2 - a/b (a, b natural numbers) satisfying b ≥ max{a, (a-1)^2}. For each such r there exists a bipartite graph H and an integer s0 such that ex^*(n, H, s) = Θ(n^r) for all s ≥ s0. The argument extends the Conlon-Janzer theorem by constructing an appropriate H and verifying that the induced-forbidden-subgraph condition is compatible with the extremal count under the stated arithmetic restriction on the denominator.

Significance. If correct, the result supplies an explicit infinite family of rational exponents in (1, 2) for which the induced extremal function realizes the conjectured Θ(n^r) growth rate. By concentrating on exponents near 2 it complements existing constructions for smaller r and supplies concrete support for the Hunter-Milojević-Sudakov-Tomon conjecture that ex^*(n, H, s) = O_{H,s}(ex(n, H)) whenever H is connected and bipartite. The transparent arithmetic condition on b makes the range of validity precise and falsifiable.

minor comments (2)
  1. The definition of the auxiliary graph H in §3 should include an explicit statement of the vertex partition sizes used in the random blow-up; this would make the subsequent counting argument easier to follow without consulting the Conlon-Janzer reference.
  2. In the proof of the lower bound (around the display following Lemma 4.2), the phrase 'sufficiently large n' appears without an explicit dependence on a and b; adding a sentence that records the threshold in terms of the parameters would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and for recommending acceptance. The report accurately summarizes the main result and its relation to the Dong-Gao-Li-Liu and Hunter-Milojević-Sudakov-Tomon conjectures.

Circularity Check

0 steps flagged

No significant circularity; result is an extension of an independent prior theorem

full rationale

The paper proves the Dong-Gao-Li-Liu conjecture for rationals r=2-a/b under the explicit arithmetic condition b ≥ max{a,(a-1)^2}. This is presented as a direct extension of the Conlon-Janzer theorem (an external, non-self-cited result) to the induced setting. The abstract and stated theorem contain no equations that reduce the new bound to a fitted parameter, self-definition, or load-bearing self-citation chain. The limitation on b is framed as the regime where the construction and counting arguments close, not as a circular fit. No self-definitional, fitted-prediction, or ansatz-smuggling patterns appear in the provided claims.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The argument rests on the standard definitions of ex(n,H) and ex*(n,H,s) together with the known Conlon-Janzer theorem; no free parameters, ad-hoc axioms, or new entities are introduced in the abstract.

axioms (2)
  • standard math Standard definitions of the extremal function ex(n,H) and the induced variant ex*(n,H,s) for bipartite H and integer s.
    These are the objects whose asymptotic growth is bounded in the statement.
  • domain assumption The Conlon-Janzer theorem on rational exponents for ordinary (non-induced) extremal functions.
    The paper explicitly states that its result extends this theorem to the induced setting.

pith-pipeline@v0.9.0 · 5499 in / 1355 out tokens · 42914 ms · 2026-05-10T20:06:52.477355+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    N. Alon, M. Krivelevich, B. Sudakov, Tur´ an numbers of bipartite graphs and related Ramsey- type questions,Combin. Probab. Comput.12(2003), 477-494

    work page 2003

  2. [2]

    B. Bukh, D. Conlon, Rational exponents in extremal graph theory,J. Eur. Math. Soc.20 (2018), 1747-1757. 16

    work page 2018

  3. [3]

    Conlon, O

    D. Conlon, O. Janzer, Rational exponents near two,Advances in Combinatorics, paper 9, (2022), 10pp

    work page 2022

  4. [4]

    Conlon, O

    D. Conlon, O. Janzer, J. Lee, More on the extremal number of subdivisions,Combinatorica 411(2021), 465-494

    work page 2021

  5. [5]

    Z. Dong, J. Gao, R. Li, H. Liu, Induced rational exponent and bipartite subgraphs inK s,s-free graphs, arXiv:2506.09020v1

    work page arXiv

  6. [6]

    Erd˝ os, On extremal problems of graphs and generalized graphs,Israel J

    P. Erd˝ os, On extremal problems of graphs and generalized graphs,Israel J. Math.2(3) (1964), 183-190

    work page 1964

  7. [7]

    Erd˝ os, On the combinatorial problems which I would most like to see solved,Combinatorica 1(1981), 25-42

    P. Erd˝ os, On the combinatorial problems which I would most like to see solved,Combinatorica 1(1981), 25-42

    work page 1981

  8. [8]

    Erd˝ os, M

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

    work page 1966

  9. [9]

    Erd˝ os, A.H

    P. Erd˝ os, A.H. Stone, On the structure of linear graphs,Bull. Amer. Math. Soc.52(1946), 1087-1091

    work page 1946

  10. [10]

    Erd˝ os, M

    P. Erd˝ os, M. Simonovits, Some extremal problems in graph theory, in Combinatorics and Applications 1, (Proc. Colloq. BalatonF¨ ured, 1969), North-Holland, Amsterdam, 1970, pp 377-390

    work page 1969

  11. [11]

    F¨ uredi, On a Tur´ an type problem of Erd˝ os,Combinatorica11(1991), 75-79

    Z. F¨ uredi, On a Tur´ an type problem of Erd˝ os,Combinatorica11(1991), 75-79

    work page 1991

  12. [12]

    F¨ uredi, M

    Z. F¨ uredi, M. Simonovits, The history of degenerate (bipartite) extremal graph problems, in Erd˝ os centennial, Bolyai Sco. Math. Stud., vol 25, Jan´ os Bolyai Math. Soc., B Budapest, 2013

    work page 2013

  13. [13]

    Hunter, A

    Z. Hunter, A. Milojevi´ c, B. Sudakov, I. Tomon, K˝ ov´ ari-S´ os-Tur´ an theorem for hereditary families,J. Combinatorial Theory, Ser. B172(2025), 168-197

    work page 2025

  14. [14]

    Janzer, The extremal number of the subdivisions of the complete bipartite graph,SIAM J

    O. Janzer, The extremal number of the subdivisions of the complete bipartite graph,SIAM J. Discrete Math34(2020), 241-250

    work page 2020

  15. [15]

    Janzer, The extremal number of longer subdivisions,Bull

    O. Janzer, The extremal number of longer subdivisions,Bull. Lond. Math. Soc.53(2021), 108-118

    work page 2021

  16. [16]

    Janzer, C

    O. Janzer, C. Pohoata, On the Zarankewicz problem for graphs with bounded VC-dimensions, Combinatorica44(2024), 839-848

    work page 2024

  17. [17]

    Jiang, J

    T. Jiang, J. Ma, L. Yepremyan, On Tur´ an exponents of bipartite graphs,Combin. Probab. Comput.31(2022), 333-344

    work page 2022

  18. [18]

    Jiang, Z

    T. Jiang, Z. Jiang, J. Ma, Negligible obstructions and Tur´ an exponents,Ann. Applied Math. 38(2022), 356-384. 17

    work page 2022

  19. [19]

    Jiang, Y

    T. Jiang, Y. Qiu, Many Tur´ an exponents via subdivisions,Combin. Probab. Comput.32(2023), 134-150

    work page 2023

  20. [20]

    Jiang, R

    T. Jiang, R. Seiver, Tur´ an numbers of subdivided graphs,SIAM. J. Disc. Math26(2012), 1238-1255

    work page 2012

  21. [21]

    D.Y. Kang, J. Kim, H. Liu, On the rational Tur´ an exponents conjecture,J. Combin. Theory Ser. B148(2021), 149-172

    work page 2021

  22. [22]

    K˝ ov´ ari, V.T

    T. K˝ ov´ ari, V.T. S´ os, P. Tur´ an, On a problem of Zarankiewicz,Colloq. Math.3(1954), 50-57. 18

    work page 1954