pith. sign in

arxiv: 2604.02165 · v2 · submitted 2026-04-02 · 🧮 math.CO · math.SP

Almost all graphs have no cospectral mates with height relative small to its order

Da Zhao This is my paper

Pith reviewed 2026-05-13 20:41 UTC · model grok-4.3

classification 🧮 math.CO math.SP MSC 05C50
keywords cospectral graphsrandom graphsGM-switchingspectral graph theoryalmost all graphsheight of cospectral matesisospectral graphs
0
0 comments X

The pith

Almost all graphs on n vertices have no cospectral mates of height o((n / ln n)^{1/10}).

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

This paper shows that a vanishing fraction of graphs on n vertices possess a non-isomorphic cospectral mate whose height is o((n / ln n)^{1/10}). The argument improves earlier results restricted to fixed height and directly covers cospectral pairs produced by GM-switching on blocks of that scale. A sympathetic reader cares because it quantifies how rarely the spectrum fails to distinguish graphs when the alternative is structurally limited. The probabilistic counting in the random model thereby places a concrete lower bound on the size of any switch or modification needed to create an isospectral partner.

Core claim

The proportion of graphs of order n that admit a cospectral mate of height o((n / ln n)^{1/10}) tends to zero as n tends to infinity. This is established by a counting argument inside the Erdős–Rényi model that bounds the number of admissible mates at each admissible height and shows their total contribution is negligible.

What carries the argument

A probabilistic counting argument over the Erdős–Rényi random graph model that bounds the number of cospectral mates whose height, defined via the scale of GM-switching blocks, is o((n / ln n)^{1/10}).

If this is right

  • The spectrum determines the graph for almost every n-vertex graph when only low-height mates are considered.
  • GM-switching on blocks smaller than the stated height bound produces new cospectral graphs only for a vanishing fraction of inputs.
  • Earlier fixed-height results extend immediately to heights that grow, albeit slowly, with n.
  • Any cospectral pair that occurs with positive probability must involve structural modifications whose scale exceeds the given bound.

Where Pith is reading between the lines

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

  • Tighter height bounds may follow from sharper tail estimates on the number of possible switching sets.
  • The same counting technique could apply to other distance notions between graphs or to other matrix spectra such as the Laplacian.
  • In network reconstruction tasks the spectrum alone may suffice whenever candidate alternatives are restricted to small structural changes.

Load-bearing premise

The precise definition of height for cospectral mates and the Erdős–Rényi random graph model together make small-height pairs countable and negligible.

What would settle it

A construction of a positive-density family of graphs on n vertices, each admitting a cospectral mate via GM-switching on blocks of size much smaller than (n / ln n)^{1/10}, would falsify the claim.

read the original abstract

The main result of this paper shows that almost all graphs of order $n$ have no cospectral mates with height $o(( n / \ln n)^{1/10})$, improving an earlier result on cospectral mates with fixed level and covering the cospectral graphs obtained by GM-switching of relative small blocks.

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

0 major / 2 minor

Summary. The manuscript proves that almost all n-vertex graphs (in the Erdős–Rényi model G(n,1/2)) have no cospectral mate obtained by GM-switching on blocks of height o((n / ln n)^{1/10}). The argument is a direct counting argument showing that the expected number of such cospectral pairs is o(2^{binom(n,2)}), improving prior results limited to fixed-height switching.

Significance. If correct, the result supplies a quantitative, growing bound on the switching height for which cospectral mates remain exceptional. It strengthens the probabilistic picture that most graphs are determined by their spectra up to small perturbations and supplies a concrete improvement over fixed-level statements. The counting method is standard in the area and appears parameter-free once the height threshold is fixed.

minor comments (2)
  1. [§2] §2: the precise definition of height (as a function of the GM-switching block size or related invariant) should be stated explicitly before the main counting argument, as the o((n/ln n)^{1/10}) threshold depends on it.
  2. The error-term analysis in the union bound (controlling the probability that a random graph is cospectral to its switched version) would benefit from an explicit statement of the constants hidden in the o-notation.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and for recommending minor revision. The summary accurately captures the main result on the expected number of cospectral pairs via GM-switching with height o((n / ln n)^{1/10}). No specific major comments were listed in the report, so we have no point-by-point responses to address. We will incorporate any minor editorial adjustments in the revised version.

Circularity Check

0 steps flagged

No significant circularity; direct probabilistic counting argument

full rationale

