pith. sign in

arxiv: 2605.15021 · v2 · pith:GADPXPPTnew · submitted 2026-05-14 · 🧮 math.CO

Local maximum of inducibility profiles

J\'ozsef Balogh , Bernard Lidick\'y , Haoran Luo This is my paper

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

classification 🧮 math.CO
keywords inducibilitylocal maximaflag algebrasextremal graph theoryinduced subgraphsK_{2,2,1}edge density
0
0 comments X

The pith

The inducibility profile of K_{2,2,1} has at least two local maxima in (0,1).

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

A question was posed whether the function that records the highest possible induced density of a fixed graph G inside host graphs of edge density e can possess a non-trivial local maximum for some choice of G. This paper establishes an affirmative answer by proving that the specific profile for G equal to K_{2,2,1} attains at least two such interior local maxima. The argument proceeds by using semidefinite programs to produce upper bounds on the profile that are tight enough to force the existence of peaks away from the endpoints 0 and 1. The paper further computes the exact value of the same profile at every edge density of the form (k-1)/k and shows that certain other graphs K_t^- likewise possess at least one non-global local maximum.

Core claim

The supremum of the induced density of K_{2,2,1} inside n-vertex graphs whose edge density approaches a fixed value e is a function I_{K_{2,2,1}}(e) that possesses at least two local maxima inside the open interval (0,1). The same function is evaluated exactly when e equals (k-1)/k for every integer k at least 3. For every t belonging to the arithmetic progression 5,8,11 up to 74 the inducibility profile of K_t^- likewise admits a non-global local maximum.

What carries the argument

Flag-algebra semidefinite programs that certify upper bounds on induced densities sufficiently tight to locate interior local maxima, together with a symmetrization reduction that converts the problem for K_t^- into an application of the clique-density theorem.

If this is right

  • The inducibility profile of at least one graph is not a unimodal function of edge density.
  • Exact values of I_{K_{2,2,1}}(e) are known at every rational point of the form (k-1)/k.
  • The inducibility profiles of K_t^- for t=5,8,...,74 each contain at least one local maximum that is not the global maximum.
  • Flag-algebra computations can be used to decide the existence of interior local maxima for small fixed graphs.

Where Pith is reading between the lines

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

  • One could attempt to determine the precise number of local maxima or the locations of all critical points for the K_{2,2,1} profile by refining the same computational method.
  • Analogous local-maximum phenomena may appear for other small 5-vertex graphs whose inducibility profiles have not yet been examined at this level of precision.
  • If the same computational certification technique succeeds for additional graphs, then non-unimodal inducibility profiles may turn out to be common rather than exceptional.

Load-bearing premise

The numerical bounds obtained from the semidefinite programs are tight enough to certify that the profile actually turns downward after each claimed interior peak rather than continuing to increase.

What would settle it

An explicit infinite family of graphs whose edge density lies near one of the claimed local-maximum points and whose induced K_{2,2,1} density strictly exceeds the value attained at a nearby density point would falsify the local-maximum claim.

Figures

Figures reproduced from arXiv: 2605.15021 by Bernard Lidick\'y, Haoran Luo, J\'ozsef Balogh.

