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

Jinghua Deng

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

T0 review · 0 major / 5 minor · reviewed 2026-07-31 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper determines the exact maximum limiting density of semi-induced blue–blue–red paths on four vertices, resolving the last open four-vertex case.

desk verdict This paper really does settle the last open four-vertex semi-inducibility case, and the proof, though long and intricate, appears sound. read the letter →

arxiv 2607.27911 v1 pith:FUUMMAC4 submitted 2026-07-30 math.CO

Jinghua Deng This is my paper · ORCID

classification math.CO MSC 05C35

keywords semi-inducibilityinducibilityred-bluegraphsgraphonlimitsextremalgraphtheoryfour-vertexblue-blue-redpathdegreequotient

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 resolves the exceptional four-vertex case left open in the classification of non-complete red-blue graphs: the semi-induced blue–blue–red path H3. It proves that the maximum limiting density of semi-induced copies in an n-vertex graph is an explicit algebraic number p*, obtained by evaluating a two-variable function F at a distinguished point (a*, x*). Here x* is the unique root in (0, 1/4) of a cubic polynomial, and a* is given by a rational expression in x*. The extremal construction is a disjoint union of a clique of relative size a* and an asymptotically regular graph of relative degree x*. A structural theorem shows that, after a degree-square tie-breaking, every extremal graphon has essentially this split form, reducing the infinite-dimensional maximization to a two-variable calculus check.

What carries the argument

The central machinery is the degree quotient combined with a degree-square tie-break. The functional Φ(W) measures weighted H3 density and can be written as β(1-β) - ∫ψ(d) - E_W(d) in terms of the red degree function d. For any quotient W^P that merges degree information, Lemma 4.3 shows that a nontrivial quotient strictly decreases Φ whenever the chosen maximizer also minimizes D(W) = ||d||²₂; equality would produce a second maximizer with smaller D. This strictness forces the degree distribution of an extremal graphon into a single high-degree atom A of weight > 1/2 that is a clique, with a low-degree remainder, collapsing the problem to the two-variable family F(a,x) and its convex-envelo

What would settle it

Evaluate the normalized semi-induced H3 count of the proposed construction for large n—a clique of size a*n disjoint from a regular graph of degree x*n—and compare with p*; any asymptotic excess would refute the upper bound. A direct computer search over small step graphons for Φ > p* would also disprove the theorem.

Watch

Extended reading notes

Core claim

Theorem 1.1 states that I(H3) = p*, where p* = F(a*, x*), x* is the unique root of 32x^3 - 40x^2 + 13x - 1 = 0 in (0, 1/4), and a* = (4x*^2 - 7x* + 2)/(3 - 8x*). Equality is attained by graphs of the form K_{(a*+o(1))n} ⊔ R_n, where R_n is asymptotically regular with every vertex of degree (x*+o(1))n, equivalently relative degree λ*+o(1) inside R_n. The proof works with graphon limits and shows that a maximizer chosen to minimize the degree-square functional must have a clique A of weight > 1/2, no edges between A and its complement, and degree at most 1/2 on the complement. This split structure turns the upper bound into the two-variable inequality F0(a,x) ≤ p*, proved by calculus and conve

Load-bearing premise

The load-bearing premise is Lemma 4.3: for a chosen maximizer that minimizes the degree-square functional, every nontrivial degree quotient strictly decreases the objective; if equality ever occurred, the proof could not force the clique-plus-low-degree split.

Editorial extensions

If this is right

The exceptional four-vertex red-blue graph is now settled, completing the classification of semi-inducibility for all non-complete red-blue graphs on four vertices.
The tie-break argument produces an extremal graphon of a forced split form: a clique of weight > 1/2 plus a remainder whose degrees are at most 1/2.
The upper-bound proof reduces to the explicit inequality F0(a,x) ≤ p*, so any graph's H3-density is controlled by a two-parameter degree summary.
The lower-bound construction is simple and explicit at every n—a clique and a cyclic regular graph—showing the bound is asymptotically sharp.

Reading between the lines

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

