pith. sign in

arxiv: 2605.30821 · v1 · pith:P76PJCZYnew · submitted 2026-05-29 · 🧮 math.CO

The spectral inducibility of graphs

Liying Kang , Xizhi Liu , Yongchun Lu This is my paper

Pith reviewed 2026-06-28 22:20 UTC · model grok-4.3

classification 🧮 math.CO
keywords spectral inducibilityinduced copiescomplete multipartite graphshypergraph spectral radiusBrown-Sidorenko reductiongraph inducibilityextremal graph theory
0
0 comments X

The pith

For complete multipartite F the graph maximizing the α-spectral radius of induced F-copies can always be chosen complete multipartite.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper replaces the classical count of induced copies of a fixed ℓ-vertex graph F with the α-spectral radius of the hypergraph whose edges are exactly the ℓ-sets that induce F. It proves that when F is complete multipartite this maximum over all n-vertex host graphs G is attained by some complete multipartite G, for every α at least 1. The construction mirrors the Brown–Sidorenko reduction but holds uniformly in the spectral parameter. As α tends to infinity the spectral radius recovers ℓ! times the number of induced copies, so the new quantity refines the ordinary inducibility while keeping the same extremal graphs.

Core claim

For every complete multipartite graph F, every n, and every α ≥ 1, a spectral extremal graph can be chosen to be complete multipartite. The leading asymptotic constant of the maximum is exactly the ordinary inducibility constant i(F). Exact multipartite reductions are obtained for stars K_{1,t} and for balanced complete r-partite graphs K_{a,…,a} when r ≤ 2^a − 1.

What carries the argument

The α-spectral radius of the ℓ-uniform hypergraph H_F(G) whose edges are the ℓ-sets that induce a copy of F.

Load-bearing premise

The α-spectral radius of H_F(G) is defined so that its growth as α becomes large recovers exactly ℓ! times the number of induced copies of F.

What would settle it

A concrete counter-example consisting of a complete multipartite F, an α ≥ 1, an n, and a non-multipartite n-vertex graph G such that the α-spectral radius of H_F(G) strictly exceeds that of every complete multipartite n-vertex graph.

read the original abstract

We introduce a spectral version of the classical inducibility problem. Given an $\ell$-vertex graph $F$ and an $n$-vertex graph $G$, let $H_F(G)$ be the $\ell$-uniform hypergraph whose edges are the $\ell$-sets inducing a copy of $F$ in $G$. We study the maximum possible $\alpha$-spectral radius of $H_F(G)$ over all $n$-vertex graphs $G$. For fixed $G$, this spectral parameter tends to $\ell!$ times the number of induced copies of $F$ in $G$ as $\alpha\to\infty$, and therefore refines the usual induced-copy count. Our main result is a spectral analogue of the Brown--Sidorenko reduction: for every complete multipartite graph $F$, every $n$, and every $\alpha\ge1$, a spectral extremal graph can be chosen to be complete multipartite. We also show that the leading asymptotic constant is the ordinary inducibility $i(F)$, and obtain exact multipartite reductions for stars $K_{1,t}$ and balanced complete $r$-partite graphs $K_{a,\ldots,a}$ with $r\le 2^a-1$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces a spectral version of the inducibility problem. For an ℓ-vertex graph F and n-vertex graph G, it defines the ℓ-uniform hypergraph H_F(G) with edges corresponding to ℓ-sets that induce a copy of F. It studies the maximum α-spectral radius of H_F(G) over all such G. The main result is a spectral analogue of the Brown-Sidorenko theorem: when F is complete multipartite, for every n and every α ≥ 1, an extremal G can be chosen complete multipartite. The paper also shows that the leading asymptotic coefficient as α → ∞ equals the classical inducibility constant i(F), and gives exact results for stars K_{1,t} and balanced complete r-partite graphs K_{a,...,a} with r ≤ 2^a - 1.

Significance. If the central reduction holds, the work supplies a spectral refinement of inducibility that is consistent with the classical theory (recovering i(F) in the α → ∞ limit) while extending the Brown-Sidorenko reduction to this interpolated setting. The exact determinations for stars and the indicated balanced multipartite graphs constitute concrete, falsifiable instances. The manuscript delivers a parameter-free reduction theorem together with an asymptotic identification that matches an existing combinatorial constant; these are strengths under the evaluation criteria.

