← All papers
First page of Median eigenvalues of subcubic graphs

Median eigenvalues of subcubic graphs

Hricha Acharya, Benjamin Jeter, Zilin Jiang

math.CO Feb 18, 2025 · v3
The case analysis behind key lemmas is formalized in Lean 4 with AI assistance (Codex/GPT), and the Lean project is shipped as arXiv ancillary files.
We show that the median eigenvalues of every connected graph of maximum degree at most three, except for the Heawood graph, are at most $1$ in absolute value, resolving open problems posed by Fowler and Pisanski, and by Mohar.

The question is whether the median eigenvalues of every connected subcubic graph lie in [-1,1], the Heawood graph excepted. This resolves open problems of Fowler–Pisanski and Mohar.

The argument uses Cauchy interlacing through positive and negative tail estimates relative to a maximum cut. It then performs an extensive case analysis of local configurations: cut enhancers and positive and negative tail reducers. As an independent check, the case analysis and its use in Lemmas 2.7 and 2.8 were formalized in Lean 4 with Codex and an OpenAI GPT model. The authors reviewed the formal statements.

The median eigenvalues of every connected subcubic graph other than the Heawood graph are at most 1 in absolute value, and a positive-fraction strengthening is also proved. The ancillary Lean project builds successfully.