Figure 1
Figure 1. Figure 1: Lower bound on IK2,2,1 (e) from constructions. e ∈ [0, 2/3] e = 2/3 e ∈ [2/3, 3/4] e = 3/4 [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Constructions for Conjecture 5. Conjecture 7. For every k > 0 there is a graph H ∈ M where IH(x) has at least k local maxima. While IK2,2,1 (e) is continuous, it seems to not be differentiable at e = (k − 1)/k. Our experiments with other multipartite graphs indicate that these peaks may become sharper and may create local maxima. The inducibility of balanced graphs in M was determined by Bollob´as, Egawa, … view at source ↗
read the original abstract

For a graph $G$ and $e\in [0,1]$, denote by $I_G(e)$ the supremum of induced density of $G$ over $n$-vertex graphs with edge density $e$ as $n$ goes to infinity. Liu, Mubayi and Reiher asked if there exists a graph $G$, where $I_G(e)$ has a non-trivial local maximum. In this paper, we answer this problem affirmatively. We first show that $I_{K_{2,2,1}}(e)$ has at least two local maxima in $(0,1)$. Part of this proof is using flag algebras. Additionally, we determine $I_{K_{2,2,1}}(e)$, when $e=(k-1)/k$ for every integer $k\ge 3.$ We also prove that $I_{K_t^-}(e)$ has a non-global local maximum for every $t\in\{5,8,11,\ldots,$ $74\}$. The proof combines a symmetrization theorem of Schelp and Thomason with Reiher's clique density theorem.

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 answers an open question of Liu, Mubayi and Reiher by showing that the inducibility profile I_{K_{2,2,1}}(e) has at least two local maxima in (0,1), with part of the argument relying on flag-algebra semidefinite programs. It also determines the exact value of I_{K_{2,2,1}}(e) at the points e=(k-1)/k for every integer k≥3, and proves that I_{K_t^-}(e) has a non-global local maximum for every t in the set {5,8,11,…,74} by combining the Schelp-Thomason symmetrization theorem with Reiher's clique density theorem.

Significance. If the flag-algebra computations are rigorous and the SDP upper bounds are tight enough to certify interior local maxima (rather than merely boundary behavior), the result would be significant: it supplies the first explicit example of a graph whose inducibility profile has multiple non-trivial local maxima, thereby resolving the question posed by Liu-Mubayi-Reiher. The exact determinations at rational edge densities and the additional family of examples for K_t^- further strengthen the contribution, especially given the reliance on two well-established external theorems.

major comments (1)
  1. [Abstract / flag-algebra proof of local maxima for K_{2,2,1}] Abstract and flag-algebra section: the claim that I_{K_{2,2,1}}(e) has at least two local maxima in (0,1) rests on flag-algebra SDPs producing upper bounds sufficiently tight to detect interior peaks. The manuscript must supply the flag-set size, the numerical precision achieved, explicit error bounds on the SDP value, and an argument showing that any gap between the relaxation and the true inducibility cannot erase the detected local maxima (i.e., that the profile cannot be monotone or boundary-only within the reported precision).
minor comments (2)
  1. [Introduction] Notation: the definition of I_G(e) should explicitly state whether the supremum is taken over all graphs or only over graphs with edge density exactly e (or in a neighborhood).
  2. [Introduction] The exact determinations at e=(k-1)/k are stated without a reference to the section containing the proof; a forward pointer would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful and constructive report. We address the major comment below.

read point-by-point responses

  1. Referee: [Abstract / flag-algebra proof of local maxima for K_{2,2,1}] Abstract and flag-algebra section: the claim that I_{K_{2,2,1}}(e) has at least two local maxima in (0,1) rests on flag-algebra SDPs producing upper bounds sufficiently tight to detect interior peaks. The manuscript must supply the flag-set size, the numerical precision achieved, explicit error bounds on the SDP value, and an argument showing that any gap between the relaxation and the true inducibility cannot erase the detected local maxima (i.e., that the profile cannot be monotone or boundary-only within the reported precision).

    Authors: We agree that the manuscript requires additional technical details to rigorously certify the interior local maxima via the flag-algebra SDPs. In the revised version we will expand the relevant section (and add an appendix if needed) to report: the flag-set size used, the numerical precision and solver tolerances achieved, explicit error bounds on the SDP values, and a self-contained argument showing that the gap between the SDP relaxation and the true inducibility is smaller than the separation between the detected interior peaks and the boundary values. This will establish that the profile cannot be monotone or boundary-only within the reported precision. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation relies on external theorems and standard flag-algebra method

full rationale

The paper's central claims rest on (1) flag-algebra semidefinite programs, a method introduced by Razborov and external to the authors, and (2) direct invocation of Reiher's clique-density theorem and the Schelp-Thomason symmetrization theorem, both by non-overlapping authors. No self-citation is load-bearing, no fitted parameter is relabeled as a prediction, and no ansatz or uniqueness result is smuggled via prior work by the same team. The derivation chain therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard asymptotic definitions in extremal graph theory and two previously published theorems; no new free parameters or invented entities are introduced.

axioms (1)
  • standard math The limit defining I_G(e) as n tends to infinity exists.
    Invoked in the definition of I_G(e) as a supremum over n-vertex graphs.

pith-pipeline@v0.9.1-grok · 5725 in / 1013 out tokens · 37979 ms · 2026-06-30T20:06:12.943613+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

24 extracted references · 24 canonical work pages · 1 internal anchor

  1. [1]

    Semi-inducibility of some small graphs, 2026.arXiv:2601.03433

    J´ ozsef Balogh, Bernard Lidick´ y, Dhruv Mubayi, Florian Pfender, and Jan Volec. Semi-inducibility of some small graphs, 2026.arXiv:2601.03433

    work page arXiv 2026

  2. [2]

    Minimizing the number of 5- cycles in graphs with given edge-density.Combinatorics, Probability and Computing, 29(1):44–67, 2019

    Patrick Bennett, Andrzej Dudek, Bernard Lidick´ y, and Oleg Pikhurko. Minimizing the number of 5- cycles in graphs with given edge-density.Combinatorics, Probability and Computing, 29(1):44–67, 2019. doi:10.1017/s0963548319000257

    work page doi:10.1017/s0963548319000257 2019

  3. [3]

    Semi-inducibility of 4-vertex graphs

    Levente Bodn´ ar and Oleg Pikhurko. Semi-inducibility of 4-vertex graphs, 2025.arXiv:2510.24336

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  4. [4]

    Some exact inducibility-type results for graphs via flag algebras, 2025.arXiv:2507.01596

    Levente Bodn´ ar and Oleg Pikhurko. Some exact inducibility-type results for graphs via flag algebras, 2025.arXiv:2507.01596

    work page arXiv 2025

  5. [5]

    Bollobás, Y

    B´ ela Bollob´ as, Yoshimi Egawa, Andrew Harris, and Guoping Jin. The maximal number of induced r-partite subgraphs.Graphs and Combinatorics, 11(1):1–19, 1995.doi:10.1007/bf01787417

    work page doi:10.1007/bf01787417 1995

  6. [6]

    Bożyk, A

    Lukasz Bo˙ zyk, Andrzej Grzesik, and Bart lomiej Kielak. On the inducibility of oriented graphs on four vertices.Discrete Mathematics, 345(7):112874, 2022.doi:10.1016/j.disc.2022.112874

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

  7. [7]

    Getting to the root of the problem: Sums of squares for infinite trees, 2024.arXiv:2404.12838

    Daniel Brosch and Diane Puges. Getting to the root of the problem: Sums of squares for infinite trees, 2024.arXiv:2404.12838

    work page arXiv 2024

  8. [8]

    Brown and Alexander Sidorenko

    Jason I. Brown and Alexander Sidorenko. The inducibility of complete bipartite graphs.Journal of Graph Theory, 18(6):629–645, 1994.doi:10.1002/jgt.3190180610

    work page doi:10.1002/jgt.3190180610 1994

  9. [9]

    Hao Chen and Jonathan A. Noel. On alternating 6-cycles in edge-coloured graphs, 2025.arXiv: 2505.09809. 6

    work page arXiv 2025

  10. [10]

    Inducibility of directed paths.Discrete Mathematics, 343(10):112015, 2020.doi:10.1016/j.disc.2020.112015

    Ilkyoo Choi, Bernard Lidick´ y, and Florian Pfender. Inducibility of directed paths.Discrete Mathematics, 343(10):112015, 2020.doi:10.1016/j.disc.2020.112015

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

  11. [11]

    Even-Zohar and N

    Chaim Even-Zohar and Nati Linial. A note on the inducibility of 4-vertex graphs.Graphs and Combi- natorics, 31(5):1367–1380, 2014.doi:10.1007/s00373-014-1475-4

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

  12. [12]

    The codegree threshold ofK − 4

    Victor Falgas-Ravry, Oleg Pikhurko, Emil Vaughan, and Jan Volec. The codegree threshold ofK − 4 . Journal of the London Mathematical Society, 107(5):1660–1691, 2023.doi:10.1112/jlms.12722

    work page doi:10.1112/jlms.12722 2023

  13. [13]

    The four-color Ramsey multiplicity of triangles

    Aldo Kiem, Sebastian Pokutta, and Christoph Spiegel. The four-color Ramsey multiplicity of triangles. InProceedings of the Discrete Mathematics Days, 2024.arXiv:2312.08049

    work page arXiv 2024

  14. [14]

    Lidický, C

    Bernard Lidick´ y, Connor Mattes, and Florian Pfender.C 5 is almost a fractalizer.J. Graph Theory, 104(1):220–244, 2023.doi:10.1002/jgt.22957

    work page doi:10.1002/jgt.22957 2023

  15. [15]

    Stability from graph sym- metrisation arguments with applications to inducibility.Journal of the London Mathematical Society, 108(3):1121–1162, 2023.doi:10.1112/jlms.12777

    Hong Liu, Oleg Pikhurko, Maryam Sharifzadeh, and Katherine Staden. Stability from graph sym- metrisation arguments with applications to inducibility.Journal of the London Mathematical Society, 108(3):1121–1162, 2023.doi:10.1112/jlms.12777

    work page doi:10.1112/jlms.12777 2023

  16. [16]

    The exact minimum number of triangles in graphs with given order and size.Forum Math

    Hong Liu, Oleg Pikhurko, and Katherine Staden. The exact minimum number of triangles in graphs with given order and size.Forum Math. Pi, 8:e8, 144, 2020.doi:10.1017/fmp.2020.7

    work page doi:10.1017/fmp.2020.7 2020

  17. [17]

    The feasible region of induced graphs.J

    Xizhi Liu, Dhruv Mubayi, and Christian Reiher. The feasible region of induced graphs.J. Combin. Theory Ser. B, 158(part 2):105–135, 2023.doi:10.1016/j.jctb.2022.09.003

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

  18. [18]

    Nikiforov

    V. Nikiforov. The number of cliques in graphs of given order and size.Transactions of the American Mathematical Society, 363(3):1599–1618, 2010.doi:10.1090/s0002-9947-2010-05189-x

    work page doi:10.1090/s0002-9947-2010-05189-x 2010

  19. [19]

    Strong forms of stability from flag algebra calculations.Journal of Combinatorial Theory, Series B, 135:129–178, 2019.doi:10.1016/j.jctb

    Oleg Pikhurko, Jakub Sliaˇ can, and Konstantinos Tyros. Strong forms of stability from flag algebra calculations.Journal of Combinatorial Theory, Series B, 135:129–178, 2019.doi:10.1016/j.jctb. 2018.08.001

    work page doi:10.1016/j.jctb 2019

  20. [20]

    Pippenger and M

    Nicholas Pippenger and Martin Charles Golumbic. The inducibility of graphs.Journal of Combinatorial Theory, Series B, 19(3):189–203, 1975.doi:10.1016/0095-8956(75)90084-2

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

  21. [21]

    Razborov

    Alexander A. Razborov. Flag algebras.J. Symbolic Logic, 72(4):1239–1282, 2007.doi:10.2178/jsl/ 1203350785

    work page doi:10.2178/jsl/ 2007

  22. [22]

    Razborov

    Alexander A. Razborov. On the minimal density of triangles in graphs.Combin. Probab. Comput., 17(4):603–618, 2008.doi:10.1017/S0963548308009085

    work page doi:10.1017/s0963548308009085 2008

  23. [23]

    The clique density theorem.Annals of Mathematics, 184(3):683–707, 2016.doi: 10.4007/annals.2016.184.3.1

    Christian Reiher. The clique density theorem.Annals of Mathematics, 184(3):683–707, 2016.doi: 10.4007/annals.2016.184.3.1

    work page doi:10.4007/annals.2016.184.3.1 2016

  24. [24]

    Schelp and Andrew Thomason

    Richard H. Schelp and Andrew Thomason. A remark on the number of complete and empty subgraphs. Combin. Probab. Comput., 7(2):217–219, 1998.doi:10.1017/S0963548397003234. Appendix A The first proof of Theorem 6 wherekis restricted to be an integer we obtained using flag algebras. We include it because it is interesting to see a parametric proof in flag alg...

    work page doi:10.1017/s0963548397003234 1998