The degree-square tie-breaking device is likely transferable to other semi-inducibility problems: it converts an infinite-dimensional graphon maximization into a one-dimensional degree analysis whenever degree quotients preserve the objective and the tie-break forces strictness.
One can probe the same problem with a prescribed red-edge density by maximizing F(a,x) under the constraint β(a,x) = c; the explicit formulas here suggest a piecewise algebraic density profile with a phase change near the boundary of the split-regular region.
A computer search over small step graphons could independently test p*: a step graphon with Φ > p* would expose a gap in the quotient argument, while agreement would corroborate the exact value.
The structural dichotomy—either a majority clique atom exists or the density is bounded below 3/20—may generalize to other red-blue trees with a blue prefix path, since the same half-slope inequality (57) governs the high-degree rows.

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.

Desk Editor's Note

read the letter

What you should know: this is the missing four-vertex case, blue–blue–red path H3, and the paper gives the exact value I(H3) = p*, with a clean extremal construction: a clique disjoint from a regular graph. The result closes the Bodnár–Pikhurko classification, so it's a real milestone for the area.

The method is the real news: choose a maximizer that minimizes the degree-square functional D(W), then show any nontrivial degree quotient must strictly decrease Φ. That degree-square tie-breaking plus the half-slope inequality (Lemma 4.5) is a genuinely reusable idea, not a one-off computation. The lower bound is simple and exact; the upper bound is a long but explicit chain. I went through the quotient lemmas (4.2, 4.3), the degree-atomization, and the final small-atom/majority estimates. Everything checks out. The constants x* and a* come from solving the calculus problem, not from fitting the construction, so there's no circularity. The citation pattern is normal; the exceptional case is properly attributed to Bodnár and Pikhurko.

The soft spots are the usual ones for a proof this size. Section 4 is delicate: the measure-theoretic passages (Lebesgue–Besicovitch differentiation, quotient sigma-algebras, coupling to the degree distribution) and the two big polynomial estimates in Lemmas 4.14 and 4.15. I spot-checked the Bernstein expansions (eqs. 114 and 144) and they're correct, but these are exactly the places where a sign error could hide. The paper states it used AI for proof checking and exposition. I don't read that as disqualifying—the arguments are specific and verifiable—but it is another reason to want a careful human referee rather than a quick acceptance.

Who is this for? Extremal graph theorists working on inducibility and semi-inducibility. It deserves a serious referee. I'd send it to someone comfortable with graphon variational arguments and ask them to focus on Section 4.4–4.6, especially the polynomial identities and the measure-theoretic reductions. My own verdict: accept, with moderate-to-high confidence.

Referee Report

0 major / 5 minor

Summary. The paper determines the exact semi-inducibility constant for the four-vertex red-blue path H3 with edge colors blue–blue–red. It proves that I(H3)=p*, where x* is the unique root in (0,1/4) of 32x^3-40x^2+13x-1=0, a*=(4x*^2-7x*+2)/(3-8x*), and p*=F(a*,x*); equality is attained by a graph sequence of the form K_{(a*+o(1))n} ⊔ R_n with R_n asymptotically regular. The proof uses graphon compactness, a degree-square-minimizing maximizer, weighted vertex quotients, KKT-style edge perturbations, and a structural reduction to a clique joined to a low-degree part. The final upper bound is reduced to a two-variable optimization, which is solved exactly with explicit polynomial and Bernstein identities.

Significance. This resolves the last open four-vertex case from the Bodnár–Pikhurko classification of non-complete red-blue graphs, giving a new exact semi-inducibility value. The method is of independent interest: the degree-square tie-breaking among maximizers, the half-slope inequality, and the atomization argument form a coherent and largely self-contained structural toolkit. The lower-bound construction is explicit, and the upper-bound proof is independent of it; the analytic estimates are supported by concrete Bernstein expansions. I see no circularity or parameter fitting. If the proof is correct, this is a valuable contribution to the semi-inducibility literature.

minor comments (5)

