The ordered matching number bounds the inertia of zero-diagonal graph matrices
Version 2 (correction). Version 1 of this record presented an invariant zeta(G) as new. A prior-art search carried out after its release showed that zeta(G) is the ordered matching number of Constantinescu and Varbaro (2011), also known as the semi-induced matching number (Chalermsook, Laekhanukit, Nanongkai, 2013). Version 2 corrects the title, the attribution and several statements, and withdraws the overstatements of version 1; Section 9 of the paper lists the corrections. Abstract. For a graph G, consider the real symmetric matrices with zero diagonal whose off-diagonal nonzero pattern is the edge set of G. We observe that every such matrix has at least nu-o(G) negative and at least nu-o(G) positive eigenvalues, where nu-o is the ordered matching number. The proof is elementary (pendant-vertex inertia lemma and Cauchy interlacing). We also note a zero-forcing description of the ordered matching number and a join formula. The main content is computational: with exact-arithmetic certificates, the bound is attained for every connected graph on at most 8 vertices, while exactly 18 of the 261080 connected graphs on 9 vertices are proved to have ordered matching number 3 and minimum inertia 4 (6 remain undecided). A recursive Schur-complement refinement accounts for all 18. Important: this work was produced with substantial assistance from AI systems (Claude, Anthropic), including the prior-art search. The proofs were cross-checked by independent AI reviewer agents and by exhaustive computation, but have NOT been reviewed by a human specialist; the literature search is necessarily incomplete. The results should be treated as claims awaiting independent verification. Code (MIT licence), certificates, the AI reviewers' reports and the prior-art reports are included.
Authors
- Antoine Delorme
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-16
- DOI
- https://doi.org/10.5281/zenodo.24290048
- Primary Topic
- Graph theory and applications
- Type
- preprint