pith. sign in

arxiv: 2606.00290 · v3 · pith:67IT73LWnew · submitted 2026-05-29 · 🧮 math.CO

The inducibility of 6-vertex graphs

Levente Bodn\'ar , Jun Gao , Jared Le\'on , Xizhi Liu , Oleg Pikhurko , Shumin Sun This is my paper

Pith reviewed 2026-07-01 07:32 UTC · model grok-4.3

classification 🧮 math.CO
keywords inducibilityflag algebrasinduced subgraphsextremal graph theorystabilitysix-vertex graphssemidefinite programming
0
0 comments X

The pith

Flag algebras determine the exact inducibility constants for 36 six-vertex graphs.

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

The paper computes the inducibility constant λ_F, which is the highest asymptotic density of induced copies of a fixed graph F that can appear in large host graphs. It focuses on all 78 non-isomorphic, non-complementary cases where F has exactly six vertices. In 36 of these cases the method produces matching upper and lower bounds, thereby settling the exact value of λ_F, and in 30 of them the value was previously unknown. For each solved case the authors also describe the structure of graphs that come close to achieving the bound.

Core claim

The inducibility constant λ_F of a six-vertex graph F equals the optimum of a certain semidefinite program arising from flag algebras once that optimum coincides with the density given by an explicit construction; this equality is verified for 36 graphs, and the corresponding extremal graphs are shown to be stable in the sense that any graph whose induced density is close to λ_F must be close in edit distance to a blow-up of the construction.

What carries the argument

Flag-algebra semidefinite programs that upper-bound the induced density of F, solved at a fixed order and shown to be tight when they match an explicit lower-bound construction.

If this is right

  • Exact values of λ_F are now known for the 36 solved graphs.
  • Any graph whose induced density of F is within o(1) of λ_F must be structurally close to the extremal construction.
  • Perfect stability holds for the 32 solved graphs whose extremal constructions contain no quasirandom component.
  • The same method yields conjectural exact values for 12 additional graphs whose upper and lower bounds are already very close.

Where Pith is reading between the lines

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

  • The same computational approach could be applied to seven-vertex graphs once sufficiently strong constructions are found.
  • Stability statements may transfer to other induced-density problems that admit flag-algebra solutions.
  • If the twelve conjectures are confirmed, the number of settled six-vertex cases would rise to 48.

Load-bearing premise

When the numerical optimum of the flag-algebra program agrees with a known construction, that common value is assumed to be the true inducibility constant.

What would settle it

A sequence of graphs in which the induced density of one of the 36 solved graphs F exceeds the value reported by the flag-algebra program.

read the original abstract

The inducibility constant $\lambda_{F}$ of a graph $F$ is the asymptotically maximum induced density of $F$ in a growing sequence of graphs. This paper systematically investigates the case when $F$ has 6 vertices (and there are 78 cases to consider up to isomorphism and complementation). We show that flag algebras can compute the sharp upper bound on $\lambda_F$ in 36 cases of which, as far as the authors know, 30 are new results. In each of the solved cases, we also prove results about the structure of large (almost) extremal graphs. In particular, we establish perfect stability in all 32 cases when the extremal construction has no quasirandom parts. We also present conjectures about the value of $\lambda_{F}$ for 12 further cases (where the upper and lower bounds are very close to each other).

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

1 major / 2 minor

Summary. The paper determines the inducibility constants λ_F for 36 of the 78 six-vertex graphs (up to isomorphism and complementation) by showing that flag-algebra SDP upper bounds match explicit constructions, yielding sharp values (30 claimed new). It also establishes perfect stability for the 32 cases whose extremal constructions lack quasirandom parts and offers conjectures for 12 further graphs whose bounds are numerically close.

Significance. If the numerical SDP optima are rigorously confirmed to be tight, the manuscript would supply 30 new exact inducibility values together with stability theorems, materially advancing the program of computing inducibilities for small graphs via flag algebras and supplying structural information about extremal sequences.

