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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

The ordered matching number bounds the inertia of zero-diagonal graph matrices

Antoine Delorme
1 links
Zenodo (CERN European Organization for Nuclear Research)
Graph theory and applications
preprint

The ordered matching number bounds the inertia of zero-diagonal graph matrices

Antoine Delorme
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Graph theory and applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon