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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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$.
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
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [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)
- [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.
- [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.
- [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
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
assumptions (4)
- standard math Standard inequalities (Cauchy-Schwarz, AM-GM, Jensen) apply to real-valued sums over vertices.
- domain assumption The Chung-Graham-Wilson theorem characterizes quasirandom graphs via codegree sums (Definition 1.8).
- 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.
- 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.
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.
Forward citations
Cited by 1 Pith paper
-
The semi-inducibility of the blue--blue--red path on four vertices
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
-
[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
work page Pith review arXiv 2023
- [1]
- [2]
-
[3]
B. Bollob´ as. On complete subgraphs of different orders. Math. Proc. Camb. Phil. Soc. , 79:19–24, 1976
work page 1976
-
[4]
B. Bollob´ as, Y. Egawa, A. Harris, and G. Jin. The maximal number of induced r-partite subgraphs. Graphs Combin., 11:1–19, 1995
work page 1995
-
[5]
B. Bollob´ as, C. Nara, and S. Tachibana. The maximal number of induced complete bipartite graphs. Disc. Math., 62(3):271 – 275, 1986
work page 1986
-
[6]
J. I. Brown and A. Sidorenko. The inducibility of complete bipartite graphs. J. Graph Theory , 18:629–645, 1994
work page 1994
- [7]
Show all 46 references
-
[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
1980
-
[9]
Cairncross, C
E. Cairncross, C. Mizgerd, and D. Mubayi. Inducibility of rainbow graphs. arXiv preprint arXiv:2405.03112, 2024
2024
-
[10]
Cairncross and D
E. Cairncross and D. Mubayi. Ordered and colored subgraph density problems. arXiv preprint arXiv:2403.12016 , 2024
2024 arXiv
-
[11]
Cheng and K
Y. Cheng and K. Staden. Stability of transversal Hamilton cycles and paths. arXiv preprint arXiv:2403.09913 , 2024
2024 arXiv
-
[12]
F. R. K. Chung, R. L. Graham, and R. M. Wilson. Quasi-random graphs. Combinatorica, 9:345–362, 1989
1989
-
[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
2013
-
[14]
Cummings and M
J. Cummings and M. Young. Graphs containing triangles are not 3-common. J. Combin. , 2(1):1–14, 2011
2011
-
[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
2018 arXiv
-
[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
1962
-
[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
1972
-
[18]
Erd˝ os and A
P. Erd˝ os and A. H. Stone. On the structure of linear graphs. Bull. Amer. Math. Soc. , 1946
1946
-
[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
2015
-
[20]
J. Fox, H. Huang, and C. Lee. A solution to the inducibility problem for almost all graphs. manuscript
-
[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
2021
-
[22]
Frieze and M
A. Frieze and M. Karo´ nski.Introduction to Random Graphs . Cambridge, 2016
2016
-
[23]
A. W. Goodman. On sets of acquaintances and strangers at any party. Amer. Math. Monthly, 66(9):778–783, 1959
1959
-
[24]
Hatami, J
H. Hatami, J. Hirst, and S. Norin. The inducibility of blow-up graphs. J. Combin. Theory B , 109:196 – 212, 2014
2014
-
[25]
Hefetz and M
D. Hefetz and M. Tyomkyn. On the inducibility of cycles. J. Combin. Theory B , 133:243 – 258, 2018
2018
-
[26]
J. Hirst. The inducibility of graphs on four vertices. J. Graph Theory , 75:231–243, 2014
2014
-
[27]
P. Hu, J. Ma, S. Norin, and H. Wu. Inducibility of oriented stars. arXiv:2008.05430
2008 arXiv
-
[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
2004
-
[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
2023
-
[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
2023
-
[32]
X. Liu, D. Mubayi, and C. Reiher. The feasible region of induced graphs. J. Combin. Theory B , 158:105–135, 2023
2023
-
[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
2021
-
[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
2019
-
[35]
Pippenger and M
N. Pippenger and M. C. Golumbic. The inducibility of graphs. J. Combin. Theory B , 19:189–203, 1975
1975
-
[36]
A. A. Razborov. Flag algebras. J. Symbolic Logic, 72(4):1239–1282, 2007
2007
-
[37]
A. Sah, M. Sawhney, and Y. Zhao. Paths of given length in tournaments. Combin. Theory, 3(2), 2023
2023
-
[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
1998
-
[39]
A. F. Sidorenko. Cycles in graphs and functional inequalities. Mathematical Notes of the Academy of Sciences of the USSR , 46:877–882, 1989
1989
-
[40]
A. F. Sidorenko. A correlation inequality for bipartite graphs. Graphs Combin., 9:201–204, 1993
1993
-
[41]
Simonovits
M. Simonovits. Extremal graph problems, degenerate extremal problems, and supersaturated graphs. Progress in graph theory (Waterloo, Ont., 1982) , pages 419–437, 1984
1982
-
[42]
Thomason
A. Thomason. A disproof of a conjecture of Erd˝ os in Ramsey theory. J. London Math. Soc. , 2(2):246–255, 1989
1989
-
[43]
Thomason
A. Thomason. Graph products and monochromatic multiplicities. Combinatorica, 17:125–134, 1997
1997
-
[44]
P. Tur´ an. On an extremal problem in graph theory.Mat. Fiz. Lapok , 48:436–452, 1941
1941
-
[45]
R. Yuster. On the exact maximum induced density of almost all graphs and their inducibility. J. Combin. Theory B, 136:81 – 109, 2019
2019
-
[46]
A. Zykov. On some properties of linear complexes. Matematiˇ ceski ˘ ı Sbornik N.s., 24(66):163–188, 1949
1949
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.