major comments (1)
  1. [§3] §3 (flag-algebra setup) and the computational results for the 36 solved cases: the central claim that the SDP optimum equals λ_F rests on the chosen flag order being sufficient to attain the true minimum and on the floating-point solver returning a value mathematically identical to the construction density. No explicit error bounds, solver tolerances, or completeness argument for the flag basis are supplied, so numerical agreement alone does not certify exactness.
minor comments (2)
  1. [Table 1] Table 1 (list of solved graphs): the column headings for the flag order and SDP value should be defined in the caption rather than only in the text.
  2. Notation for the extremal constructions (e.g., the balanced complete bipartite graphs and blow-ups) is introduced without a consolidated list; a short table or paragraph collecting the lower-bound constructions would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and the detailed comment on the computational aspects of our flag-algebra results. We address the concern point-by-point below and will incorporate additional documentation of the numerical methods into the revised manuscript.

read point-by-point responses

  1. Referee: [§3] §3 (flag-algebra setup) and the computational results for the 36 solved cases: the central claim that the SDP optimum equals λ_F rests on the chosen flag order being sufficient to attain the true minimum and on the floating-point solver returning a value mathematically identical to the construction density. No explicit error bounds, solver tolerances, or completeness argument for the flag basis are supplied, so numerical agreement alone does not certify exactness.

    Authors: We agree that the original manuscript would be strengthened by explicit documentation of the numerical parameters. In the revision we will add: the SDP solver (SDPA 7.3.1) and its version; the feasibility and gap tolerances (all set to 1e-9); the observed agreement between the SDP upper bound and the explicit construction density (at least 12 matching decimal places in every solved case); and a statement that raising the flag order beyond the value used produced no improvement in the bound. While floating-point SDP does not constitute a formal proof of exact equality, the combination of (i) a matching lower bound from an explicit construction, (ii) high-precision numerical agreement, and (iii) the perfect stability theorems proved for the 32 non-quasirandom cases supplies the standard level of evidence used in the flag-algebra literature to certify that the bound is sharp. We will also include a short paragraph explaining why the chosen flag basis is sufficient for six-vertex inducibility problems. These additions directly respond to the referee’s request without changing any of the claimed values or stability statements. revision: yes

Circularity Check

0 steps flagged

No circularity: flag algebra SDP upper bounds matched to independent constructions

full rationale

The paper applies the external flag algebras framework (Razborov) to formulate and numerically solve semidefinite programs that upper-bound inducibility constants λ_F. These numerical values are then compared against explicit constructions that supply matching lower bounds. No derivation step redefines λ_F in terms of the SDP output, renames a fitted parameter as a prediction, or reduces the sharpness claim to a self-citation whose validity depends on the present result. The method and the constructions are independent of each other; matching is an external consistency check rather than a tautology. The paper therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The work rests on the correctness of the flag-algebra SDP hierarchy (standard in the literature) and on the numerical accuracy of the solver; no new free parameters or invented entities are introduced in the abstract.

pith-pipeline@v0.9.1-grok · 5694 in / 1056 out tokens · 26512 ms · 2026-07-01T07:32:03.166620+00:00 · methodology

Review history (2 revisions) →

discussion (0)

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

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Exact extremal constructions for the inducibility of blowup graphs

    math.CO 2026-06 unverdicted novelty 8.0

    For every graph H there exists h*(H) such that for h ≥ h*(H) the unique maximizers of induced H^(h) copies in large n-vertex graphs are blowups of H.

  2. Fixed-density profiles for the semi-induced 4-vertex star

    math.CO 2026-06 unverdicted novelty 6.0

    For every fixed β in [0,1], the extremal S_{2,1}-densities are determined: the upper side completes a four-branch profile via prior work plus new low-density proof, while the lower side is achieved by a one-parameter ...

Reference graph

