Pith. sign in

REVIEW 1 major objections 3 minor 1 cited by

The semi-inducibility problem

T0 review · 1 major / 3 minor · reviewed 2026-08-10 · deepseek-v4-flash

Pith's one-line read A four-vertex quantum graph with positive coefficients has quasirandom graphs as its unique extremal graphs across an entire interval of edge densities.

desk verdict Solid new results on two-colour inducibility, capped by a positive-coefficient quantum graph with quasirandom unique extremals over an interval of densities. read the letter →

arxiv 2501.09842 v2 pith:HHAS23VT submitted 2025-01-16 math.CO

classification math.CO MSC 05C3505C8005C1505C38
keywords semi-inducibilityred-bluegraphsquantumquasirandominducibilityproblemalternatingwalkscycles4-cycles
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper introduces the semi-inducibility problem: given a fixed red-blue graph $H$, how many copies of $H$ can a red-blue complete graph on $n$ vertices contain? It determines this quantity, up to sharp or almost sharp bounds with full extremal characterisations, for alternating walks, for alternating cycles whose length is divisible by four, and for every colour pattern of a 4-cycle. The central claim is that a particular four-vertex quantum graph $Q$ with positive coefficients has the binomial random graph as its unique asymptotic maximiser over the whole interval of edge densities $\sigma\in[1/4(1+\sqrt{2}),1]$. If the paper is right, the recent negative result for single graphs, that a random graph is never a maximiser in the inducibility problem at an interior density, does not extend to positive-coefficient quantum graphs. The proof is elementary and self-contained, using degree and codegree relaxations, stability arguments, and an edge-flip lemma that upgrades almost-partitioned extremal graphs to exactly partitioned ones.

What carries the argument

The load-bearing object is the degree–codegree relaxation for the red graph. Writing $d_i$ for the red degree of vertex $i$ and $z_{ij}$ for the red codegree of a pair, the number of RRRB 4-cycles is $\frac{n^4}{2}f(d,z)+O(n^3)$, where $f(d,z)=n^{-2}\sum_{i<j}z_{ij}(d_i+d_j-2z_{ij})$. The paper maximises $f$ over a relaxed feasible set $S(\sigma)$ consisting of all vectors whose mean degree is $\sigma$ and whose $z$-sums obey the identity $\sum z_{ij}=\frac{n}{2}(\tau n-\sigma)$ with $\tau=n^{-1}\sum d_i^2$. Lemma 7.9 shows that for $\sigma\geq\frac14(1+\sqrt{2})$ the maximum is $\sigma^3(1-\sigma)$, and any near-maximiser has almost all $z_{ij}$ within $o(n)$ of $\sigma^2 n$, which through the standard quasirandom equivalence forces the whole graph to be quasirandom. For the bipartite results, the analogous mechanism is Lemma 3.11, whose canonical inequality $p_H(\alpha,\beta)\leq h-\eta/2$ controls how few copies of $H$ can use a minority edge in an almost-partitioned host; the edge-flip argument then rules out all minority edges and forces an exact partition.

What would settle it

Fix $\sigma=\frac14(1+\sqrt{2})$ and build, for infinitely many $n$, red-blue complete graphs whose red graph is $\sigma n$-regular but whose red codegrees are not concentrated: for some fixed $c>0$, a positive proportion of pairs have codegree $(\sigma^2+c)n$ and a positive proportion have codegree $(\sigma^2-c)n$, while the identity relating degrees and codegrees is maintained. If the number of RRRB 4-cycles in any such graph equals $\frac12\sigma^3(1-\sigma)n^4+o(n^4)$, the quasirandom-uniqueness assertion of Theorem 2.7 is false; the theorem predicts that every such near-maximiser has codegrees concentrated around $\sigma^2 n$.

Watch

Extended reading notes

Core claim

The paper proves Theorem 2.6: for the four-vertex quantum graph $Q$ defined in the paper, $I(Q,\sigma)=\mathrm{rand}(Q,\sigma)$ for every $\sigma\in[1/4(1+\sqrt{2}),1]$, and $I(Q)=\sup_{\sigma\in[0,1]}\mathrm{rand}(Q,\sigma)=\mathrm{rand}(Q,3/4)$. Moreover, for any $\delta<10^{-6}$, any $n$-vertex graph $J$ with density $\sigma$ and $I(Q,J)>(\mathrm{rand}(Q,\sigma)-\delta)\binom{n}{4}$ must be $(3\delta^{1/8})$-quasirandom of density $\sigma$. In other words, over a continuum of densities, the only near-extremal graphs are quasirandom ones, which is an interval version of random-graph uniqueness for a quantum graph with positive coefficients. The paper also establishes companion results for individual red-blue graphs: alternating walks of length $t$ are bounded by $2n((n-1)/2)^t$, alternating $4t$-cycles are maximised exactly, for large $n$, by a balanced bipartite colouring, and RRRB 4-cycles are maximised at $\frac{27}{512}n^4+O(n^3)$ with all near-maximisers quasirandom of density $3/4$.

