Pith. sign in

REVIEW 5 minor 18 references

Under a structural condition on F, maximizing spectral radius among non-r-partite F-free graphs reduces to maximizing edges, and the maximizer is unique.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

For s-embeddable edge-color-critical F with the stated edge correction, spectral extremal non-r-partite F-free graphs are unique and edge-extremal; complete multipartite cases are fully classified.

T0 review reviewed 2026-07-14 challenge →

load-bearing objection Solid reduction that settles Fang–Lin under a clean hypothesis and finishes the multipartite spectral classification; the concurrent edge count is handled honestly.

arxiv 2607.00561 v3 pith:4Q7BF3P7 submitted 2026-07-01 math.CO

A reduction principle for non-r-partite spectral extremal problems, with a complete multipartite classification

Suil O , Jiadong Wu This is my paper
classification math.CO MSC 05C5005C35
keywords spectral radiusnon-r-partite graphedge-color-critical graphTurán numbercomplete multipartite graphs-embeddablesecular functionY_r(n)
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

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 attacks a spectral version of Turán-type questions in which the host graph is forced to have chromatic number larger than r. Fang and Lin conjectured that, for every edge-color-critical F of chromatic number r+1, every large graph that maximizes the adjacency spectral radius among non-r-partite F-free graphs also maximizes the number of edges. The authors prove a reduction principle that confirms the conjecture whenever F is s-embeddable and the edge extremal number is exactly the Turán number of T_{n,r} minus floor(n/r) plus 2(s-1). The reduction converts the spectral problem into a pure edge-counting problem by comparing secular functions of candidate graphs and extracting a second-order residual gain from the Rayleigh principle. They then verify the hypotheses for every complete multipartite F with exactly two singleton parts and t_min ≥ 2, obtaining both the exact edge count and a unique spectral maximizer (the balanced complete r-partite graph with one vertex joined to s-1 vertices in each of two throttled parts and completely to the rest). When three or more parts are singletons the embeddability condition fails, and a separate saturation argument shows that the unique maximizer is the Li–Peng graph Y_r(n). The result therefore settles the spectral problem for the entire family of edge-color-critical complete multipartite graphs.

Core claim

If F is edge-color-critical with χ(F)=r+1, is s-embeddable, and satisfies ex_{r+1}(n,F)=|E(T_{n,r})|-⌊n/r⌋+2(s-1) for large n, then every spectral extremal graph is edge extremal and is in fact unique: the balanced complete r-partite graph on n-1 vertices plus one vertex joined to exactly s-1 vertices in each of two smallest parts and to all other vertices. For F=K_{1,1,t_3,…,t_{r+1}} with t_i≥2 this formula holds with s=t_min; when t_3=1 the unique maximizer is instead Y_r(n).

What carries the argument

The s-embeddability condition (Definition 2.6): a vertex that meets a near-Turán host in at least s places of one part, one place of a second part, and fully off the rest already forces a copy of F, while the balanced graph throttled to s-1 neighbors in two parts remains F-free. Combined with direct comparison of secular functions and a Temple-type residual refinement of Rayleigh, this forces any spectral maximizer into the unique balanced throttled configuration.

Load-bearing premise

The forbidden graph must be s-embeddable: attaching a single vertex in the precise near-Turán pattern already creates a copy of F, while the same pattern with one fewer neighbor in each of two parts stays F-free.

What would settle it

Exhibit an s-embeddable edge-color-critical F for which the non-r-partite edge extremal number equals the claimed formula, yet some large non-r-partite F-free graph has strictly larger spectral radius than every edge-extremal example; or show that the claimed edge formula fails for some complete multipartite F with t_min≥2.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • For every complete multipartite F with exactly two singleton parts and t_min≥2 the spectral extremal graph is unique and coincides with the unique balanced throttled construction of size |E(T_{n,r})|-⌊n/r⌋+2(t_min-1).
  • The complete graph K_{r+1} and the complete split graphs B_{r,q} fall into the endpoint regime and both have unique non-r-partite spectral maximizer Y_r(n).
  • Any future edge-color-critical F that can be shown to be s-embeddable and to obey the same edge correction automatically inherits the spectral-to-edge inclusion and uniqueness.
  • The secular-function comparison and residual Rayleigh estimate supply reusable tools for other non-r-partite spectral problems whose first-order Rayleigh signal vanishes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same reduction should apply to any edge-color-critical family whose avoidance cost is exactly two throttled parts rather than one, even if the family is not multipartite.
  • When the edge extremal number sits farther from |E(T_{n,r})|-⌊n/r⌋ the reduction fails and a genuinely different spectral construction may appear; the paper’s methods give a template for locating that construction.
  • Theta graphs and other color-critical families already known to satisfy related edge estimates become natural next test cases once embeddability is checked or suitably weakened.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper studies non-r-partite spectral extremal problems for edge-color-critical F with χ(F)=r+1. It proves a reduction principle (Theorem 1.2): if F is s-embeddable and ex_{r+1}(n,F)=|E(T_{n,r})|-⌊n/r⌋+2(s-1) for large n, then EX_{r+1,ρ}(n,F)⊆EX_{r+1}(n,F) and the spectral maximizer is unique. The proof compares secular functions and uses a Temple-type residual refinement of Rayleigh. For complete multipartite F=K_{1,1,t_3,…,t_{r+1}} with t_i≥2 the authors establish the edge formula with s=t_min (Theorem 6.9), verify s-embeddability (Lemma 6.1), and identify the unique spectral extremal graph. The endpoint family with three or more singletons is treated separately by saturation reduction plus the Li–Peng theorem, yielding uniqueness of Y_r(n) (Theorem 4.1); K_{r+1} and B_{r,q} appear as special cases.

