pith. sign in

arxiv: 2607.00561 · v1 · pith:4Q7BF3P7new · submitted 2026-07-01 · 🧮 math.CO

For edge-color-critical graphs, non-r-partite spectral extremal graphs are edge extremal

Suil O , Jiadong Wu This is my paper

Pith reviewed 2026-07-02 11:10 UTC · model grok-4.3

classification 🧮 math.CO
keywords edge-color-critical graphsspectral extremal graphsTurán graphextremal numbernon-r-partite graphsadjacency spectral radiusFang-Zhai conjecture
0
0 comments X

The pith

For edge-color-critical graphs F with chromatic number r+1, non-r-partite F-free graphs that maximize adjacency spectral radius also maximize the number of edges when the extremal function is close to the Turán number.

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

The paper proves that if ex_{r+1}(n,F) equals the edge count of the Turán graph T_{n,r} minus floor(n/r) plus O(1) and F satisfies a structural condition on its sub-decomposition family, then the family of non-r-partite F-free graphs on n vertices attaining the maximum spectral radius is contained in the family attaining the maximum number of edges. This confirms the Fang-Zhai conjecture for the specific family F equal to the complete multipartite graph K_{1,1,t_3,...,t_{r+1}} with each t_i at least 2. A reader would care because the result shows when spectral and edge extremal problems have the same solution set rather than merely similar growth rates.

Core claim

Under the hypothesis that ex_{r+1}(n,F) = |E(T_{n,r})| - floor(n/r) + O(1) together with a structural condition on the sub-decomposition family of F, the paper shows EX_{r+1,ρ}(n,F) ⊆ EX_{r+1}(n,F). As the main application, for F = K_{1,1,t_3,...,t_{r+1}} with t_i ≥ 2 it proves the exact formula ex_{r+1}(n,F) = |E(T_{n,r})| - floor(n/r) + 2(t_min - 1) for all sufficiently large n, from which the inclusion follows.

What carries the argument

The sub-decomposition family of F, invoked together with the assumed asymptotic form of the extremal function to force the spectral maximizers to be edge maximizers.

If this is right

  • The exact extremal number for these F is |E(T_{n,r})| minus floor(n/r) plus twice the minimum t_i minus 2.
  • The spectral extremal family is contained inside the edge extremal family for these F and all large n.
  • The Fang-Zhai conjecture holds for every F of the form K_{1,1,t_3,...,t_{r+1}} with t_i ≥ 2.
  • Any further F for which the O(1) closeness hypothesis can be verified will automatically satisfy the spectral-edge inclusion.

Where Pith is reading between the lines

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

  • The same argument may extend to other edge-color-critical graphs once their extremal numbers are shown to be within O(1) of the Turán count minus n/r.
  • Computational checks for small r and moderate n could confirm whether the exact formula already holds below the 'sufficiently large' threshold.
  • The result suggests that for many multipartite forbidden graphs the spectral and edge problems are solved by the same near-Turán constructions.

Load-bearing premise

That the number of edges in any extremal graph is the Turán count minus roughly n/r plus a bounded constant, together with the sub-decomposition condition on F.

What would settle it

Existence, for arbitrarily large n, of a non-r-partite F-free graph whose edge count exceeds |E(T_{n,r})| - floor(n/r) + 2(t_min - 1) or whose spectral radius exceeds that of every graph with exactly that many edges.

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 Zhai conjectured that $\mathrm{EX}_{r+1,\rho}(n,F)\subseteq\mathrm{EX}_{r+1}(n,F)$ for every such $F$ and all large $n$. In this paper, we prove this inclusion under the hypothesis $\mathrm{ex}_{r+1}(n,F)=|E(T_{n,r})|-\lfloor n/r\rfloor+O(1)$, where $T_{n,r}$ is the Tur\'an graph, together with a structural condition on the sub-decomposition family of $F$. As the main application, 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 deduce that $\mathrm{EX}_{r+1,\rho}(n,F)\subseteq\mathrm{EX}_{r+1}(n,F)$.

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

1 major / 2 minor

Summary. The paper proves that for edge-color-critical F with χ(F)=r+1, if ex_{r+1}(n,F)=|E(T_{n,r})|−⌊n/r⌋+O(1) and a structural condition on the sub-decomposition family of F both hold, then EX_{r+1,ρ}(n,F)⊆EX_{r+1}(n,F). As the main application, for F=K_{1,1,t_3,…,t_{r+1}} (t_i≥2) the authors establish the exact value ex_{r+1}(n,F)=|E(T_{n,r})|−⌊n/r⌋+2(t_min−1) for large n (where t_min=min{t_3,…,t_{r+1}}), which implies the spectral-edge inclusion for this family.

Significance. If the results hold, the work gives a conditional proof of the Fang-Zhai conjecture under an explicit hypothesis that is then verified for a concrete infinite family of color-critical graphs, together with an exact (rather than O(1)) determination of the extremal number. This strengthens the link between spectral radius and edge-extremal problems in the non-r-partite setting and supplies a verifiable instance where the structural condition applies.

