Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ ZENODOarrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
ZENODO
Preprint
Data sources: ZENODO
addClaim

Unfolding a Graph into a Tree: A Machine-Checked Proof of the Heilmann-Lieb Theorem in Lean 4 (Part II)

Authors: Carles Marín Muñoz;

Unfolding a Graph into a Tree: A Machine-Checked Proof of the Heilmann-Lieb Theorem in Lean 4 (Part II)

Abstract

A machine-checked formalization, in Lean 4 / Mathlib, of the Heilmann-Lieb theorem: the matching polynomial mu_G of every finite graph is real-rooted, and for maximum degree Delta >= 2 all its roots lie in the Ramanujan band [-2 sqrt(Delta-1), 2 sqrt(Delta-1)]. The proof follows Godsil's path tree: unfold G into the tree T(G,u) of its paths (where the matching polynomial equals a characteristic polynomial) and transport back along the divisibility mu_G | mu_{T(G,u)}; the root bound is proved from scratch by a weighted Gershgorin / Collatz-Wielandt argument reduced to two facts about distances in a tree. All headline theorems are sorry-free (axioms: propext, Classical.choice, Quot.sound). It formalizes classical mathematics and claims no new theorem; the novelty is the formalization, supported by a search of the Lean/Mathlib, Isabelle/AFP and Coq/mathcomp ecosystems. Lean sources: github.com/karlesmarin/godsil-gutman-lean. English and Spanish editions are included, with the full Lean 4 sources.

Powered by OpenAIRE graph
Found an issue? Give us feedback