Load-bearing premise

The exact if-and-only-if results all pass through Lemma 3.11, whose proof assumes that the canonical inequality $p_H(\alpha,\beta)\leq h-\eta/2$ holds uniformly for all small parameters and all vertex proportions in the stated range; if that inequality failed on a set of vertices of density $o(1)$, the conclusion that an extremal graph is exactly partitioned would weaken to 'almost partitioned'.

Editorial extensions

If this is right

  • For every $\sigma\in[\frac14(1+\sqrt{2}),1]$, the binomial random graph $G(n,\sigma)$ is asymptotically extremal for $Q$, and any sequence of graphs performing as well must be quasirandom of density $\sigma$.
  • The maximum induced $Q$-density is attained at $\sigma=3/4$ and equals $\frac{27}{512}n^4+O(n^3)$, giving the random-graph value of $Q$ at that density.
  • Alternating 4-cycles and alternating $4t$-cycles are maximised, for large $n$, only by colourings in which one colour induces a balanced complete bipartite graph, so the extremal host is unique for these subgraphs.
  • RRBB 4-cycles have a different unique extremal shape: one colour induces a complete bipartite graph whose part sizes differ by $\Theta(\sqrt{n})$, so the extremal graph is deliberately unbalanced.
  • Together, the results determine the semi-inducibility problem for every red-blue 4-cycle colour pattern, with the RRRB case providing the quasirandom phenomenon at the core of the paper.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The threshold $\frac14(1+\sqrt{2})$ arises as the point where the unconstrained quadratic maximiser of the relaxation leaves the feasible region; this suggests that below the threshold the extremal structure changes, and a finite-dimensional optimisation of the same relaxed problem would indicate whether quasirandom graphs stop being extremal there.
  • The degree–codegree relaxation is not tied to 4-cycles: the same scheme could be applied to other fixed colour patterns, and any new interval of densities with a quasirandom unique maximiser would be detected by the same analytic stability argument.
  • The result also suggests a directed analogue: a 4-vertex tournament or directed quantum graph could have a quasirandom tournament as its unique extremal object, which would settle the open problem in that setting in a way parallel to Theorem 2.6.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 3 minor

Summary. The paper defines the semi-inducibility problem: given a red-blue graph H, maximize the number of copies of H in a red-blue complete graph on n vertices. The authors prove sharp or nearly sharp bounds for alternating walks (Theorem 1.3), alternating cycles of length divisible by 4 (Theorems 1.5 and 1.6), and for every colour pattern of a 4-cycle (Theorems 1.6, 1.7, and 1.9). They also determine the extremal graphs for several red-blue K1,1,2 graphs (Section 8). The central new contribution is Theorem 2.6, which exhibits a quantum graph Q with positive coefficients and an interval of edge densities on which the binomial random graph is asymptotically extremal and, moreover, is the unique near-extremal graph up to quasirandomness. This contrasts with the recent negative result of Jain, Michelen, and Wei for single graphs, and it is derived from the density version Theorem 2.7 for RRRB-cycles via the identity #(RRRB, G_J) = I(Q,J).

Significance. If the results are correct, this is a substantial contribution to extremal graph theory. The paper introduces a natural generalization of the inducibility problem and solves it for several families of small graphs, with elementary methods rather than flag algebras. The most notable result, Theorem 2.6, is the first example of a positive-coefficient quantum graph for which random graphs are uniquely extremal over an entire interval of densities, in striking contrast to the single-graph case settled negatively in [28]. The proofs are detailed, largely self-contained, and include explicit stability statements with quantifiable quasirandomness bounds. The reliance on two external results by overlapping authors ([11, Lemma 3.2] and [31, Theorem 1.1]) is clearly indicated and does not undermine the novelty.

