{"id":"490697fa-7648-492c-bd67-a8a95ed791db","arxiv_id":"2411.17362","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Except for the star and the single-edge graph, every other graph has inducibility at most c + o_k(1) for a fixed c < 1/e, and graphs with inducibility bounded away from zero are exactly those with a bounded-size taming set.","lead":"The paper proves that the star and the single-edge graph are essentially the only graphs whose inducibility approaches the universal bound 1/e; every other graph is bounded below that bound by a fixed constant. It also ties inducibility staying bounded away from zero to a simple structural condition on the graph's automorphism group.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The iff characterization in the abstract rests on an unproved converse direction: the claim that every D-tame graph has ind(H) ≥ γ(D) > 0 is deferred to the bachelor thesis.","rationale":"I read the paper in good faith and found the main upper-bound machinery plausible: Theorem 1.2 follows from Theorems 2.1–2.3, the proof of Theorem 2.4 gives the desired D-tameness with D depending only on γ, and the intricate Section 7 coloring argument appears internally coherent (the recurrence that a repeated last black vertex remains black explains the 1/n lower bound). The single genuine gap is the unproved converse for the characterization: the abstract and Remark 1.5 assert an iff statement, but only the necessity direction is proved in the preprint. This is not a disagreement with consensus or a stylistic issue; it is a missing proof of a claimed equivalence. The reader's weakest_assumption identified exactly this point, and I agree. Because the concern does not undermine Theorem 1.2 or the one-way Theorem 1.4, the reader's CONDITIONAL verdict remains appropriate. The concrete test—supplying the short construction or checking the explicit multipartite example—would settle whether the characterization is fully valid.","tokens_in":25394,"tokens_out":22661,"duration_ms":225153,"concrete_test":"Ask the author to include the deferred construction from [11, Appendix B], or verify it directly as follows. For a D-tame graph H with V0 of size d0+d1, let R = V(H)\\V0, and partition V0 into those vertices adjacent to all of R (count d0) and those adjacent to none (count d1). Build G on n vertices with parts A0, A1, B of sizes d0 n/k, d1 n/k, and (1 - (d0+d1)/k)n. Put a G(|A0|+|A1|, 1/2) random graph inside A0∪A1 to realize H[V0] with probability 2^{-binom(D,2)}; put complete bipartite edges between A0 and B, no edges between A1 and B, and make B empty or complete according to whether R is stable or a clique. Compute the limiting probability that a uniform k-set has exactly d0 vertices in A0, d1 in A1, and the remaining k-D in B, and that the sampled vertices in A0∪A1 induce H[V0].","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's headline result is the equivalence \"ind(H) ≥ Ω(1) iff H is O(1)-tame\" (abstract and Remark 1.5). Theorem 1.4 proves only the forward direction: ind(H) ≥ γ implies H is D-tame. The reverse direction is stated without proof immediately after Definition 1.3: \"It is not hard to show, by adapting the construction of G for H = K_{1,k-1}, that all D-tame graphs have inducibility at least γ = γ(D) > 0,\" with details deferred to the author's bachelor thesis [11, Appendix B]. This is the load-bearing missing step for the characterization. The star and single-edge examples show the construction idea for D=1 and D=2, but for general D one must simultaneously sample up to D exceptional vertices with possibly different cross-edge behavior to V(H)\\V0; the probability of doing so is a constant depending only on D (for K_{D,k-D}, one gets at least D^D e^{-D}/D! by choosing parts of size n/k), but this requires an explicit proof. Without it, the abstract's \"explicitly characterize\" claim is stronger than what is established in the preprint. Notably, Theorem 1.2's c < 1/e bound and Theorem 1.4's necessity direction are independent of this converse, so the gap is localized to the characterization statement rather than to the main upper bound machinery.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the inducibility ind(H) of k-vertex graphs H. Building on the resolved edge-statistics conjecture, it proves an absolute gap below 1/e: if H has k vertices and 2 ≤ ℓ ≤ (1/2) binom(k,2) edges and is not the star K_{1,k-1}, then ind(H) ≤ c + o_k(1) for an absolute constant c < 1/e (Theorem 1.2). It also proves a structural necessary condition: for every γ > 0 there is D = D(γ) such that ind(H) ≥ γ implies H is D-tame, meaning a bounded set V0 exists such that every permutation of V(H)\\V0 extends to an automorphism of H (Theorem 1.4). The abstract and Remark 1.5 additionally assert an iff characterization of all graphs with ind(H) = Ω(1) as the O(1)-tame graphs, but the sufficiency direction ('every D-tame graph has ind(H) ≥ γ(D) > 0') is only claimed and deferred to the author's bachelor's thesis [11, Appendix B]. The main proofs of Theorems 1.2 and 1.4 are detailed and proceed through lemmas built on Kwan–Sudakov–Tran, Fox–Sauermann, and Martinsson et al.","tokens_in":25557,"tokens_out":7061,"duration_ms":66223,"significance":"The main upper-bound results, if correct, are a genuine advance: Theorem 1.2 strengthens the asymptotic inducibility bound from 1/e to an absolute c < 1/e for all non-star graphs in the stated edge range, and Theorem 1.4 gives a clean structural necessary condition for graphs with inducibility bounded away from zero. The proof of Theorem 1.4 is particularly attractive: Fact 3.5 reduces tameness to controlling S ∪ T ∪ U, and the anti-concentration machinery is used only to bound the sizes of these sets. The paper is transparent about its external dependencies and supplies substantial in-paper proofs; there is no parameter fitting or circularity in the upper-bound arguments. The caveat is that the headline 'characterization' is only half-proved in this manuscript.","major_comments":[{"comment":"The abstract's 'explicitly characterize' claim and the equivalence in Remark 1.5 require proving that every D-tame graph H satisfies ind(H) ≥ γ(D) > 0. This direction is not proved in the manuscript; it is asserted directly after Definition 1.3 with the sentence 'It is not hard to show...' and deferred to the author's bachelor's thesis [11, Appendix B]. The star case D = 1 and the single-edge case D = 2 illustrate the construction but do not establish the general claim, where one must simultaneously sample up to D exceptional vertices with possibly different cross-edge behavior to V(H)\\V0. Because this converse is load-bearing for the characterization, the journal version should either include the full proof (or a precise reduction to a published argument) or restate the results as a conditional characterization and move the converse to a conjecture. Theorems 1.2 and 1.4 are unaffected by this gap.","section":"Section 1, Definition 1.3 and Remark 1.5"},{"comment":"The remark that the complete bipartite graph with parts of sizes 2 and k−2, the graph with two non-adjacent edges, and the graph obtained from K_{2,k−2} by adding an edge in the part of size 2 all have inducibility at least 2/e^2 + o_k(1) is only a sketch. This claim is not needed for the main theorems, but since it motivates Conjecture 1.6 and fixes the lower bound for c, a short computation or a precise citation would make the discussion self-contained.","section":"Section 1, after Conjecture 1.6"}],"minor_comments":[{"comment":"The line 'for m1(H) = 2, we have m(H) ≤ 2m(H) = 4' should read 'm(H) ≤ 2m1(H) = 4'; as written the inequality is dimensionally inconsistent and momentarily obscures the argument.","section":"Section 6, proof of Claim 6.11"},{"comment":"The phrase 'It follows from the resolved Edge-statistics conjecture' should be rephrased as 'It follows from the resolution of the Edge-statistics conjecture' or directly linked to Theorem 1.1, since the conjecture is used as a proven theorem rather than an assumption.","section":"Abstract and Section 1"},{"comment":"The proof of the converse of tameness is deferred to the author's bachelor's thesis [11, Appendix B]. For an archival journal article, including that proof in an appendix or providing a more standard published reference would be preferable to a deferral to an unpublished thesis.","section":"References"},{"comment":"The notation for asymptotic expressions with a subscript, such as o_{n|k}(1), is explained in the text, but a reader encountering it for the first time may benefit from one explicit example in addition to the definition.","section":"Section 2.2"}],"recommendation":"major_revision","confidential_remarks":"The missing converse of the characterization is the only structural obstruction to the paper's headline claim; it is localized and appears very likely fixable by adapting the star construction, but the journal version should not archive an iff theorem without the proof. The upper-bound results themselves seem solid and well within the scope of math.CO. The paper is clearly written and the self-citation to the bachelor's thesis is transparent. I would ask the author to either include the missing proof or explicitly mark the characterization as conditional."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper delivers two solid results. Theorem 1.2 strengthens the resolved edge-statistics conjecture: every non-extremal H with at least two edges and not a star has inducibility at most c + o_k(1) for an absolute c < 1/e. Theorem 1.4 gives the structural necessity direction: ind(H) ≥ γ forces H to be D-tame for D = D(γ). These are genuine advances and the proofs are careful. The use of Kwan–Sudakov–Tran, Fox–Sauermann, and Martinsson et al. is appropriate, and the sparse-case argument in Lemma 6.7 (the 'detectable/bright' labeling machinery) is intricate but appears to hold. I did not machine-check it, but the chain from the random labeling to the bound on P[E] is coherent. The paper also proves Conjecture 1.6's bound 2/e^2 in the case m(H) ≥ Ω(k), which is a nice partial result.\n\nThe soft spot is exactly where the reader put it: the abstract and Remark 1.5 claim an iff characterization, but only the forward direction is proved. The converse—every D-tame graph has ind(H) ≥ γ(D) > 0—is stated as 'not hard to show' and deferred to the bachelor's thesis. The star and single-edge constructions illustrate D=1 and D=2, but the general case needs an explicit argument: sampling up to D exceptional vertices with controlled cross-edges gives a constant probability, yet this is not a one-line consequence for arbitrary tameness patterns. If the converse fails, the abstract's 'explicitly characterize' claim collapses, even though Theorems 1.2 and 1.4 remain intact. This is a localized gap, not a load-bearing flaw in the upper-bound machinery. A second, minor point: the constant c in Theorem 2.3 is chosen implicitly through α and a chain of inequalities, so the reader does not learn how small it actually is; Conjecture 1.6's 2/e^2 remains open in the sparse case.\n\nWho is this for? Researchers in extremal graph theory, especially anyone working on inducibility or edge-statistics. It deserves a serious referee: the main theorems are new, the proofs are mostly self-contained, and the one gap is clearly identifiable and fixable. My recommendation: send it to peer review with a request that the author either include the converse proof or soften the abstract to state the one-way theorem plus a conjecture. If the converse is already in the thesis, including it here would make the paper complete.","headline":"A serious and substantial paper: the c < 1/e bound and the tameness necessity direction are real results, but the headline 'characterization' overclaims because the converse is deferred to a thesis.","tokens_in":26153,"tokens_out":1146,"would_cite":true,"duration_ms":13430,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05D40","05C80"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that only the star and the one-edge graph—together with their complements—can attain the extremal $1/e$ inducibility bound, and that every graph with inducibility bounded away from zero is tame in a precise sense.","keywords":["inducibility","induced density","edge-statistics conjecture","tame graphs","graph automorphisms","extremal graph theory","anti-concentration","sparse graphs"],"falsifier":"Compute the inducibility of any explicitly defined family of $D$-tame graphs with $k$ growing; for instance, take $H_k$ to be a graph whose only edges join one fixed vertex to an independent set and see whether $\\mathrm{ind}(H_k)$ stays bounded below a positive constant. A single $D$-tame family with $\\mathrm{ind}(H_k)=o_k(1)$ would disprove the paper's characterizing converse. Separately, to test Theorem 1.2, look for any sequence of non-star $k$-vertex graphs with $2\\le \\ell \\le \\frac{1}{2}\\binom{k}{2}$ whose inducibility tends to $1/e$.","tokens_in":2141,"feed_emoji":"⭐","tokens_out":2653,"duration_ms":103897,"temperature":0.7,"pith_summary":"Inducibility measures the largest possible probability that $k$ uniformly random vertices of a large graph induce a given $k$-vertex graph $H$. A known theorem says that unless $H$ is empty or complete, this probability is at most $1/e + o(1)$, and stars and one-edge graphs attain that value. This paper proves that these are the only near-extremal shapes: every other graph with at least two edges has inducibility at most $c + o(1)$ for an absolute constant $c < 1/e$. It also characterizes graphs whose inducibility is bounded away from zero as exactly the $D$-tame graphs, those in which all vertices outside a bounded exceptional set are interchangeable under automorphisms. The upshot is a structural dichotomy: either $H$ is essentially a symmetric object with a small core, or its inducibility is asymptotically smaller than the extremal value.","feed_headline":"Only the star and one-edge graphs hit the 1/e inducibility bound","feed_subtitle":"Every other graph lies below an absolute constant c<1/e; high inducibility means a bounded core tames symmetries.","key_machinery":"The load-bearing object is the $D$-tame graph: $V_0 \\subseteq V(H)$ with $|V_0| \\le D$ such that every permutation of $V(H) \\setminus V_0$ fixing $V_0$ extends to an automorphism. Equivalently, $V(H) \\setminus V_0$ is a clique or a stable set, and each vertex of $V_0$ is adjacent to all or none of it. The proofs split graphs into a dense regime, handled by an anticoncentration reduction that leaves only $\\ell \\le Ck$, and a sparse regime controlled by three lemmas about degree distributions: high-degree vertices, near-regular low-degree vertices, and graphs with no dominant degree class. The extremal sparse case is treated with a random labeling in which vertices are colored black, green, or red, and the inducibility bound is forced by the probability that a sequence of i.i.d. labels produces exactly two green terms or one red term. Throughout, the quantity $s^s/(s!\\,e^s)$ and hypergeometric tail bounds carry the numerical smallness that yields constants like $2/e^2$.","core_discovery":"The paper's central theorem states that there is an absolute constant $c < 1/e$ such that for every $k$, every $\\ell$ with $2 \\le \\ell \\le \\frac{1}{2}\\binom{k}{2}$, and every graph $H$ with $k$ vertices and $\\ell$ edges that is not isomorphic to the star $K_{1,k-1}$, one has $\\mathrm{ind}(H) \\le c + o_k(1)$. Since inducibility is complement-invariant, this says the two known equality cases in the edge-statistics bound are isolated. The paper also proves the structural half of a characterization: for any fixed $\\gamma>0$ there is a $D$ such that $\\mathrm{ind}(H) \\ge \\gamma$ implies $H$ is $D$-tame, meaning a set $V_0$ of at most $D$ vertices exists and every permutation of $V(H) \\setminus V_0$ fixing $V_0$ extends to an automorphism. The paper defers to a bachelor thesis the converse claim that every $D$-tame $H$ has inducibility at least $\\gamma(D)>0$; if that converse is supplied, the three properties—inducibility bounded below, bounded tameness, and having $(k-O(1))!$ automorphisms—are equivalent.","pith_inferences":["If the missing converse is supplied, the characterization would turn 'has induced density bounded away from zero' into a symmetry certificate that can be checked by guessing a bounded vertex set—an algorithmic dichotomy potentially useful for other hereditary graph parameters.","The constant $2/e^2$ appearing as the conjectured optimum matches the quantity $s^s/(s!e^s)$ for $s=2$, suggesting a hierarchy of thresholds $r^r/(r!e^r)$ for graphs whose extremal constructions require $r$ exceptional vertices; the paper's Lemma 3.1 already points to this shape.","A natural test is to compute $\\inf_H \\mathrm{ind}(H)$ over $D$-tame graphs for each fixed $D$; the paper gives an upper structural theorem but no explicit lower bound $\\gamma(D)$, so numerical or constructive lower bounds would complete the quantitative picture.","One could try to prove Conjecture 1.6 by extending Theorem 2.3's constants: the current proof only reaches $c<1/e$ when $m(H)\\le \\alpha k$, so a sharper analysis of the black/green/red labeling may push that case to $2/e^2$."],"forward_implications":["For every non-star $H$ with $2\\le \\ell \\le \\frac{1}{2}\\binom{k}{2}$ edges, $\\mathrm{ind}(H) \\le c + o_k(1)$ with a universal $c<1/e$; the star, the one-edge graph, and their complements are the only graphs that get asymptotically close to $1/e$.","Any graph with $\\mathrm{ind}(H) \\ge \\gamma$ for a fixed $\\gamma>0$ must be $D$-tame for $D=D(\\gamma)$, so it has at least $(k-D)!$ automorphisms.","If the deferred converse holds, high inducibility is equivalent to $O(1)$-tameness and to having $(k-O(1))!$ automorphisms, giving a complete structural characterization.","Sparse graphs with at most $\\alpha k$ non-isolated vertices and at least two edges have inducibility at most $c<1/e$, so no sparse construction can match the $1/e$ extremal value.","The conjectured optimal constant is $2/e^2$, and the paper proves this bound in the case where the number of non-isolated vertices is linear in $k$."],"supporting_citations":[{"why":"Supplies the anticoncentration theorem (Theorem 2.1) that reduces the proof to sparse graphs with $\\ell \\le Ck$.","marker":"[7]"},{"why":"Provides the edge-statistics completion and Claim 3.3, used as Lemma 3.3 for graphs with no common degree class; also the random-labeling approach adapted in the key lemma.","marker":"[8]"},{"why":"Supplies Lemmas 3.1 and 3.2, used in Theorem 2.5 to control inducibility when $m(H)$ is between $D$ and $k/32$.","marker":"[3]"},{"why":"Proposed the conjecture that the $1/e$ bound is tight and identified the star and one-edge constructions as extremal examples; the paper answers the follow-up question.","marker":"[1]"},{"why":"Introduced the inducibility parameter that the whole paper studies.","marker":"[9]"},{"why":"Contains the converse direction of the characterization and an alternative proof of Lemma 3.3; the paper's main equivalence depends on this reference for the missing direction.","marker":"[11]"},{"why":"Supplies the hypergeometric tail bound used in Lemma 3.1's proof to show the low/high-degree split event has probability $o_k(1)$.","marker":"[5]"}],"fun_headline_variants":["Only star and one-edge graphs reach the 1/e inducibility bound","Beyond stars and one-edge graphs, inducibility drops below 1/e","High inducibility forces a bounded automorphism core","Graphs with high inducibility have a small symmetry core","Star and one-edge graphs are isolated at the 1/e inducibility ceiling"],"cache_read_input_tokens":28160,"weakest_assumption_plain":"The full characterization requires the unproved converse—that every $D$-tame graph has inducibility at least some $\\gamma(D)>0$—which the paper asserts but defers to a bachelor thesis; if that direction fails, the 'iff' collapses, although Theorems 1.2 and 1.4 still stand.","fun_headline_variants_meta":{"raw":{"variants":["Only star and one-edge graphs reach the 1/e inducibility bound","Beyond stars and one-edge graphs, inducibility drops below 1/e","High inducibility forces a bounded automorphism core","Graphs with high inducibility have a small symmetry core","Star and one-edge graphs are isolated at the 1/e inducibility ceiling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00108,"raw_usage":{"total_tokens":4578,"prompt_tokens":1066,"completion_tokens":3512,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":682,"completion_tokens_details":{"reasoning_tokens":3418}},"tokens_in":682,"tokens_out":3512,"duration_ms":23754,"temperature":1.0,"reasoning_tokens":3418,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:12:31.658126+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the inducibility of any explicitly defined family of $D$-tame graphs with $k$ growing; for instance, take $H_k$ to be a graph whose only edges join one fixed vertex to an independent set and see whether $\\mathrm{ind}(H_k)$ stays bounded below a positive constant. A single $D$-tame family with $\\mathrm{ind}(H_k)=o_k(1)$ would disprove the paper's characterizing converse. Separately, to test Theorem 1.2, look for any sequence of non-star $k$-vertex graphs with $2\\le \\ell \\le \\frac{1}{2}\\binom{k}{2}$ whose inducibility tends to $1/e$.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the anticoncentration theorem (Theorem 2.1) that reduces the proof to sparse graphs with $\\ell \\le Ck$."},{"cited_title":"Martinsson, F","cited_arxiv_id":null,"evidence_quote":"Provides the edge-statistics completion and Claim 3.3, used as Lemma 3.3 for graphs with no common degree class; also the random-labeling approach adapted in the key lemma."},{"cited_title":"Fox and L","cited_arxiv_id":null,"evidence_quote":"Supplies Lemmas 3.1 and 3.2, used in Theorem 2.5 to control inducibility when $m(H)$ is between $D$ and $k/32$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Proposed the conjecture that the $1/e$ bound is tight and identified the star and one-edge constructions as extremal examples; the paper answers the follow-up question."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Contains the converse direction of the characterization and an alternative proof of Lemma 3.3; the paper's main equivalence depends on this reference for the missing direction."}],"review_version":1}