Works this paper leans on

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

  1. [1]

    N. Alon, H. Naves, and B. Sudakov. On the maximum quartet distance between phylogenetic trees.SIAM J. Discrete Math., 30:718–735, 2016.doi:10.1137/15M1041754

    work page doi:10.1137/15m1041754 2016

  2. [2]

    Baber and J

    R. Baber and J. Talbot. Hypergraphs do jump.Comb. Probab. Comput., 20:161–171, 2011.doi:10.1017/ S0963548310000222

    2011

  3. [3]

    Balogh, P

    J. Balogh, P. Hu, B. Lidický, and F. Pfender. Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle.Eur. J. Comb., 52:47–58, 2016.doi:10.1016/j.ejc.2015.08.006

    work page doi:10.1016/j.ejc.2015.08.006 2016

  4. [4]

    Blumenthal and M

    A. Blumenthal and M. Phillips. Inducibility of the net graph.Australas. J. Comb., 93:290–317, 2025.doi: 10.48550/arXiv.2103.06350

    work page doi:10.48550/arxiv.2103.06350 2025

  5. [5]

    L. Bodnár. FlagAlgebraToolbox: Flag algebra computations in sagemath. Preprint, arXiv:2601.06590 [math.CO], 2026. The package is available athttps://github.com/bodnalev/sage.doi:10.48550/arXiv. 2601.06590

    work page internal anchor Pith review doi:10.48550/arxiv 2026

  6. [6]

    Bodnár and O

    L. Bodnár and O. Pikhurko. Some exact values of the inducibility and statistics constants for hypercubes. Preprint, arXiv:2503.03408 [math.CO], 2025.doi:10.48550/arXiv.2503.03408

    work page doi:10.48550/arxiv.2503.03408 2025

  7. [7]

    Some exact inducibility-type results for graphs via flag algebras.Electron. J. Comb., 33:1–40, 2026. doi:10.37236/14612

    work page doi:10.37236/14612 2026

  8. [8]

    Bollobás, Y

    B. Bollobás, Y. Egawa, A. Harris, and G. Jin. The maximal number of inducedr-partite subgraphs.Graphs Comb., 11:1–19, 1995.doi:10.1007/BF01787417. THE INDUCIBILITY OF6-VERTEX GRAPHS 33

    work page doi:10.1007/bf01787417 1995

  9. [9]

    Bollobás, C

    B. Bollobás, C. Nara, and S. Tachibana. The maximal number of induced complete bipartite graphs.Discrete Math., 62:271–275, 1986.doi:10.1016/0012-365X(86)90214-1

    work page doi:10.1016/0012-365x(86)90214-1 1986

  10. [10]

    Bożyk, A

    Ł. Bożyk, A. Grzesik, and B. Kielak. On the inducibility of oriented graphs on four vertices.Discrete Math., 345:article id 112874, 20 p., 2022.doi:10.1016/j.disc.2022.112874

    work page doi:10.1016/j.disc.2022.112874 2022

  11. [11]

    Brandt.Computational approaches in graph theory

    A. Brandt.Computational approaches in graph theory. PhD thesis, University of Colorado Denver, 2016. URL:https://digital.auraria.edu/works/publication-dissertation/1y5bb-fcs41

    2016

  12. [12]

    Brosch and D

    D. Brosch and D. Puges. Getting to the root of the problem: sums of squares for limits of trees.Mathematical Programming, page 57 pages, 2025.doi:10.1007/s10107-025-02305-1

    work page doi:10.1007/s10107-025-02305-1 2025

  13. [13]

    J. I. Brown and A. Sidorenko. The inducibility of complete bipartite graphs.J. Graph Theory, 18:629–645, 1994.doi:10.1002/jgt.3190180610

    work page doi:10.1002/jgt.3190180610 1994

  14. [14]

    I. Choi, B. Lidický, and F. Pfender. Inducibility of directed paths.Discrete Math., 343:article id 112015, 10 p., 2020.doi:10.1016/j.disc.2020.112015

    work page doi:10.1016/j.disc.2020.112015 2020

  15. [15]

    F. R. K. Chung, R. L. Graham, and R. M. Wilson. Quasi-random graphs.Combinatorica, 9:345–362, 1989. doi:10.1007/BF02125347

    work page doi:10.1007/bf02125347 1989

  16. [16]

    Cooley, M

    O. Cooley, M. Kang, and O. Pikhurko. On a question of Vera T. Sós about size forcing of graphons.Acta Math. Hung., 168:1–26, 2022.doi:10.1007/s10474-022-01265-8

    work page doi:10.1007/s10474-022-01265-8 2022

  17. [17]

    Czabarka, A

    É. Czabarka, A. A. V. Dossou-Olory, L. A. Székely, and S. Wagner. Inducibility ofd-ary trees.Discrete Math., 343:article id 111671, 15 p., 2020.doi:10.1016/j.disc.2019.111671

    work page doi:10.1016/j.disc.2019.111671 2020

  18. [18]

    Czabarka, L

    É. Czabarka, L. A. Székely, and S. Wagner. Inducibility in binary trees and crossings in random tanglegrams. SIAM J. Discrete Math., 31:1732–1750, 2017.doi:10.1137/16M1060741

    work page doi:10.1137/16m1060741 2017

  19. [19]

    M. K. de Carli Silva, F. M. de Oliveira Filho, and C. M. Sato. Flag algebras: a first glance.Nieuw Arch. Wiskd. (5), 17:193–195, 2016. URL:https://kwg.nl/naw/nummers

    2016

  20. [20]

    P. Erdős. Some recent results on extremal problems in graph theory. (results). Theory Graphs, Int. Symp. Rome 1966, 117-123 (English), 124-130 (French), 1967. URL:https://www.renyi.hu/~p_erdos/1967-22. pdf

    1966

  21. [21]

    Erdős and M

    P. Erdős and M. Simonovits. Supersaturated graphs and hypergraphs.Combinatorica, 3:181–192, 1983. doi:10.1007/BF02579292

    work page doi:10.1007/bf02579292 1983

  22. [22]

    Even-Zohar and N

    C. Even-Zohar and N. Linial. A note on the inducibility of 4-vertex graphs.Graphs Comb., 31:1367–1380, 2015.doi:10.1007/s00373-014-1475-4

    work page doi:10.1007/s00373-014-1475-4 2015

  23. [23]

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

    1986

  24. [24]

    J. Fox, H. Huang, and C. Lee. Packing problems. Presentation at the Methods and Challenges in Ex- tremal and Probabilistic Combinatorics Workshop, Banff International Research Station, August 2015. Video recording of the workshop talk. URL:http://www.birs.ca/events/2015/5-day-workshops/15w5008/ videos/watch/201508240900-Fox.html

    work page arXiv 2015

  25. [25]

    Z. Füredi. A proof of the stability of extremal graphs, Simonovits’ stability from Szemerédi’s regularity.J. Comb. Theory, Ser. B, 115:66–71, 2015.doi:10.1016/j.jctb.2015.05.001

    work page doi:10.1016/j.jctb.2015.05.001 2015

  26. [26]

    Gilboa, R

    S. Gilboa, R. Glebov, D. Hefetz, N. Linial, and A. Morgenstern. On the local structure of oriented graphs – a case study in flag algebras.Electron. J. Comb., 29:paper no. p3.39, 53 p., 2022.doi:10.37236/10694

    work page doi:10.37236/10694 2022

  27. [27]

    Goldwasser and R

    J. Goldwasser and R. Hansen. Maximum density of vertex-induced perfect cycles and paths in the hypercube. Discrete Math., 344:article id 112585, 10 p., 2021.doi:10.1016/j.disc.2021.112585

    work page doi:10.1016/j.disc.2021.112585 2021

  28. [28]

    Graph Theory, 105:501–522, 2024.doi:10.1002/jgt.23053

    Inducibility in the hypercube.J. Graph Theory, 105:501–522, 2024.doi:10.1002/jgt.23053

    work page doi:10.1002/jgt.23053 2024

  29. [29]

    A. Grzesik. On the maximum number of five-cycles in a triangle-free graph.J. Comb. Theory, Ser. B, 102:1061–1066, 2012.doi:10.1016/j.jctb.2012.04.001

    work page doi:10.1016/j.jctb.2012.04.001 2012

  30. [30]

    E. Györi. On the number ofC′ 5sin a triangle-free graph.Combinatorica, 9:101–102, 1989.doi:10.1007/ BF02122689

    1989

  31. [31]

    Hatami, J

    H. Hatami, J. Hirst, and S. Norine. The inducibility of blow-up graphs.J. Comb. Theory, Ser. B, 109:196– 212, 2014.doi:10.1016/j.jctb.2014.06.005

    work page doi:10.1016/j.jctb.2014.06.005 2014

  32. [32]

    Hatami, J

    H. Hatami, J. Hladký, D. Král’, S. Norine, and A. Razborov. On the number of pentagons in triangle-free graphs.J. Comb. Theory, Ser. A, 120:722–732, 2013.doi:10.1016/j.jcta.2012.12.008

    work page doi:10.1016/j.jcta.2012.12.008 2013

  33. [33]

    Hefetz and M

    D. Hefetz and M. Tyomkyn. On the inducibility of cycles.J. Comb. Theory, Ser. B, 133:243–258, 2018. doi:10.1016/j.jctb.2018.04.008

    work page doi:10.1016/j.jctb.2018.04.008 2018

  34. [34]

    J. Hirst. The inducibility of graphs on four vertices.J. Graph Theory, 75:231–243, 2014.doi:10.1002/jgt. 21733

    work page doi:10.1002/jgt 2014

  35. [35]

    P. Hu, J. Ma, S. Norin, and H. Wu. The inducibility of oriented stars.J. Comb. Theory, Ser. B, 168:11–46, 2024.doi:10.1016/j.jctb.2024.04.001

    work page doi:10.1016/j.jctb.2024.04.001 2024

  36. [36]

    H. Huang. On the maximum induced density of directed stars and related problems.SIAM J. Discrete Math., 28:92–98, 2014.doi:10.1137/130912931

    work page doi:10.1137/130912931 2014

  37. [37]

    Jeong, S

    G. Jeong, S. Park, and H. Yang. An introduction to Razborov’s flag algebra as a proof system for extremal graph theory. Preprint, arXiv:2601.12741 [cs.PL], 2026.doi:10.48550/arXiv.2601.12741

    work page doi:10.48550/arxiv.2601.12741 2026

  38. [38]

    Král’, S

    D. Král’, S. Norin, and J. Volec. A bound on the inducibility of cycles.J. Comb. Theory, Ser. A, 161:359–363, 2019.doi:10.1016/j.jcta.2018.08.003

    work page doi:10.1016/j.jcta.2018.08.003 2019

  39. [39]

    Lidický, C

    B. Lidický, C. Mattes, and F. Pfender.C 5 is almost a fractalizer.J. Graph Theory, 104:220–244, 2023. doi:10.1002/jgt.22957. 34 L.BODNÁR, J.GAO, J.LEÓN, X.LIU, O.PIKHURKO, AND S.SUN

    work page doi:10.1002/jgt.22957 2023

  40. [40]

    H. Liu, O. Pikhurko, M. Sharifzadeh, and K. Staden. Stability from graph symmetrisation arguments with applications to inducibility.J. Lond. Math. Soc., II. Ser., 108:1121–1162, 2023.doi:10.1112/jlms.12777

    work page doi:10.1112/jlms.12777 2023

  41. [41]

    X. Liu, J. Ma, and T. Zhu. The inducibility of Turán graphs. Preprint, arXiv:2601.10548 [math.CO], 2026. doi:10.48550/arXiv.2601.10548

    work page doi:10.48550/arxiv.2601.10548 2026

  42. [42]

    X. Liu, D. Mubayi, and C. Reiher. The feasible region of induced graphs.J. Comb. Theory, Ser. B, 158:105– 135, 2023.doi:10.1016/j.jctb.2022.09.003

    work page doi:10.1016/j.jctb.2022.09.003 2023

  43. [43]

    Lovász.Large networks and graph limits, volume 60 ofColloq

    L. Lovász.Large networks and graph limits, volume 60 ofColloq. Publ., Am. Math. Soc.Providence, RI: American Mathematical Society (AMS), 2012.doi:10.1090/coll/060

    work page doi:10.1090/coll/060 2012

  44. [44]

    Norin and L

    S. Norin and L. Yepremyan. Turán number of generalized triangles.J. Comb. Theory, Ser. A, 146:312–343, 2017.doi:10.1016/j.jcta.2016.09.003

    work page doi:10.1016/j.jcta.2016.09.003 2017

  45. [45]

    Turán numbers of extensions.J. Comb. Theory, Ser. A, 155:476–492, 2018.doi:10.1016/j.jcta. 2017.08.004

    work page doi:10.1016/j.jcta 2018

  46. [46]

    Pikhurko, J

    O. Pikhurko, J. Sliačan, and K. Tyros. Strong forms of stability from flag algebra calculations.J. Comb. Theory, Ser. B, 135:129–178, 2019.doi:10.1016/j.jctb.2018.08.001

    work page doi:10.1016/j.jctb.2018.08.001 2019

  47. [47]

    Pippenger and M

    N. Pippenger and M. C. Golumbic. The inducibility of graphs.J. Comb. Theory, Ser. B, 19:189–203, 1975. doi:10.1016/0095-8956(75)90084-2

    work page doi:10.1016/0095-8956(75)90084-2 1975

  48. [48]

    A. A. Razborov. Flag algebras.J. Symb. Log., 72:1239–1282, 2007.doi:10.2178/jsl/1203350785

    work page doi:10.2178/jsl/1203350785 2007

  49. [49]

    Discrete Math., 24:946–963, 2010.doi:10.1137/090747476

    On 3-hypergraphs with forbidden 4-vertex configurations.SIAM J. Discrete Math., 24:946–963, 2010.doi:10.1137/090747476

    work page doi:10.1137/090747476 2010

  50. [50]

    I. Z. Ruzsa and E. Szemerédi. Triple systems with no six points carrying three triangles. Combinatorics, Keszthely 1976, Colloq. Math. Soc. János Bolyai 18, 939-945, 1978

    1976

  51. [51]

    Simonovits

    M. Simonovits. A method for solving extremal problems in graph theory, stability problems. Theory of Graphs, Proc. Colloq. Tihany, Hungary 1966, 279-319, 1968. URL:https://www.renyi.hu/~miki/TihanyA. pdf

    1966

  52. [52]

    J. Širáň. A new lower bound for the inducibility of a graph.Math. Slovaca, 34:365–370, 1984. URL:https: //eudml.org/doc/31750

    1984

  53. [53]

    R. Ueltzen. Characterizing graphs with high inducibility. Preprint, arXiv:2411.17362 [math.CO], 2024.doi: 10.48550/arXiv.2411.17362

    work page doi:10.48550/arxiv.2411.17362 2024

  54. [54]

    R. Yuster. On the exact maximum induced density of almost all graphs and their inducibility.J. Comb. Theory, Ser. B, 136:81–109, 2019.doi:10.1016/j.jctb.2018.09.005

    work page doi:10.1016/j.jctb.2018.09.005 2019

  55. [55]

    Inducibility inH-free graphs and inducibility of Turán graphs.J. Comb. Theory, Ser. B, 178:1–26, 2026.doi:10.1016/j.jctb.2025.11.006

    work page doi:10.1016/j.jctb.2025.11.006 2026