[§4.1 (notation)] The symbol A is used both for the σ-algebra σ(d) in (45) and later for the clique vertex set in Theorem 4.12 and Theorem 4.1. This overload makes the structural section harder to read; consider using a script letter or Σ for the σ-algebra.
[Lemma 4.5] In the non-atomic part, the transition from Lebesgue–Besicovitch differentiation to the choice of radii satisfying the small L1 condition and then to (60) is compressed. A sentence stating that at a µ-Lebesgue point one first makes the normalized L1 error < η_k^2 and then applies Markov would help.
[Lemma 4.14] The argument from (104) to (106) is terse where R_a crosses from positive to nonpositive. It is correct, but the reader must infer that when R≤0 the bound comes directly from U≤U0≤153/1024, and when R_a remains positive the maximum is V(1/2)=F_aux. Expanding this by a few lines would improve readability.
[Lemma 4.15] The sign checks in (138) and (145)–(146) are correct, but the connection between the interval [1/2,1/√2] and the Bernstein variable t∈[0,1] is stated only implicitly; make explicit that the relevant t-range is a subinterval.
[§4.1] The line 'Put d(x,y):=(d(x),d(y))' after (46) is unused; it can be deleted.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: upper bound and lower bound are independently established.

full rationale

The derivation is self-contained. The upper bound (Theorem 1.1 via Lemma 2.3, Theorem 4.1, Lemmas 4.14/4.15, and eq. (152)) establishes Φ(W) ≤ p* for every graphon W, where p* is defined independently through the polynomial system (3)–(4). The lower bound is an explicit construction K_{a*n} ⊔ R_n evaluated at (a*, x*) (eq. (153) and Section 5), not a parameter fitted to match the upper bound. The structural reduction rests on Lemma 4.2–4.3, which derives strict decrease of Φ under nontrivial degree quotients from the D-minimizing choice of maximizer; this is an internally proved tie-breaking argument, not an imported uniqueness theorem. Lemma 4.5 derives the half-slope inequality from local quotient perturbations and Lebesgue differentiation, not from the target equality. Lemmas 3.3 and 3.4 solve the two-variable optimization independently of the structural theorem. The only self-citation, [DH26] in the introduction, is contextual and not used in any proof. No equation in the paper reduces to an assumed answer; in particular, (49)–(50) plus (53) are derived identities, not renamed predictions. No limitation or missing-support passages affecting circularity were found.

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

No data-fitted constants: x* is the unique root of a cubic, and a*, p* are explicit functions of x*. The optimization variables a and x define the extremal family and are not fitted to external data. The proof relies only on standard graph-limit and real-analysis background; no new entities are postulated.

assumptions (3)

standard math Graphon compactness and cut-continuity of finite homomorphism densities.
Used in Lemma 2.3 and Section 4 to pass from finite graphs to a maximizer and to choose a degree-square minimizer.
standard math Fubini's theorem, Jensen's inequality, and Lebesgue-Besicovitch differentiation for finite Borel measures.
Used for the integral identities in Lemma 2.4, the convex-envelope bounds in Sections 3 and 4.5, and the a.e. half-slope inequality in Lemma 4.5.
domain assumption The semi-induced density extends to graphons and the finite-graph value differs by O(1/n) (Lemma 2.3).
This is proved via inclusion-exclusion and Lovász-Szegedy convergence but is the formal bridge between the discrete problem and the graphon optimization.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The semi-inducibility of the blue--blue--red path on four vertices." pith.science (2026). https://pith.science/paper/FUUMMAC4

@misc{pith2026260727911,
  author       = {Pith},
  title        = {Pith review of: The semi-inducibility of the blue--blue--red path on four vertices},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FUUMMAC4}},
  note         = {Machine review of arXiv:2607.27911}
}

abstract

For an $n$-vertex graph $G$, let $N(H_3,G)$ be the number of injective labeled copies of the red-blue path $H_3$ for which the two blue pairs are mapped to non-edges of $G$ and the red pair is mapped to an edge of $G$. We determine the maximum limiting value of $N(H_3,G)/n^4$ and give an extremal construction, which is the disjoint union of a clique and an asymptotically regular graph. The proof uses weighted vertex quotients and degree-square tie-breaking. We thereby resolve the exceptional four-vertex case left open in the recent classification of non-complete red-blue graphs.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 4 linked inside Pith

[1]

Balogh, B

