The Strengthened Hanna Neumann Conjecture I: A Combinatorial Proof

Abstract

We prove the Strengthened Hanna Neumann Conjecture, in its common graph theoretic formulation. Our original approach to this conjecture used cohomology of sheaves on graphs, although here we give a short combinatorial proof that we found in a succession of simplifications of the cohomological approach. Our proof is inductive, and requires Tardos' previous result settling the rank two case of the conjecture.

This has been withdrawn due to an error

References in corpus (3)

• A short proof that positive generation implies the Hanna Neumann Conjecture
• On the Hanna Neumann Conjecture
• Cohomology in Grothendieck Topologies and Lower Bounds in Boolean Complexity II: A Simple Example