major comments (2)
  1. [Definition of α-spectral radius (§2)] The definition of the α-spectral radius of H_F(G) (presumably in §2) must be shown to satisfy lim_{α→∞} ρ_α(H_F(G)) = ℓ! · (number of induced copies of F), up to the precise normalization used. This limit is load-bearing for the claim that the leading asymptotic constant equals the ordinary inducibility i(F); an explicit derivation of the limit, including any scaling factors, is required.
  2. [Theorem 1.1 and its proof] Theorem 1.1 (the spectral Brown-Sidorenko reduction): the argument that the extremal graph may be taken complete multipartite when F is complete multipartite relies on the specific form of the α-spectral radius. The proof should isolate the step where the complete-multipartite hypothesis on F is used to rule out non-multipartite extremal graphs, especially for the boundary case α = 1.
minor comments (2)
  1. [Abstract and §2] Notation for the α-spectral radius should be introduced once and used consistently; the current abstract phrasing “tends to ℓ! times the number” would benefit from an explicit displayed limit statement.
  2. [Introduction] The exact results for stars and balanced complete multipartite graphs are stated without reference to the corresponding theorems or corollaries; adding forward references would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, positive evaluation, and constructive suggestions. We address the two major comments point by point below. Both points can be resolved by adding explicit derivations and clarifications; we will incorporate these changes in the revised manuscript.

read point-by-point responses

  1. Referee: [Definition of α-spectral radius (§2)] The definition of the α-spectral radius of H_F(G) (presumably in §2) must be shown to satisfy lim_{α→∞} ρ_α(H_F(G)) = ℓ! · (number of induced copies of F), up to the precise normalization used. This limit is load-bearing for the claim that the leading asymptotic constant equals the ordinary inducibility i(F); an explicit derivation of the limit, including any scaling factors, is required.

    Authors: We agree that an explicit derivation strengthens the presentation. The manuscript states that the α-spectral radius tends to ℓ! times the number of induced copies as α → ∞, but the computation is currently left implicit from the definition. In the revision we will insert a short lemma (or expanded paragraph) in §2 that derives the limit explicitly, tracking all scaling factors and confirming the normalization matches the classical inducibility constant i(F). revision: yes

  2. Referee: [Theorem 1.1 and its proof] Theorem 1.1 (the spectral Brown-Sidorenko reduction): the argument that the extremal graph may be taken complete multipartite when F is complete multipartite relies on the specific form of the α-spectral radius. The proof should isolate the step where the complete-multipartite hypothesis on F is used to rule out non-multipartite extremal graphs, especially for the boundary case α = 1.

    Authors: We accept the suggestion to improve readability. The proof of Theorem 1.1 uses the complete-multipartite structure of F to guarantee that any optimal weighting can be replaced by an equitable complete-multipartite graph without decreasing the α-spectral radius; this step relies on the edge-transitivity properties induced by F being complete multipartite. We will revise the proof to isolate this replacement argument in a separate claim, with a dedicated paragraph addressing the case α = 1 (where the functional reduces to the ordinary spectral radius of the hypergraph). revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper defines the α-spectral radius of H_F(G) such that its α→∞ limit recovers ℓ! times the induced-copy count by explicit construction of the spectral parameter; this is a definitional property, not a derived claim. The central result is a reduction theorem (spectral analogue of Brown–Sidorenko) asserting that for complete multipartite F the extremal graph may be taken complete multipartite, for every α≥1. This reduction is stated as an independent theorem and does not reduce, by any equation or self-citation in the abstract, to a fitted parameter, a self-referential definition, or a load-bearing prior result by the same authors. The fact that the leading asymptotic equals the classical inducibility i(F) follows directly from the limit property and supplies no circularity in the reduction itself. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

Review performed from abstract only; full list of background assumptions and any ad-hoc choices cannot be extracted.

axioms (1)
  • standard math Standard properties of the alpha-spectral radius for uniform hypergraphs
    The limit statement as alpha tends to infinity is presented as a definitional fact.
invented entities (1)
  • hypergraph H_F(G) no independent evidence
    purpose: Encodes induced copies of F for spectral analysis
    New auxiliary construction introduced to define the spectral parameter.