major comments (1)
  1. [§5] §5, proof of Theorem 5.3 (exact value of ex_{r+1}(n,F)): the lower bound follows from an explicit construction modifying T_{n,r} by deleting ⌊n/r⌋ edges and adding 2(t_min−1) edges; the upper bound invokes the sub-decomposition family to rule out other modifications, but the case analysis does not explicitly enumerate or exclude unbalanced part-size adjustments or alternative edge-addition patterns that could produce a larger O(1) term while remaining F-free and χ=r+1.
minor comments (2)
  1. [§2] Notation: the definition of the sub-decomposition family appears only in §2 and is used without restatement in §4; a brief reminder of its precise meaning would improve readability.
  2. [§3] The statement of the structural condition (used in the general theorem) is given as an assumption rather than derived; if it can be checked algorithmically for the given F, an explicit verification paragraph would strengthen the application.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and the constructive comment on the proof of Theorem 5.3. We respond to the major comment below.

read point-by-point responses

  1. Referee: [§5] §5, proof of Theorem 5.3 (exact value of ex_{r+1}(n,F)): the lower bound follows from an explicit construction modifying T_{n,r} by deleting ⌊n/r⌋ edges and adding 2(t_min−1) edges; the upper bound invokes the sub-decomposition family to rule out other modifications, but the case analysis does not explicitly enumerate or exclude unbalanced part-size adjustments or alternative edge-addition patterns that could produce a larger O(1) term while remaining F-free and χ=r+1.

    Authors: We agree that the case analysis in the upper bound of Theorem 5.3 would be strengthened by a more explicit enumeration of unbalanced part-size adjustments and alternative edge-addition patterns. The structural condition on the sub-decomposition family of F is intended to exclude configurations yielding a strictly larger O(1) term while preserving F-freeness and chromatic number r+1, but we acknowledge that the current presentation does not list these cases in full detail. In the revised manuscript we will expand the case analysis in Section 5 to enumerate and rule out these possibilities explicitly, thereby making the upper bound fully rigorous. revision: yes

Circularity Check

0 steps flagged

No circularity; proof conditional on explicit hypothesis with independent verification for specific F

full rationale

The paper states its main theorem as a conditional result: the spectral inclusion EX_{r+1,ρ}(n,F) ⊆ EX_{r+1}(n,F) holds under the standing hypothesis that ex_{r+1}(n,F) = |E(T_{n,r})| − ⌊n/r⌋ + O(1) together with a structural condition on the sub-decomposition family of F. For the concrete family F = K_{1,1,t_3,…,t_{r+1}} the authors then prove the sharpened exact value ex_{r+1}(n,F) = |E(T_{n,r})| − ⌊n/r⌋ + 2(t_min − 1) by exhibiting a construction and (implicitly) a stability argument that rules out denser non-r-partite F-free graphs; this exact count is derived directly from the definition of F and the Turán graph, not by fitting a parameter to data and re-deriving it. No self-citation is load-bearing, no ansatz is smuggled, and no quantity is defined in terms of a later-derived object. The derivation chain is therefore self-contained against external combinatorial benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard definitions of chromatic number, Turán graphs, and edge-color-criticality; the only non-standard inputs are the explicit hypothesis on ex and the structural condition on the sub-decomposition family, both stated as assumptions rather than derived.

axioms (2)
  • standard math Properties of the Turán graph T_{n,r} and the definition of non-r-partite graphs via chromatic number
    Invoked in the definitions of ex_{r+1}(n,F) and the families EX.
  • domain assumption The hypothesis ex_{r+1}(n,F) = |E(T_{n,r})| − ⌊n/r⌋ + O(1) and the structural condition on the sub-decomposition family of F
    The inclusion is proved only under these two premises; they are not shown to hold in general.

pith-pipeline@v0.9.1-grok · 5894 in / 1507 out tokens · 29681 ms · 2026-07-02T11:10:12.382340+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

16 extracted references · 1 canonical work pages

  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 M.Q

    L.F. Fang and M.Q. Zhai, Non-bipartite graphs without theta subgraphs.J. Algebr. Comb.,63(2026), 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]

    Liu, Extremal graphs for blow-ups of cycles and trees,Electron

    H. Liu, Extremal graphs for blow-ups of cycles and trees,Electron. J. Combin.20 (2013), no. 1, Paper 65

    2013

  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]

    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

  10. [10]

    Miao, R.F

    L. Miao, R.F. Liu, E. R. van Dam, Tur´ an number of books in non-bipartite graphs,J. Graph Theory(2025)

    2025

  11. [11]

    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

  12. [12]

    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

    2026

  13. [13]

    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

  14. [14]

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

    2023

  15. [15]

    Y. Wang, X. Cheng, E. Gy˝ ori, K. Varga and X. Zhao, Non-r-partite Tur´ an refinement of the critical edge theorem, preprint, 2026

    2026

  16. [16]

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

    work page arXiv 2025