J. Balogh, B. Lidick\'y, D. Mubayi, F. Pfender, and J. Volec, Semi-inducibility of some small graphs, arXiv:2601.03433, 2026

arXiv 2026
[2]

Basit, B

A. Basit, B. Granet, D. Horsley, A. K\"undgen, and K. Staden, The semi-inducibility problem, arXiv:2501.09842, 2025

arXiv 2025
[3]

Bodn\'ar, J

L. Bodn\'ar, J. Gao, J. Le\'on, X. Liu, O. Pikhurko, and S. Sun, The inducibility of 6-vertex graphs, arXiv:2606.00290, 2026

arXiv 2026
[4]

Bodn\'ar and O

L. Bodn\'ar and O. Pikhurko, Semi-inducibility of 4-vertex graphs, Discrete Appl. Math. 392 (2026), 303--323

2026
[5]

Bodn\'ar and O

L. Bodn\'ar and O. Pikhurko, Some exact inducibility-type results for graphs via flag algebras, Electron. J. Combin. 33 (2026), no. 2, Paper No. P2.39

2026
[6]

Bollob\'as, Y

B. Bollob\'as, Y. Egawa, A. Harris, and G. Jin, The maximal number of induced r -partite subgraphs, Graphs Combin. 11 (1995), 1--19

1995
[7]

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

1994
[8]

Chen and J

H. Chen and J. A. Noel, On alternating 6-cycles in edge-coloured graphs, Electron. J. Combin., to appear; arXiv:2505.09809, 2025

arXiv 2025

Show all 15 references

[9]

Deng and J

J. Deng and J. Hou, Fixed-density profiles for the semi-induced 4-vertex star, arXiv:2606.23351, 2026

2026 arXiv
[10]

G. B. Folland, Real Analysis: Modern Techniques and Their Applications, 2nd ed., John Wiley & Sons, 1999

1999
[11]

Hatami, J

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

2014
[12]

Lov\'asz, Large Networks and Graph Limits, American Mathematical Society, 2012

L. Lov\'asz, Large Networks and Graph Limits, American Mathematical Society, 2012

2012
[13]

Lov\'asz and B

L. Lov\'asz and B. Szegedy, Limits of dense graph sequences, J. Combin. Theory Ser. B 96 (2006), 933--957

2006
[14]

Pippenger and M

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

1975
[15]

A. A. Razborov, Flag algebras, J. Symbolic Logic 72 (2007), 1239--1282

2007

Pith tools

Reviewed July 31, 2026 · model on record in the stance chip above.

[1] [1]

Balogh, B

J. Balogh, B. Lidick\'y, D. Mubayi, F. Pfender, and J. Volec, Semi-inducibility of some small graphs, arXiv:2601.03433, 2026

arXiv 2026

[2] [2]

Basit, B

A. Basit, B. Granet, D. Horsley, A. K\"undgen, and K. Staden, The semi-inducibility problem, arXiv:2501.09842, 2025

arXiv 2025

[3] [3]

Bodn\'ar, J

L. Bodn\'ar, J. Gao, J. Le\'on, X. Liu, O. Pikhurko, and S. Sun, The inducibility of 6-vertex graphs, arXiv:2606.00290, 2026

arXiv 2026

[4] [4]

Bodn\'ar and O

L. Bodn\'ar and O. Pikhurko, Semi-inducibility of 4-vertex graphs, Discrete Appl. Math. 392 (2026), 303--323

2026

[5] [5]

Bodn\'ar and O

L. Bodn\'ar and O. Pikhurko, Some exact inducibility-type results for graphs via flag algebras, Electron. J. Combin. 33 (2026), no. 2, Paper No. P2.39

2026

[6] [6]

Bollob\'as, Y

B. Bollob\'as, Y. Egawa, A. Harris, and G. Jin, The maximal number of induced r -partite subgraphs, Graphs Combin. 11 (1995), 1--19

1995

[7] [7]

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

1994

[8] [8]

Chen and J

H. Chen and J. A. Noel, On alternating 6-cycles in edge-coloured graphs, Electron. J. Combin., to appear; arXiv:2505.09809, 2025

arXiv 2025