pith. sign in

arxiv: 2606.06202 · v1 · pith:72DIUY3Fnew · submitted 2026-06-04 · 🧮 math.CO

Exact extremal constructions for the inducibility of blowup graphs

Wanfang Chen , Xizhi Liu This is my paper

Pith reviewed 2026-06-28 00:32 UTC · model grok-4.3

classification 🧮 math.CO
keywords inducibilityblowup graphsextremal graph theoryinduced subgraphsasymptotic extremal problemsgraph homomorphisms
0
0 comments X

The pith

For every graph H there is a finite threshold h_*(H) such that large-h blowups of H are maximized in induced copies only by blowups of H itself.

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

The paper proves that for any fixed graph H, once the blowup parameter h grows past a constant depending only on H, the n-vertex graphs containing the largest number of induced copies of the h-blowup H^{(h)} must themselves be blowups of H. This holds for all sufficiently large n. The result gives an exact structural description of the extremal graphs rather than only an asymptotic density, and it resolves a question posed in 1995 about when such exact constructions exist.

Core claim

For every finite graph H there exists a constant h_*(H) such that whenever h ≥ h_*(H) and n is large enough, every n-vertex graph that maximizes the number of induced copies of H^{(h)} is a blowup of H.

What carries the argument

The h-blowup H^{(h)}, formed by replacing each vertex of H by an independent set of size h and each edge by a complete bipartite graph; the argument shows that for large h any maximizer must preserve exactly this partite structure.

If this is right

  • The inducibility value of H^{(h)} equals the density achieved by the balanced complete h-partite graph whose parts are sized according to the Turán graph of H.
  • Exact extremal graphs for the inducibility problem are identified for all sufficiently blown-up targets.
  • The 1995 question of Bollobás, Egawa, Harris and Jin receives a positive answer for every H once h is large enough.

Where Pith is reading between the lines

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

  • The same threshold technique may apply to other induced-subgraph extremal problems where the target is a blowup of a fixed pattern.
  • For concrete small H it may now be feasible to determine the precise value of h_*(H) by direct checking of small cases.
  • The result suggests that inducibility problems often stabilize to blowup constructions once the target graph becomes sufficiently uniform.

Load-bearing premise

A finite threshold h_*(H) exists for every graph H beyond which the blowup property holds uniformly.

What would settle it

A counterexample consisting of some fixed H together with a sequence of h growing to infinity and, for each such h, an n-vertex graph (n large) that is not a blowup of H yet contains strictly more induced copies of H^{(h)} than any blowup of H.

read the original abstract

For a finite graph $H$ and a positive integer $h$, the $h$-blowup $H^{(h)}$ of $H$ is the graph obtained by replacing each vertex of $H$ by a set of size $h$ and each edge by a complete bipartite graph between the corresponding sets. We prove that, for every $H$, there exists a constant $h_*(H)$ such that whenever $h\ge h_*(H)$ and $n$ is sufficiently large, every $n$-vertex graph maximizing the number of induced copies of $H^{(h)}$ is a blowup of $H$. This refines the asymptotic result of Hatami, Hirst and Norine and settles the question posed by Bollob\'as, Egawa, Harris and Jin in 1995.

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 for every finite graph H there exists a constant h_*(H) such that, whenever h ≥ h_*(H) and n is sufficiently large, every n-vertex graph maximizing the number of induced copies of the h-blowup H^{(h)} is a blowup of H. The result refines the asymptotic inducibility theorem of Hatami, Hirst and Norine and settles the 1995 question of Bollobás, Egawa, Harris and Jin.

Significance. If correct, the theorem supplies the first exact (rather than asymptotic) characterization of the extremal graphs for the inducibility of blowups, confirming that H-blowups are the unique maximizers once the blowup parameter exceeds a finite threshold depending only on H. The argument converts a known density result into an exact statement for all large n without introducing free parameters or unbounded quantities, thereby strengthening the toolkit for exact induced-extremal problems.

minor comments (2)
  1. [§1] §1: the definition of the h-blowup H^{(h)} is referenced before it is formally introduced; a forward pointer to the definition in §2 would improve readability.
  2. [§4] The proof of the main theorem relies on a stability argument whose quantitative bounds are stated only implicitly; making the dependence of the stability threshold on h explicit would clarify the passage from asymptotic to exact extremality.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their supportive summary of our work and for recommending minor revision. No major comments appear in the report, so we have no specific points to address.

Circularity Check

0 steps flagged