Significance. If correct, the work confirms the Fang–Lin conjecture under a clean structural hypothesis, supplies a reusable reduction that converts a spectral problem into an edge-counting one, and gives a complete spectral classification for all edge-color-critical complete multipartite forbidden graphs. The self-contained majorization proof of the edge formula (matching the concurrent independent count of Wang–Zhao) and the elementary but carefully applied secular-function and residual tools are genuine strengths; uniqueness of the spectral maximizer is stronger than the corresponding edge statement. The separation of the t_3=1 endpoint is methodologically clear and recovers known results for K_{r+1} and B_{r,q} as special cases.

minor comments (5)
  1. The abstract in the manuscript cuts off mid-sentence at "The complete graph K_{r+1} and the complete split graph B_{r,q}"; restore the missing closing clause for completeness.
  2. Introduction and abstract: a few spacing typos appear (e.g., "exceedsr", "largen", "exr+1"); a light copy-edit pass would remove them.
  3. Section 3: the long attachment analysis (Cases A–C of Lemma 3.4) would benefit from a one-paragraph roadmap at the start of the lemma stating the three cases and the role of the residual inequality, to help the reader navigate the casework.
  4. Section 5 table: the comparison table is useful; adding a short footnote that the edge formula for the endpoint family is known only in the special cases K_{r+1} and B_{r,q} (not claimed in general) would prevent misreading.
  5. References: the concurrent preprint of Wang–Zhao is properly acknowledged in the text and Section 7; ensure the final published citation is updated if a journal version appears before production.

Circularity Check

0 steps flagged

No significant circularity: reduction and multipartite classification rest on independent definitions, elementary spectral comparisons, and self-contained combinatorial counts.

full rationale

The load-bearing chain begins from external theorems (Simonovits edge-color-critical Turán, Desai et al. spectral stability, Li–Peng non-r-partite spectral Turán refinement) and the new but independently stated Definition 2.6 of s-embeddability. Theorem 1.2 assumes the edge formula as a hypothesis and derives the spectral inclusion by cleaning (Lemmas 2.8–2.16), attachment control via condition (E) (Lemma 3.3–3.4), and balancing via direct secular-function comparison plus Temple residual (Lemmas 2.4, 3.5); none of these steps defines a quantity in terms of the claimed maximizer. For the complete multipartite family the edge formula is proved from scratch (Construction 6.2 lower bound, majorization Lemma 6.5 and compensation Lemma 6.8 upper bound) and s-embeddability is verified by direct embedding (Lemma 6.1). The endpoint t_3=1 is handled by a separate saturation reduction to a K_{r+1}-free graph followed by Li–Peng, never invoking embeddability. Concurrent independent edge work of Wang–Zhao is acknowledged but not used. No parameter is fitted and recovered as a prediction, no uniqueness is imported from the authors’ prior papers, and no ansatz is smuggled via self-citation. The derivation is therefore self-contained against its stated hypotheses.

Axiom & Free-Parameter Ledger

0 free parameters · 6 axioms · 2 invented entities

The paper is pure extremal spectral graph theory. It imports classical theorems (Simonovits, spectral stability of Desai et al., Li–Peng refinement of Turán, Rayleigh and Temple-type inequalities) as black boxes and introduces one new structural definition (s-embeddability) whose two clauses are verified directly for the multipartite family. No numerical free parameters appear; all constants are combinatorial (part sizes, throttling thresholds, large-n thresholds).