major comments (1)
  1. [Section 3.4, Lemma 3.11] The proof of Lemma 3.11 mixes labelled and unlabelled copies of H in a way that makes equation (5) inconsistent. The set D_x is defined as labelled copies of H containing x, but Lemma 3.3 and #(H,G) concern unlabelled copies. To pass from the bound |D_x| ≤ (1/2−6δ)^{h−1}(h−η/3)n^{h−1} to an upper bound on #(H,G), one must divide by |Aut(H)|, giving an extra factor in (5). Similarly, the lower bound on the number of copies in the flipped graph G* is stated as h(1/2−5δ)^{h−1}n^h labelled copies, but converting to unlabelled copies introduces another factor of |Aut(H)| (and the text also appears to omit a factor 1/h in the total count). These two corrections cancel, so the intended contradiction is valid, but as written the proof is not internally consistent. Since Lemma 3.11 is used to derive the exact extremal characterizations in Theorems 1.5, 1.7, and Section 8.1, this needs to be fixed or clarified.
minor comments (3)
  1. [Section 7.2, Theorem 2.6] The identity (33) is stated without a full proof; the phrase 'there are two, two and one ways respectively to make a 4-cycle with one missing edge' is too terse, especially since the pictures are not reproducible in text. I recommend adding a short explicit explanation: for each copy of an RRRB-cycle in G_J, the two diagonals of the K4 give two completions to a K1,1,2, and the count of such completions over the three patterns yields the factor 2, 2, 1. This would make the derivation of I(Q,σ)=rand(Q,σ) easier to verify.
  2. [Section 3.4, Lemma 3.11] The proof of Lemma 3.11 also contains a minor arithmetic slip in the sentence 'the total number of labelled copies of H in G* is at least h(1/2−5δ)^{h−1}n^h'; since there are n vertices each contributing at least h(1/2−5δ)^{h−1}n^{h−1} copies, the total should be (1/2−5δ)^{h−1}n^h times a factor of h/|Aut(H)| when converted. This is part of the labelled/unlabelled issue raised above.
  3. [Section 1, Table 1.1] In the table's row for alternating 4t-cycles, the entry '1/t · 2^{4t+1}' may confuse readers because it is not enclosed in a formula environment; writing 1/(t·2^{4t+1}) would be clearer.

Circularity Check

0 steps flagged · score 0.0 of 10

Central quasirandom-extremality theorem is proved self-containedly; no circular step identified.

full rationale

The central claim (Theorem 2.6) is derived from Theorem 2.7, whose proof in Section 7.2 is self-contained: Lemma 7.6 expresses #(RRRB,G) as (n^4/2)f(d,z)+O(n^3) for the true degree–codegree vector, which lies in S(σ); the upper bound is obtained by maximizing f over this superset S(σ) (Lemmas 7.7–7.9), with no assumption that the random graph is extremal. The matching lower bound is the standard random-graph evaluation rand(Q,σ)=12σ^3(1−σ), so I(Q,σ)=rand(Q,σ) is an equality proved from both sides rather than an input. The quasirandom stability conclusion follows from the same relaxation: if f is δ-close to σ^3(1−σ), then z_ij is forced close to σ^2 via Lemma 7.9, an algebraic consequence of the optimization rather than a restatement of the definition of quasirandom. The quoted self-citations (Lemma 3.7 from [11]; Theorem 8.2 from [31]) do not appear in the proof of Theorem 2.7; they support the peripheral alternating-cycle/RRBB and K1,1,2 results and are external results with proofs elsewhere. I find no step where a prediction is equivalent by construction to a fitted parameter or to the target statement.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

Nothing in the paper is fitted to data and no new physical or combinatorial objects beyond definitions are postulated. The proofs rest on standard inequalities, two external theorems (one on symmetrisation with overlapping authorship, one on bipartite stability), and the quasirandom equivalence theorem. These are all independent published results, not restatements of the paper's claims.

assumptions (4)
  • standard math Standard inequalities (Cauchy-Schwarz, AM-GM, Jensen) apply to real-valued sums over vertices.
    Invoked throughout, e.g., Section 3.3 and in the proof of Theorem 1.3 (equations (7)-(11)).
  • domain assumption The Chung-Graham-Wilson theorem characterizes quasirandom graphs via codegree sums (Definition 1.8).
    Used in Theorem 1.9 and Theorem 2.7 to convert sum-of-codegrees estimates into quasirandomness of the red graph; cited as [12].
  • domain assumption The symmetrisation stability theorem of Liu-Pikhurko-Sharifzadeh-Staden [31, Theorem 1.1] is applicable to the quantum graph Q in Section 8.2, and the associated 'strictness' conditions (S1) and (S2) hold for the tripartite Turán graph.
    Used to prove Theorem 8.1 (red-blue K_{1,1,2}); the paper verifies (S1) and (S2) in the proof of Theorem 8.1, but the theorem itself is external.
  • domain assumption The Cheng-Staden bipartite lemma [11, Lemma 3.2], stated here as Lemma 3.7, correctly identifies red-blue graphs with most degrees near n/2 and a sparse cut as close to bipartite.
    Used in the stability proofs of Theorem 6.1 and Lemma 7.1; cited as [11].