The paper establishes its main claim via a direct counting argument in the Erdős–Rényi G(n,1/2) model: it bounds the expected number of cospectral pairs arising from GM-switching on blocks whose size is controlled by the height parameter o((n/ln n)^{1/10}), showing this expectation is o(2^{binom(n,2)}). The height is an externally defined parameter that limits block size in the switching construction; the derivation does not redefine height in terms of the cospectral property, fit any parameters to data and rename them as predictions, or rely on load-bearing self-citations whose content reduces to the present claim. All steps are standard union-bound estimates on the probability that a random graph is invariant under the switching operation, making the argument self-contained against the chosen random-graph measure and the explicit switching construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on the standard Erdős–Rényi random graph model and the definition of height for cospectral constructions; no free parameters or invented entities are visible in the abstract.

axioms (1)
  • domain assumption Standard properties of the Erdős–Rényi random graph G(n,p) for suitable p
    Used to establish that almost all graphs satisfy the no-small-height-mate property.

pith-pipeline@v0.9.0 · 5327 in / 1101 out tokens · 39753 ms · 2026-05-13T20:41:26.122135+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

27 extracted references · 27 canonical work pages · 2 internal anchors

  1. [1]

    Switching methods of level 2 for the construction of cospectral graphs

    arXiv: 2410.07948, doi:10.48550/arXiv.2410.07948. [BS09] A. E. Brouwer and E. Spence. Cospectral graphs on 12 vertices. The Electronic Journal of Combinatorics, 16(1):N20, June

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2410.07948

  2. [2]

    [GP56] Hs

    doi:10.1007/BF02189621. [GP56] Hs. H. Günthard and H. Primas. Zusammenhang von graphentheorie und MO-theorie von molekeln mit systemen konjugierter bindungen. Hel- vetica Chimica Acta , 39(6):1645–1653, January

    work page doi:10.1007/bf02189621

  3. [3]

    19560390623

    doi:10.1002/hlca. 19560390623. [GWW92] Carolyn Gordon, David L. Webb, and Scott Wolpert. One cannot hear the shape of a drum. Bulletin of the American Mathematical Society , 27(1):134– 138,

    work page doi:10.1002/hlca

  4. [4]

    [Har73] F

    doi:10.1090/S0273-0979-1992-00289-6 . [Har73] F. Harary. New directions in the theory of graphs

    work page doi:10.1090/s0273-0979-1992-00289-6 1992

  5. [5]

    [IS25] Ferdinand Ihringer and Robin Simoens

    doi: 10.1016/S0195-6698(03)00100-8. [IS25] Ferdinand Ihringer and Robin Simoens. Design switching on graphs. https://arxiv.org/abs/2508.11523v1, August

    work page doi:10.1016/s0195-6698(03)00100-8

  6. [6]

    11970915

    doi:10.1080/00029890.1966. 11970915. [KK24] Illya Koval and Matthew Kwan. Exponentially many graphs are determined by their spectrum, November

    work page doi:10.1080/00029890.1966 1966

  7. [7]

    [Mil64] J

    arXiv:2309.09788, doi:10.48550/ arXiv.2309.09788. [Mil64] J. Milnor. Eigenvalues of the laplace operator on certain manifolds. Pro- ceedings of the National Academy of Sciences , 51(4):542–542, April

    work page arXiv

  8. [8]

    [OT16] Sean O’Rourke and Behrouz Touri

    doi:10.1073/pnas.51.4.542. [OT16] Sean O’Rourke and Behrouz Touri. On a Conjecture of Godsil Concerning Controllable Random Graphs. SIAM Journal on Control and Optimization , 54(6):3347–3378, January

    work page doi:10.1073/pnas.51.4.542

  9. [9]

    [Sal23] Per Salberger

    doi:10.1137/15M1049622. [Sal23] Per Salberger. Counting rational points on projective varieties. Proceedings of the London Mathematical Society , 126(4):1092–1133, April

    work page doi:10.1137/15m1049622

  10. [10]

    [Tut79] W

    doi: 10.1112/plms.12508. [Tut79] W. T. Tutte. All the king’s horses. A guide to reconstruction. In Graph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977), pages 15–33. Academic Press, New York-London,

    work page doi:10.1112/plms.12508 1977

  11. [11]

    [vH03] Edwin R

    doi:10.1007/BF02941924. [vH03] Edwin R. van Dam and Willem H. Haemers. Which graphs are deter- mined by their spectrum? Linear Algebra and its Applications, 373:241–272, November

    work page doi:10.1007/bf02941924

  12. [12]

    [vH09] Edwin R

    doi:10.1016/S0024-3795(03)00483-X. [vH09] Edwin R. van Dam and Willem H. Haemers. Developments on spectral characterizations of graphs. Discrete Mathematics , 309(3):576–586, Febru- ary

    work page doi:10.1016/s0024-3795(03)00483-x

  13. [13]

    [Vu21] Van H

    doi:10.1016/j.disc.2008.08.019. [Vu21] Van H. Vu. Recent progress in combinatorial random matrix theory. Prob- ability Surveys , 18(none):179–200, January

    work page doi:10.1016/j.disc.2008.08.019 2008

  14. [14]

    [VVW26] Nils Van de Berg and Alexander Van Werde

    doi:10.1214/20-PS346. [VVW26] Nils Van de Berg and Alexander Van Werde. Are sparse graphs typically determined by their spectrum? https://arxiv.org/abs/2602.22757v1, Febru- ary

    work page doi:10.1214/20-ps346

  15. [15]

    arXiv:2602.00233, doi:10.48550/arXiv.2602. 00233. [WH25] Wei Wang and Ximei Huang. Almost all cographs have a cospectral mate, July

    work page doi:10.48550/arxiv.2602

  16. [16]

    [Wol79] Scott Wolpert

    arXiv:2507.16730, doi:10.48550/arXiv.2507.16730. [Wol79] Scott Wolpert. The length spectra as moduli for compact riemann surfaces. The Annals of Mathematics , 109(2):323, May

    work page doi:10.48550/arxiv.2507.16730

  17. [17]

    [WQH19] Wei Wang, Lihong Qiu, and Yulin Hu

    arXiv:1971114, doi: 10.2307/1971114. [WQH19] Wei Wang, Lihong Qiu, and Yulin Hu. Cospectral graphs, GM-switching and regular rational orthogonal matrices of level p. Linear Algebra and its Applications, 563:154–177, February

    work page doi:10.2307/1971114

  18. [18]

    doi:10.1016/j.laa.2018.10

    work page doi:10.1016/j.laa.2018.10 2018

  19. [19]

    On a generalization of the johnson-newman theorem to multiple rank-one perturbations

    [WW25] Wei Wang and Siqi Wu. On a generalization of the johnson-newman theorem to multiple rank-one perturbations. https://arxiv.org/abs/2512.12599v1, December

    work page arXiv

  20. [20]

    Results in Engineering29, 108898 (2026) https://doi.org/10.1016/j

    doi:10.1016/j. laa.2006.01.016. [WX06b] Wei Wang and Cheng-xian Xu. A sufficient condition for a family of graphs being determined by their generalized spectra. European Journal of Combi- natorics, 27(6):826–840, August

    work page doi:10.1016/j 2006

  21. [21]

    [WX07] Wei Wang and Cheng-Xian Xu

    doi:10.1016/j.ejc.2005.05.004. [WX07] Wei Wang and Cheng-Xian Xu. Note: On the generalized spectral charac- terization of graphs having an isolated vertex. Linear Algebra and its Appli- cations, 425(1):210–215, August

    work page doi:10.1016/j.ejc.2005.05.004 2005

  22. [22]

    11 [WX10] Wei Wang and Cheng-Xian Xu

    doi:10.1016/j.laa.2007.03.028. 11 [WX10] Wei Wang and Cheng-Xian Xu. On the asymptotic behavior of graphs determined by their generalized spectra. Discrete Mathematics , 310(1):70– 76, January

    work page doi:10.1016/j.laa.2007.03.028 2007

  23. [23]

    [WZ25] Wei Wang and Da Zhao

    doi:10.1016/j.disc.2009.07.028. [WZ25] Wei Wang and Da Zhao. Almost all graphs have no cospectral mate with fixed level, September

    work page doi:10.1016/j.disc.2009.07.028 2009

  24. [24]

    Do large language models perform latent multi-hop reasoning without exploiting shortcuts? abs/2411.16679, 2024

    arXiv:2509.05781, doi:10.48550/arXiv. 2509.05781. [WZ26] Wei Wang and Da Zhao. Graph isomorphism and multivariate graph spectrum. Advances in Applied Mathematics , 173:102994, February

    work page internal anchor Pith review doi:10.48550/arxiv

  25. [25]

    [Xia26] Ziqing Xiang

    doi:10.1016/j.aam.2025.102994. [Xia26] Ziqing Xiang. Natural graph spectra, January

    work page doi:10.1016/j.aam.2025.102994 2025

  26. [26]

    [XZ25] Yanrui Xu and Da Zhao

    arXiv:2602.00936, doi:10.48550/arXiv.2602.00936. [XZ25] Yanrui Xu and Da Zhao. Generalized block diagonal Laplacian spectrum of graphs, November

    work page doi:10.48550/arxiv.2602.00936

  27. [27]

    arXiv:2511.23246, doi:10.48550/arXiv.2511. 23246. 12

    work page doi:10.48550/arxiv.2511