pith-pipeline@v0.9.1-grok · 5741 in / 1226 out tokens · 32684 ms · 2026-06-28T22:20:03.452015+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 3 canonical work pages · 1 internal anchor

  1. [1]

    Balogh, P

    J. Balogh, P. Hu, B. Lidick´ y, and F. Pfender. Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle.European Journal of Combinatorics, 52:47–58, 2016

    2016

  2. [2]

    Bollob´ as, Y

    B. Bollob´ as, Y. Egawa, A. Harris, and G. Jin. The maximal number of inducedr-partite subgraphs. Graphs and Combinatorics, 11:1–19, 1995

    1995

  3. [3]

    J. I. Brown and A. Sidorenko. The inducibility of complete bipartite graphs.Journal of Graph Theory, 18:629–645, 1994

    1994

  4. [4]

    Even-Zohar and N

    C. Even-Zohar and N. Linial. A note on the inducibility of 4-vertex graphs.Graphs and Combinatorics, 31:1367–1380, 2015

    2015

  5. [5]

    G. Exoo. Dense packings of induced subgraphs.Ars Combinatoria, 22:5–10, 1986

    1986

  6. [6]

    J. Fox, H. Huang, and C. Lee. A solution to the inducibility problem for almost all graphs.Preprint, 2017

    2017

  7. [7]

    Friedman

    J. Friedman. Some graphs with small second eigenvalue.Combinatorica, 15(1):31–42, 1995. 13

    1995

  8. [8]

    Friedman and A

    J. Friedman and A. Wigderson. On the second eigenvalue of hypergraphs.Combinatorica, 15(1):43–65, 1995

    1995

  9. [9]

    Hatami, J

    H. Hatami, J. Hirst, and S. Norine. The inducibility of blow-up graphs.Journal of Combinatorial Theory, Series B, 109:196–212, 2014

    2014

  10. [10]

    J. Hirst. The inducibility of graphs on four vertices.Journal of Graph Theory, 75:231–243, 2014

    2014

  11. [11]

    Kang and V

    L. Kang and V. Nikiforov. Extremal problems for thep-spectral radius of graphs.Electronic Journal of Combinatorics, 21:Paper 3.21, 2014

    2014

  12. [12]

    Keevash, J

    P. Keevash, J. Lenz, and D. Mubayi. Spectral extremal problems for hypergraphs.SIAM Journal on Discrete Mathematics, 28:1838–1854, 2014

    2014

  13. [13]

    X. Liu. Spectral generalized Tur´ an problems.arXiv preprint arXiv:2507.21689, 2025

    work page arXiv 2025

  14. [14]

    X. Liu, J. Ma, and T. Zhu. The inducibility of Tur´ an graphs.arXiv preprint arXiv:2601.10548, 2026

    work page arXiv 2026

  15. [15]

    X. Liu, D. Mubayi, and C. Reiher. The feasible region of induced graphs.Journal of Combinatorial Theory, Series B, 158:105–135, 2023

    2023

  16. [16]

    Nikiforov

    V. Nikiforov. Some inequalities for the largest eigenvalue of a graph.Combinatorics, Probability and Computing, 11:179–189, 2002

    2002

  17. [17]

    Nikiforov

    V. Nikiforov. A spectral Erd˝ os–Stone–Bollob´ as theorem.Combinatorics, Probability and Computing, 18:455–458, 2009

    2009

  18. [18]

    Nikiforov

    V. Nikiforov. Some extremal problems for hereditary properties of graphs.Electronic Journal of Com- binatorics, 21:Paper 1.17, 2014

    2014

  19. [19]

    Pikhurko, J

    O. Pikhurko, J. Sliaˇ can, and K. Tyros. Strong forms of stability from flag algebra calculations.Journal of Combinatorial Theory, Series B, 135:129–178, 2019

    2019

  20. [20]

    Pippenger and M

    N. Pippenger and M. C. Golumbic. The inducibility of graphs.Journal of Combinatorial Theory, Series B, 19:189–203, 1975

    1975

  21. [21]

    A. A. Razborov. Flag algebras.Journal of Symbolic Logic, 72:1239–1282, 2007

    2007

  22. [22]

    R. Yuster. On the exact maximum induced density of almost all graphs and their inducibility.Journal of Combinatorial Theory, Series B, 136:81–109, 2019

    2019

  23. [23]

    R. Yuster. Inducibility inH-free graphs and inducibility of Tur´ an graphs.Journal of Combinatorial Theory, Series B, 178:1–26, 2026

    2026

  24. [24]

    Spectral extremal problems for the $(p,Q)$-spectral radius of hypergraphs

    J. Zheng, H. Li, and L. Su. Spectral extremal problems for the (p, Q)-spectral radius of hypergraphs. arXiv preprint arXiv:2510.02776, 2025. 14

    work page internal anchor Pith review Pith/arXiv arXiv 2025