No circularity; refines external asymptotic result

full rationale

The manuscript proves existence of finite h_*(H) for each fixed H such that large-h blowups of H are the unique maximizers of induced H^{(h)} copies for large n. It explicitly refines the known asymptotic theorem of Hatami-Hirst-Norine (external citation with no author overlap) and resolves the 1995 Bollobás-Egawa-Harris-Jin question. No self-citations appear as load-bearing steps, no parameters are fitted then relabeled as predictions, and no definitional or ansatz smuggling occurs. The derivation chain is therefore independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract only; no free parameters, axioms, or invented entities are visible in the provided text.

pith-pipeline@v0.9.1-grok · 5662 in / 1067 out tokens · 26493 ms · 2026-06-28T00:32:03.792502+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

19 extracted references · 1 linked inside Pith

  1. [1]

    N. Alon, D. Hefetz, M. Krivelevich, and M. Tyomkyn. Edge-statistics on large graphs.Combin. Probab. Comput., 29(2):163–189, 2020

    2020

  2. [2]

    Balogh, P

    J. Balogh, P. Hu, B. Lidick` y, and F. Pfender. Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle.European J. Combin., 52:47–58, 2016

    2016

  3. [3]

    Bodnár, J

    L. Bodnár, J. Gao, J. León, X. Liu, O. Pikhurko, and S. Sun. The inducibility of 6-vertex graphs. arXiv preprint arXiv:2606.00290, 2026

    Pith/arXiv arXiv 2026

  4. [4]

    Bollobás, Y

    B. Bollobás, Y. Egawa, A. Harris, and G. Jin. The maximal number of inducedr-partite subgraphs. Graphs Combin., 11(1):1–19, 1995

    1995

  5. [5]

    Even-Zohar and N

    C. Even-Zohar and N. Linial. A note on the inducibility of 4-vertex graphs.Graphs Combin., 31(5):1367–1380, 2015

    2015

  6. [6]

    G. Exoo. Dense packings of induced subgraphs.Ars Combin., 22:5–10, 1986

    1986

  7. [7]

    J. Fox, H. Huang, and C. Lee. A solution to the inducibility problem for almost all graphs. Manuscript, 2017

    2017

  8. [8]

    Fox and L

    J. Fox and L. Sauermann. A completion of the proof of the edge-statistics conjecture.Adv. Comb., pages Paper No. 4, 52, 2020

    2020

  9. [9]

    Hatami, J

    H. Hatami, J. Hirst, and S. Norine. The inducibility of blow-up graphs.J. Combin. Theory Ser. B, 109:196–212, 2014

    2014

  10. [10]

    Hefetz and M

    D. Hefetz and M. Tyomkyn. On the inducibility of cycles.J. Combin. Theory Ser. B, 133:243–258, 2018

    2018

  11. [11]

    J. Hirst. The inducibility of graphs on four vertices.J. Graph Theory, 75(3):231–243, 2014

    2014

  12. [12]

    Král’, S

    D. Král’, S. Norin, and J. Volec. A bound on the inducibility of cycles.J. Combin. Theory Ser. A, 161:359–363, 2019

    2019

  13. [13]

    M. Kwan, B. Sudakov, and T. Tran. Anticoncentration for subgraph statistics.J. Lond. Math. Soc. (2), 99(3):757–777, 2019

    2019

  14. [14]

    Martinsson, F

    A. Martinsson, F. Mousset, A. Noever, and M. Trujić. The edge-statistics conjecture forℓ≪k 6/5. Israel J. Math., 234(2):677–690, 2019

    2019

  15. [15]

    Pikhurko, J

    O. Pikhurko, J. Sliačan, and K. Tyros. Strong forms of stability from flag algebra calculations.J. Combin. Theory Ser. B, 135:129–178, 2019

    2019

  16. [16]

    Pippenger and M

    N. Pippenger and M. C. Golumbic. The inducibility of graphs.J. Combin. Theory Ser. B, 19(3):189– 203, 1975

    1975

  17. [17]

    A. A. Razborov. Flag algebras.J. Symbolic Logic, 72(4):1239–1282, 2007

    2007

  18. [18]

    R. Ueltzen. Characterizing graphs with high inducibility.arXiv preprint arXiv:2411.17362, 2024

    arXiv 2024

  19. [19]

    R. Yuster. On the exact maximum induced density of almost all graphs and their inducibility.J. Combin. Theory Ser. B, 136:81–109, 2019. 14

    2019