axioms (6)
  • standard math Simonovits’s theorem: for edge-color-critical F with χ(F)=r+1, ex(n,F)=|E(T_{n,r})| for large n with unique extremal T_{n,r}.
    Invoked throughout the cleaning arguments (Theorem 2.1) to bound internal edges and missing cross edges.
  • standard math Spectral stability of Desai et al.: an F-free graph with spectral radius close to that of T_{n,r} differs from T_{n,r} by o(n²) edges.
    Theorem 2.2 supplies the starting near-Turán partition for every spectral extremal graph.
  • standard math Li–Peng spectral refinement: among non-r-partite K_{r+1}-free graphs the unique maximizer of spectral radius is Y_r(n).
    Theorem 2.3 is the terminal comparison tool for the endpoint family (Section 4).
  • standard math Rayleigh principle and the second-order residual (Temple-type) inequality of Lemma 2.4.
    Used to extract spectral gain when first-order kernels vanish (attachment and balancing steps).
  • ad hoc to paper F is s-embeddable (Definition 2.6): embedding criterion (E) and freeness certificate (T).
    The central structural hypothesis of the reduction principle; verified for complete multipartite graphs with t_min≥2 in Lemma 6.1.
  • domain assumption The edge extremal number equals |E(T_{n,r})|-⌊n/r⌋+2(s-1) for large n.
    Numerical hypothesis of Theorem 1.2; proved for the multipartite family in Theorem 6.9 by majorization and compensation lemmas.
invented entities (2)
  • s-embeddable graph (Definition 2.6) independent evidence
    purpose: Isolates the local attachment pattern that forces the two-throttled-part structure used by the reduction.
    New combinatorial definition introduced for the paper; independent evidence is the direct verification for complete multipartite graphs and the freeness of the throttled construction.
  • Y_r(n) (Li–Peng construction, recalled before Theorem 2.3) independent evidence
    purpose: The unique spectral maximizer for the endpoint family and for K_{r+1}-free non-r-partite graphs.
    Standard object from prior literature; used as the terminal comparison graph.

reviewed 2026-07-14 · how reviews work

0 comments
Cite this review

Pith. "Pith review of A reduction principle for non-$r$-partite spectral extremal problems, with a complete multipartite classification." pith.science (2026). https://pith.science/paper/4Q7BF3P7

@misc{pith2026260700561,
  author       = {Pith},
  title        = {Pith review of: A reduction principle for non-$r$-partite spectral extremal problems, with a complete multipartite classification},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4Q7BF3P7}},
  note         = {Machine review of arXiv:2607.00561}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

A graph is non-$r$-partite if its chromatic number exceeds $r$. For an edge-color-critical graph $F$ with $\chi(F)=r+1$, let $\mathrm{ex}_{r+1,\rho}(n,F)$ be the maximum adjacency spectral radius among non-$r$-partite $F$-free graphs of order $n$, and let $\mathrm{EX}_{r+1,\rho}(n,F)$ and $\mathrm{EX}_{r+1}(n,F)$ be the families of such graphs attaining, respectively, this maximum spectral radius and the maximum number of edges $\mathrm{ex}_{r+1}(n,F)$. Fang and Lin conjectured that $\mathrm{EX}_{r+1,\rho}(n,F)\subseteq\mathrm{EX}_{r+1}(n,F)$ for every such $F$ and all large $n$. We prove a reduction principle: if $F$ is \emph{$s$-embeddable} and $\mathrm{ex}_{r+1}(n,F)=|E(T_{n,r})|-\lfloor n/r\rfloor+2(s-1)$, where $T_{n,r}$ is the Tur\'an graph, then the inclusion holds and, moreover, the spectral extremal graph is unique. The reduction replaces the spectral problem by an edge-counting one, and its proof rests on a direct comparison of secular functions together with a second-order residual refinement of the Rayleigh principle. We then determine the spectral extremal graphs for all edge-color-critical complete multipartite forbidden graphs. For $F=K_{1,1,t_3,\ldots,t_{r+1}}$ with $t_3,\ldots,t_{r+1}\ge 2$ we show \[ \mathrm{ex}_{r+1}(n,F)=|E(T_{n,r})|-\Bigl\lfloor\frac nr\Bigr\rfloor+2(t_{\min}-1), \qquad t_{\min}:=\min\{t_3,\ldots,t_{r+1}\}, \] for all sufficiently large $n$, and we identify the unique spectral extremal graph; in particular $\mathrm{EX}_{r+1,\rho}(n,F)\subseteq\mathrm{EX}_{r+1}(n,F)$. The endpoint $t_3=1$ lies outside the embeddability framework and is treated by a separate argument: for $F=K_{1,1,1,t_4,\ldots,t_{r+1}}$ with $r\ge3$, the unique non-$r$-partite spectral extremal graph is $Y_r(n)$, obtained through a saturation reduction followed by the spectral refinement of Tur\'an's theorem. The complete graph $K_{r+1}$ and the complete split graph $B_{r,q}$

