{"id":"59e91f08-03c2-4b6e-b5ec-c25f1e4b8007","arxiv_id":"2501.09842","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors determine sharp or almost sharp maximum densities for alternating walks and cycles and for every 4-cycle colour pattern in red-blue complete graphs, and exhibit a positive-coefficient quantum graph whose only asymptotically extremal graphs are quasirandom.","lead":"This paper introduces the semi-inducibility problem: the maximum number of copies of a fixed red-blue graph H inside a red-blue complete graph. It proves sharp bounds for alternating walks and cycles and for all 4-cycle colour patterns, and it shows that a certain quantum graph is uniquely maximized by quasirandom graphs over a range of densities.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: Theorem 2.6's proof chain from Theorem 2.7 through Section 7.2 is internally consistent.","rationale":"The reader's verdict identified Lemma 3.11's canonical inequality as the weakest assumption. That is a reasonable spot to scrutinize in the exact bipartite results, but it is not the load-bearing assumption for the paper's central claim, Theorem 2.6, whose proof path goes through Theorem 2.7, Lemma 7.6, Lemma 7.8, and Lemma 7.9 rather than through Lemma 3.11. I checked those lemmas in detail. The relaxation to S(σ) is a proper superset of realizable degree–codegree vectors, so the upper bound is valid; the balancing iteration in Lemma 7.8 preserves feasibility because S(σ) is defined only by linear constraints on z; and the algebra in Lemma 7.9, including the use of Lemma 7.7(ii) and the Cauchy–Schwarz step, is internally consistent. The identity connecting #(RRRB, GJ) to I(Q,J) is also consistent with the explicit random-graph expectation 12σ^3(1−σ). I found no circularity, hidden non-uniformity, or unsupported jump in the central argument. The paper's unquantified 'sufficiently large n' thresholds are a limitation of the presentation but not a correctness defect. Therefore I do not raise a load-bearing concern and recommend the reader's ACCEPT verdict stand unchanged.","tokens_in":49465,"tokens_out":28443,"duration_ms":283250,"concrete_test":"Independently re-derive equation (27) and the estimates in Lemma 7.9(i) using a computer algebra system, verifying the constants γ = 5√(2δ), the bound ℓ ≤ 1/4 + O(1/n), and the final chain 4∑_{i<j}|z_ij − σ^2| ≤ 10δ^{1/8}n^2. If any of these algebraic steps fails, the stability exponent in Theorem 2.7 changes and the quasirandom conclusion in Theorem 2.6 would need re-examination.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I read the central claim as Theorem 2.6 and traced its dependencies. Theorem 2.7 is proved by relaxing degree–codegree vectors to the set S(σ) and maximizing f over a superset of realizable vectors. Lemma 7.6 correctly expresses #(RRRB, G) as (n^4/2)f(d,z)+O(n^3), and the relaxation is legitimate for an upper bound. Lemma 7.8's balancing argument is valid: since S(σ) imposes only linear constraints on z, the transferring operation preserves feasibility and strictly increases f unless all t_ij equal ℓ; the compactness argument for attainment on S0(σ) is sound. Lemma 7.9 then correctly derives the upper bound and stability: for σ ≥ (1+√2)/4, the construction d_i ≡ σ, z_ij = σ^2 + O(1/n) lies in S(σ) and gives F(σ) = σ^3(1−σ)+O(1/n), and the inequalities leading to ∑_{i<j}|z_ij − σ^2| = O(δ^{1/8}n^2) are algebraically sound, including the Cauchy–Schwarz step converting the variance bound into a degree deviation bound. The bridge identity (33) between RRRB cycles in GJ and I(Q,J) matches the automorphism-count verification in the rand(Q,σ) formula (12σ^3(1−σ)). The reader's weakest assumption concerns Lemma 3.11, which is used for the exact bipartite results (Theorems 1.5, 1.7, 8.1), not for Theorem 2.6; for the alternating and RRBB cases the canonical inequality is established by Proposition 3.12 with a uniform margin, so I do not see a load-bearing gap there either.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":49849,"tokens_out":39576,"duration_ms":339127,"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":[{"comment":"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.","section":"Section 3.4, Lemma 3.11"}],"minor_comments":[{"comment":"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":"Section 7.2, Theorem 2.6"},{"comment":"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":"Section 3.4, Lemma 3.11"},{"comment":"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.","section":"Section 1, Table 1.1"}],"recommendation":"minor_revision","confidential_remarks":"The paper relies on two results of the authors themselves: Lemma 3.7 is taken from [11] (Cheng--Staden) and Theorem 8.2 is from [31] (Liu--Pikhurko--Sharifzadeh--Staden). This is acceptable, but the editor may wish to ensure that these are published or in press and that the present paper does not merely repackage them. Overall the main contribution, Theorem 2.6, is novel and significant; the issues I found are local and fixable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this paper. The main news: it introduces a natural two-colour generalization of inducibility and proves a collection of sharp results, the most significant being a positive-coefficient quantum graph Q such that, for every density sigma in [1/4(1+sqrt2), 1], the maximum induced Q-density equals the random-graph value and every near-extremal graph is quasirandom. That is a direct counterpoint to the Jain–Michelen–Wei negative result for single graphs, and it is the first example of its kind.\n\nWhat is actually new: the semi-inducibility framework is a special case of quantum-graph inducibility, but the theorems are new. The alternating walk bound (Theorem 1.3) is a tight Cauchy–Schwarz argument generalizing Goodman; the alternating 4t-cycle theorem gives a unique balanced-bipartite extremal; and the paper settles all four 4-cycle colour patterns. The RRBB case is genuinely surprising: the extremal parts differ by Theta(sqrt n). The proofs are elementary and detailed—no flag algebra—and the degree–codegree relaxation in Section 7 is well executed. I checked the chain from Theorem 2.7 through Lemmas 7.8 and 7.9; the balancing argument and the variance-to-degree step are sound.\n\nSoft spots, in proportion: the exact \"if and only if\" results route through Lemma 3.11, where the canonical inequality is assumed uniformly with margin eta/2. The stress-test is right that Proposition 3.12 supplies that margin in the cases actually used (alternating cycles, RRBB), so I don't see a load-bearing gap. But the paper never quantifies \"sufficiently large n\" for the stability arguments, and the dependence on two external results by overlapping authors (Lemma 3.7 and the symmetrisation theorem) is worth a referee's scrutiny. Neither is circular; the uses are specific and legitimate. The interval in Theorem 2.6 begins at roughly 0.60; for smaller densities the problem is left open, which the paper says explicitly.\n\nWho should read it: extremal and probabilistic combinatorics people working on inducibility, Sidorenko-type questions, or quasirandomness. It deserves a serious referee. My recommendation is to send it out; if the referee confirms the details of Lemma 3.11 and the external dependencies, accept.","headline":"Solid new results on two-colour inducibility, capped by a positive-coefficient quantum graph with quasirandom unique extremals over an interval of densities.","tokens_in":50389,"tokens_out":2878,"would_cite":true,"duration_ms":30677,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C80","05C15","05C38"],"pacs":[],"model":"deepseek-v4-flash","headline":"A four-vertex quantum graph with positive coefficients has quasirandom graphs as its unique extremal graphs across an entire interval of edge densities.","keywords":["semi-inducibility","red-blue graphs","quantum graphs","quasirandom graphs","inducibility problem","alternating walks","alternating cycles","4-cycles"],"falsifier":"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$.","tokens_in":49312,"feed_emoji":"🎲","tokens_out":16923,"duration_ms":168527,"temperature":0.7,"pith_summary":"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.","feed_headline":"Quasirandom graphs are unique extremal for a 4-vertex quantum graph","feed_subtitle":"New interval result shows random-like graphs maximise induced density, countering the single-graph negative result.","key_machinery":"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.","core_discovery":"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$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the strong negative result for single graphs that Theorem 2.6 is designed to contrast.","marker":"[28]"},{"why":"Defines the upper boundary $I(Q,\\sigma)$ and the random lower bound $\\mathrm{rand}(Q,\\sigma)$, the framework in which Theorem 2.6 is stated.","marker":"[32]"},{"why":"Supplies the quasirandomness definition and the equivalence between codegree concentration and subgraph densities used to conclude that near-maximisers are quasirandom.","marker":"[12]"},{"why":"Provides the walk-counting Cauchy–Schwarz method adapted to prove Theorem 1.3 on alternating walks, which underlies the alternating-cycle results.","marker":"[37]"},{"why":"Gives Goodman's theorem, the base case generalised by the alternating-walk bound and used in the alternating 4-cycle proof.","marker":"[23]"},{"why":"Introduces the inducibility problem and the reduction of semi-inducibility for complete $H$ to inducibility, the framework for the quantum graph formulation.","marker":"[35]"}],"fun_headline_variants":["Quasirandom graphs are the only extremal for quantum Q","Interval of densities: quasirandom only extremal for Q","Semi-inducibility: quasirandom unique on density interval","Quantum Q: quasirandom graphs maximise induced density","4-vertex quantum graph forces quasirandom extremals"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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'.","fun_headline_variants_meta":{"raw":{"variants":["Quasirandom graphs are the only extremal for quantum Q","Interval of densities: quasirandom only extremal for Q","Semi-inducibility: quasirandom unique on density interval","Quantum Q: quasirandom graphs maximise induced density","4-vertex quantum graph forces quasirandom extremals"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00089,"raw_usage":{"total_tokens":3889,"prompt_tokens":1043,"completion_tokens":2846,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":659,"completion_tokens_details":{"reasoning_tokens":2761}},"tokens_in":659,"tokens_out":2846,"duration_ms":22129,"temperature":1.0,"reasoning_tokens":2761,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T19:39:27.056575+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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$.","supporting_citations":[{"cited_title":"The binomial random graph is a bad inducer","cited_arxiv_id":"2306.13014","evidence_quote":"Supplies the strong negative result for single graphs that Theorem 2.6 is designed to contrast."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the upper boundary $I(Q,\\sigma)$ and the random lower bound $\\mathrm{rand}(Q,\\sigma)$, the framework in which Theorem 2.6 is stated."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the quasirandomness definition and the equivalence between codegree concentration and subgraph densities used to conclude that near-maximisers are quasirandom."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the walk-counting Cauchy–Schwarz method adapted to prove Theorem 1.3 on alternating walks, which underlies the alternating-cycle results."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives Goodman's theorem, the base case generalised by the alternating-walk bound and used in the alternating 4-cycle proof."},{"cited_title":"Pippenger and M","cited_arxiv_id":null,"evidence_quote":"Introduces the inducibility problem and the reduction of semi-inducibility for complete $H$ to inducibility, the framework for the quantum graph formulation."}],"review_version":1}