how reviews work

0 comments
Cite this review

Pith. "Pith review of The semi-inducibility problem." pith.science (2026). https://pith.science/paper/HHAS23VT

@misc{pith2026250109842,
  author       = {Pith},
  title        = {Pith review of: The semi-inducibility problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HHAS23VT}},
  note         = {Machine review of arXiv:2501.09842}
}
abstract

Let $H$ be a $k$-edge-coloured graph and let $n$ be a positive integer. What is the maximum number of copies of $H$ in a $k$-edge-coloured complete graph on $n$ vertices? This paper studies the case $k=2$, which we call the semi-inducibility problem. This problem is a generalisation of the inducibility problem of Pippenger and Golumbic which is solved only for some small graphs and limited families of graphs. We prove sharp or almost sharp results for alternating walks, for alternating cycles of length divisible by 4, and for 4-cycles of every colour pattern. Liu, Mubayi and Reiher asked whether there is a graph $F$ for which the binomial random graph is an asymptotically extremal graph in the inducibility problem over all graphs of a given edge density. This was recently answered in a strong negative sense by Jain, Michelen and Wei. In contrast, we find a \emph{quantum} graph $Q$ with positive coefficients and an interval of edge densities for which the only extremal graphs are quasirandom.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

  1. The semi-inducibility of the blue--blue--red path on four vertices

    math.CO 2026-07 accept novelty 7.0 of 10

    The maximum asymptotic density of semi-induced blue-blue-red paths on four vertices is p*, attained by a large clique together with an asymptotically regular component.

Reference graph

Works this paper leans on