Review history (3 revisions) →

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

18 extracted references · 1 linked inside Pith

  1. [1]

    Brouwer and W.H

    A.E. Brouwer and W.H. Haemers,Spectra of Graphs, Universitext, Springer, New York, 2012

    2012

  2. [2]

    Desai, L.Y

    D.N. Desai, L.Y. Kang, Y.T. Li, Z.Y. Ni, M. Tait and J. Wang, Spectral extremal graphs for intersecting cliques,Linear Algebra Appl.,644(2022), 234–258

    2022

  3. [3]

    P. Erd˝ os, Some recent results on extremal problems in graph theory (Results), In: Theory of Graphs (International Symposium Rome, 1966), Gordon and Breach, New York, Dunod, Paris, 1966, pp. 117–123

    1966

  4. [4]

    Erd˝ os, On some new inequalities concerning extremal properties of graphs, In: Theory of Graphs (Proceedings of the Colloquium, Tihany, 1966), Academic Press, New York, 1968, pp

    P. Erd˝ os, On some new inequalities concerning extremal properties of graphs, In: Theory of Graphs (Proceedings of the Colloquium, Tihany, 1966), Academic Press, New York, 1968, pp. 77–81

    1966

  5. [5]

    Fang and H.Q

    L.F. Fang and H.Q. Lin, Non-bipartite graphs without theta subgraphs,J. Algebraic Combin.63(2026), Paper No. 58

    2026

  6. [6]

    Godsil and G

    C. Godsil and G. Royle,Algebraic Graph Theory, Graduate Texts in Mathematics207, Springer, New York, 2001

    2001

  7. [7]

    H.Q. Lin, B. Ning and B. Wu, Eigenvalues and triangles in graphs,Combin. Probab. Comput.30(2021), 258–270

    2021

  8. [8]

    Li and Y.J

    Y.T. Li and Y.J. Peng, Refinement on spectral Tur´ an’s theorem,SIAM J. Discrete Math.,37(2023), 2462–2485

    2023

  9. [9]

    Li and Y.J

    Y.T. Li and Y.J. Peng, The maximum spectral radius of non-bipartite graphs forbidding short odd cycles,Electron. J. Combin.29(2022), Paper No. P4.2

    2022

  10. [10]

    Liu and L

    R.F. Liu and L. Miao, Spectral Tur´ an problem of non-bipartite graphs: forbidden books, Eur. J. Comb.126(2025), 104136

    2025

  11. [11]

    Miao, R.F

    L. Miao, R.F. Liu, E. R. van Dam, Tur´ an number of books in non-bipartite graphs,J. Graph Theory112(2026), 442–455

    2026

  12. [12]

    Simonovits, A method for solving extremal problems in graph theory, stability prob- lems, in Theory of Graphs, Tihany, Hungary, 1966, Academic, New York, 1968, pp

    M. Simonovits, A method for solving extremal problems in graph theory, stability prob- lems, in Theory of Graphs, Tihany, Hungary, 1966, Academic, New York, 1968, pp. 279–319

    1966

  13. [13]

    Wang, W.W

    B. Wang, W.W. Chen and P. Zhang, Non-r-partite graphs without complete split sub- graphs,Discrete Math.349(2026), 114882. 39

    2026

  14. [14]

    West,Introduction to Graph Theory, 2nd ed., Prentice Hall, Upper Saddle River, NJ, 2001

    D.B. West,Introduction to Graph Theory, 2nd ed., Prentice Hall, Upper Saddle River, NJ, 2001

    2001

  15. [15]

    Wang, L.Y

    J. Wang, L.Y. Kang and Y.S. Xue, On a conjecture of spectral extremal problems,J. Combin. Theory Ser. B,159(2023), 20–41

    2023

  16. [16]

    Wang and X.M

    Y.P. Wang and X.M. Zhao, Non-r-partite Tur´ an refinement of the critical edge theorem, preprint, 2026

    2026

  17. [17]

    Yu and S.C

    Y.T. Yu and S.C. Li, Spectral Turan-type problem in non-r-partite graphs: forbidden generalized book graphB r,k, arXiv:2508.12034, 2025

    Pith/arXiv arXiv 2025

  18. [18]

    Zou, L.H

    L.T. Zou, L.H. Feng and Y.T. Li, Spectral extremal problems for non-bipartite graphs without odd cycles,Discrete Math.349(2026), 114670. 40

    2026

This paper was first reviewed by grok-4.5 on July 14, 2026.