Pith. sign in

REVIEW 2 major objections 4 minor 13 references

Characterizing graphs with high inducibility

T0 review · 2 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2411.17362 v1 pith:3LJTKNCQ submitted 2024-11-26 math.CO

Richard Ueltzen This is my paper · ORCID
classification math.CO MSC 05C3505D4005C80
keywords inducibilityinduceddensityedge-statisticsconjecturetamegraphsgraphautomorphismsextremaltheoryanti-concentrationsparse
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

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.

What carries the argument

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$.

What would settle it

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$.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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$.

Reading between the lines

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

  • 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$.
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

2 major / 4 minor

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.

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 (2)
  1. [Section 1, Definition 1.3 and Remark 1.5] 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.
  2. [Section 1, after Conjecture 1.6] 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.
minor comments (4)
  1. [Section 6, proof of Claim 6.11] 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.
  2. [Abstract and Section 1] 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.
  3. [References] 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.
  4. [Section 2.2] 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.

Circularity Check

0 steps flagged · score 2.0 of 10

No construction-level circularity: the upper-bound theorems are derived from external resolved results plus in-paper lemmas; the only self-citation is the unproved-in-paper converse for the tameness characterization.

full rationale

The derivation chain for Theorem 1.2 is independent and non-circular: Theorem 1.2 is deduced from Theorems 2.2 and 2.3; Theorem 2.2 is proved from Lemmas 3.1, 3.2, 3.3, Claim 3.4 and the external resolved Edge-statistics conjecture (Theorem 1.1, from [3,7,8]); Theorem 2.3 is proved from Lemma 6.7, whose proof uses only in-paper random-labeling arguments and the external Fox–Sauermann [3] bounds; Theorem 2.4 is proved from Fact 3.5, Claims 3.4 and 3.6, Theorem 2.5 (from [3]), and Lemma 3.2. No fitted parameter is renamed as a prediction, and no displayed equation reduces to its own input by construction. The only related concern is flagged explicitly: after Definition 1.3 the paper states, '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,' and Remark 1.5 defers a converse to the author's bachelor's thesis [11, Appendix B]. This is needed for the full iff characterization in the abstract, so it is a completeness/correctness risk: the characterization claim is stronger than what is actually proved within the preprint. However, this is a deferred proof, not a definitional reduction or a fitted-input prediction, and it does not feed into the main upper-bound theorems. I therefore treat it as a minor self-citation rather than circularity.

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

No numerical parameters are fitted to data; all constants are existential. The paper's derivations rest on several external theorems from the extremal graph theory literature, plus one unproved converse assertion deferred to the author's own thesis.

assumptions (5)
  • domain assumption Theorem 1.1 (resolved edge-statistics conjecture) is used as a black box.
    Used at multiple points, e.g., the proof of Theorem 2.2 and the derivation of the main bounds. Stated in Section 1.
  • domain assumption Theorem 2.1 (Kwan-Sudakov-Tran anticoncentration result) is used to reduce to the sparse case.
    Stated in Section 2 and applied in proofs of Theorems 1.2 and 1.4.
  • domain assumption Theorem 2.5 (Fox-Sauermann lemmas) is used in Claim 3.6 to handle graphs with at most k/32 non-isolated vertices.
    Stated in Section 2.1 as a corollary of Lemmas 3.1 and 3.2 of [3].
  • domain assumption Lemma 3.3 (from Martinsson et al. Claim 3.3) bounds inducibility when no degree class is large.
    Used in proofs of Theorem 2.2 and Claim 3.6; the paper sketches the reduction.
  • ad hoc to paper Every D-tame graph has inducibility at least gamma(D) > 0.
    Asserted without proof in Section 1 after Definition 1.3; the details are deferred to the author's bachelor thesis [11, Appendix B]. Needed for the abstract's characterization and Remark 1.5's equivalences.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Characterizing graphs with high inducibility." pith.science (2026). https://pith.science/paper/3LJTKNCQ

@misc{pith2026241117362,
  author       = {Pith},
  title        = {Pith review of: Characterizing graphs with high inducibility},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3LJTKNCQ}},
  note         = {Machine review of arXiv:2411.17362}
}
abstract

For a positive integer $k$ and a graph $H$ on $k$ vertices, we are interested in the inducibility of $H$, denoted $\mathrm{ind}(H)$, which is defined as the maximum possible probability that choosing $k$ vertices uniformly at random from a large graph $G$, they induce a copy of $H$. It follows from the resolved Edge-statistics conjecture that if $H \not \in \{K_k, \bar K_k\}$, then $\mathrm{ind}(H) \leq 1 / e + o_k(1)$. Equality holds for the star graph $K_{1, k-1}$, the graph with a single edge on $k$ vertices and their complements. We prove that for all other graphs $H$, we have $\mathrm{ind}(H) \leq c + o_k(1)$ for an absolute constant $c < 1 / e$. Moreover, we explicitly characterize all graphs with inducibility bounded away from zero. Namely, we show that this is the class of graphs $H$ for which there is a set $V_0 \subseteq V(H)$ of bounded size with the property that all permutations of $V(H) \backslash V_0$ extend to an automorphism of $H$.