46 extracted references · 43 canonical work pages · cited by 1 Pith paper

  1. [28]

    V. Jain, M. Michelen, and F. Wei. The binomial random graph is a bad inducer. arXiv preprint arXiv:2306.13014, 2023. THE SEMI-INDUCIBILITY PROBLEM 45

  2. [1]

    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. Europ. J. Combin. , 52:47–58, 2016

  3. [2]

    Balogh, P

    J. Balogh, P. Hu, B. Lidick´ y, F. Pfender, J. Volec, and M. Young. Rainbow triangles in three-colored graphs. J. Combin. Theory B , 126:83–113, 2017

  4. [3]

    Bollob´ as

    B. Bollob´ as. On complete subgraphs of different orders. Math. Proc. Camb. Phil. Soc. , 79:19–24, 1976

  5. [4]

    Bollob´ as, Y

    B. Bollob´ as, Y. Egawa, A. Harris, and G. Jin. The maximal number of induced r-partite subgraphs. Graphs Combin., 11:1–19, 1995

  6. [5]

    Bollob´ as, C

    B. Bollob´ as, C. Nara, and S. Tachibana. The maximal number of induced complete bipartite graphs. Disc. Math., 62(3):271 – 275, 1986

  7. [6]

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

  8. [7]

    Burke, B

    D. Burke, B. Lidick` y, F. Pfender, and M. Phillips. Inducibility of 4-vertex tournaments. arXiv preprint arXiv:2103.07047, 2021

Show all 46 references
  1. [8]

    S. A. Burr and V. Rosta. On the Ramsey multiplicities of graphs – problems and recent results. J. Graph Theory, 4(4):347–361, 1980

  2. [9]

    Cairncross, C

    E. Cairncross, C. Mizgerd, and D. Mubayi. Inducibility of rainbow graphs. arXiv preprint arXiv:2405.03112, 2024

  3. [10]

    Cairncross and D

    E. Cairncross and D. Mubayi. Ordered and colored subgraph density problems. arXiv preprint arXiv:2403.12016 , 2024

  4. [11]

    Cheng and K

    Y. Cheng and K. Staden. Stability of transversal Hamilton cycles and paths. arXiv preprint arXiv:2403.09913 , 2024

  5. [12]

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

  6. [13]

    Cummings, D

    J. Cummings, D. Kr´ al’, F. Pfender, K. Sperfeld, A. Treglown, and M. Young. Monochromatic triangles in three- coloured graphs. J. Combin. Theory B , 103(4):489–503, 2013

  7. [14]

    Cummings and M

    J. Cummings and M. Young. Graphs containing triangles are not 3-common. J. Combin. , 2(1):1–14, 2011

  8. [15]

    De Silva, X

    J. De Silva, X. Si, M. Tait, Y. Tun¸ cbilek, R. Yang, and M. Young. Anti-Ramsey multiplicities. arXiv preprint arXiv:1801.00474, 2018

  9. [16]

    P. Erd˝ os. On the number of complete subgraphs contained in certain graphs.Magyar Tud. Akad. Mat. Kutat´ o Int. K¨ ozl, 7(3):459–464, 1962

  10. [17]

    Erd˝ os and A

    P. Erd˝ os and A. Hajnal. On Ramsey like theorems. Problems and results. In Combinatorics (Proc. Conf. Combi- natorial Math., Math. Inst., Oxford, 1972) , pages 123–140, 1972

  11. [18]

    Erd˝ os and A

    P. Erd˝ os and A. H. Stone. On the structure of linear graphs. Bull. Amer. Math. Soc. , 1946

  12. [19]

    Even-Zohar and N

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

  13. [20]

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

  14. [21]

    J. Fox, L. Sauermann, and F. Wei. On the inducibility problem for random Cayley graphs of abelian groups with a few deleted vertices. Random Struct. Algor. , 59(4):554–615, 2021

  15. [22]

    Frieze and M

    A. Frieze and M. Karo´ nski.Introduction to Random Graphs . Cambridge, 2016

  16. [23]

    A. W. Goodman. On sets of acquaintances and strangers at any party. Amer. Math. Monthly, 66(9):778–783, 1959

  17. [24]

    Hatami, J

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

  18. [25]

    Hefetz and M

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

  19. [26]

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

  20. [27]

    P. Hu, J. Ma, S. Norin, and H. Wu. Inducibility of oriented stars. arXiv:2008.05430

  21. [29]

    Keevash, M

    P. Keevash, M. Saks, B. Sudakov, and J. Verstra¨ ete. Multicolour Tur´ an problems.Adv. Applied Math., 33(2):238– 262, 2004

  22. [30]

    Lidick´ y, C

    B. Lidick´ y, C. Mattes, and F. Pfender. C5 is almost a fractalizer. J. Graph Theory , 104(1):220–244, 2023

  23. [31]

    H. Liu, O. Pikhurko, M. Sharifzadeh, and K. Staden. Stability from graph symmetrisation arguments with appli- cations to inducibility. J. London Math. Soc. , 108(3):1121–1162, 2023

  24. [32]

    X. Liu, D. Mubayi, and C. Reiher. The feasible region of induced graphs. J. Combin. Theory B , 158:105–135, 2023

  25. [33]

    Mubayi and A

    D. Mubayi and A. Razborov. Polynomial to exponential transition in Ramsey theory. Proc. London Math. Soc. , 122(1):69–92, 2021

  26. [34]

    Pikhurko, J

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

  27. [35]

    Pippenger and M

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

  28. [36]

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

  29. [37]

    A. Sah, M. Sawhney, and Y. Zhao. Paths of given length in tournaments. Combin. Theory, 3(2), 2023

  30. [38]

    R. H. Schelp and A. G. Thomason. A remark on the number of complete and empty subgraphs. Combin. Probab. Comput., 7:217–220, 1998

  31. [39]

    A. F. Sidorenko. Cycles in graphs and functional inequalities. Mathematical Notes of the Academy of Sciences of the USSR , 46:877–882, 1989

  32. [40]

    A. F. Sidorenko. A correlation inequality for bipartite graphs. Graphs Combin., 9:201–204, 1993

  33. [41]

    Simonovits

    M. Simonovits. Extremal graph problems, degenerate extremal problems, and supersaturated graphs. Progress in graph theory (Waterloo, Ont., 1982) , pages 419–437, 1984

  34. [42]

    Thomason

    A. Thomason. A disproof of a conjecture of Erd˝ os in Ramsey theory. J. London Math. Soc. , 2(2):246–255, 1989

  35. [43]

    Thomason

    A. Thomason. Graph products and monochromatic multiplicities. Combinatorica, 17:125–134, 1997

  36. [44]

    P. Tur´ an. On an extremal problem in graph theory.Mat. Fiz. Lapok , 48:436–452, 1941

  37. [45]

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

  38. [46]

    A. Zykov. On some properties of linear complexes. Matematiˇ ceski ˘ ı Sbornik N.s., 24(66):163–188, 1949

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.