Figures

Figures reproduced from arXiv: 2411.17362 by the authors.

Figure 1
Figure 1. The graph H is tamed by V0. It is not hard to show, by adapting the construction of G for H = K1,k−1, that all D-tame graphs have inducibility at least γ = γ(D) > 0. Conversely, the following theorem shows that all graphs with inducibility bounded away from 0 exhibit this structure: Theorem 1.4. For any fixed γ > 0, there exists a positive integer D such that any graph H satisfying ind(H) ≥ γ is D-tame. Remark 1.5. … view at source ↗
Figure 2
Figure 2. The graph H is tamed by V0 = S ∪ T ∪ U. Proof. Let D1 := D( γ 2 ) be the constant from Theorem 2.5. For any nonnegative integer i, let ki be the number of vertices of degree i in H and define β := 31 32 ∈ [ 1 2 , 1). If ki ≤ βk for all integers i, then by Lemma 3.3 with ℓ ≤ 2Ck, we have ind(H) ≤ ok(1). Now, let us assume that for some nonnegative integer τ , we have kτ ≥ βk. Therefore, kτ τ ≤ P v∈V (H) d(v) ≤ 2ℓ and… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 8 canonical work pages

  1. [1]

    N. Alon, D. Hefetz, M. Krivelevich, and M. Tyomkyn.Edge-statistics on large graphs. Combin. Probab. Comput. 29 (2020), 163–189.doi: 10.1017/s0963548319000294

    work page doi:10.1017/s0963548319000294 2020

  2. [2]

    Balogh, P

    J. Balogh, P. Hu, B. Lidický, and F. Pfender.Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle. European J. Combin. 52 (2016), 47–58.doi: 10.1016/j.ejc.2015.08. 006

    work page doi:10.1016/j.ejc.2015.08 2016

  3. [3]

    Fox and L

    J. Fox and L. Sauermann.A completion of the proof of the edge-statistics conjecture. Adv. Comb. (2020), Paper No. 4, pp. 52.doi: 10.19086/aic.12047

    work page doi:10.19086/aic.12047 2020

  4. [4]

    Hefetz and M

    D. Hefetz and M. Tyomkyn.On the inducibility of cycles. J. Combin. Theory Ser. B 133 (2018), 243–258. doi: 10.1016/j.jctb.2018.04.008

    doi:10.1016/j.jctb.2018.04.008 2018

  5. [5]

    Janson, T

    S. Janson, T. Łuczak, and A. Rucinski.Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000.doi: 10.1002/9781118032718. 19

    doi:10.1002/9781118032718

  6. [6]

    Král’, S

    D. Král’, S. Norin, and J. Volec.A bound on the inducibility of cycles. J. Combin. Theory Ser. A 161 (2019), 359–363.doi: 10.1016/j.jcta.2018.08.003

    doi:10.1016/j.jcta.2018.08.003 2019

  7. [7]

    M. Kwan, B. Sudakov, and T. Tran.Anticoncentration for subgraph statistics. J. Lond. Math. Soc. (2) 99 (2019), 757–777.doi: 10.1112/jlms.12192

    work page doi:10.1112/jlms.12192 2019

  8. [8]

    Martinsson, F

    A. Martinsson, F. Mousset, A. Noever, and M. Trujić.The edge-statistics conjecture forℓ ≪ k6/5. Israel J. Math. 234 (2019), 677–690.doi: 10.1007/s11856-019-1929-8

    work page doi:10.1007/s11856-019-1929-8 2019

Show all 13 references
  1. [9]

    Pippenger and M

    N. Pippenger and M. C. Golumbic.The inducibility of graphs. J. Combinatorial Theory Ser. B 19 (1975), 189–203. doi: 10.1016/0095-8956(75)90084-2

    1975 doi

  2. [10]

    Robbins.A remark on Stirling’s formula

    H. Robbins.A remark on Stirling’s formula. Amer. Math. Monthly 62 (1955), 26–29.doi: 10.2307/ 2308012

    1955

  3. [11]

    R. Ueltzen. Characterizing Graphs with High Inducibility. Bachelor’s thesis, available athttps: //richardueltzen.com/Ueltzen_BS_Thesis.pdf. 2024. (Visited on 11/25/2024)

    2024

  4. [12]

    Yuster.On the exact maximum induced density of almost all graphs and their inducibility

    R. Yuster.On the exact maximum induced density of almost all graphs and their inducibility. J. Combin. Theory Ser. B 136 (2019), 81–109.doi: 10.1016/j.jctb.2018.09.005. A General anti-concentration inequalities Lemma A.1. Let ˆs be a fixed positive integer. For positive intege...

    2019 doi

  5. [13]

    If P[Zf = s] = 0, the claim is trivial

    Therefore, R′ := R\Rf satisfies |R′| = n − |Rf | ≥n 2 ≥ Ωn(n). If P[Zf = s] = 0, the claim is trivial. Thus, let us assumeP[Zf = s] > 0. By symmetry, the distribution of W, conditioned onZf = s, is uniform on R′ k−s . Therefore, by the inductive assumption forf − 1, P[Z1 = · ·...

Pith tools

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