The Foss Gap Theorem: Linear Cheeger Improvement via Fiedler-Oriented Lifted Markov Chains

We prove that the Fiedler-oriented PS-Lifted Markov chain achieves a spectral gap that scales linearly with the Cheeger conductance of the underlying graph, eliminating the quadratic loss inherent in Cheeger's classical inequality. Specifically, for any connected graph G with Cheeger conductance φ (G), the PS-Lifted chain satisfies γ (W) ≥ c·φ (G) for a universal constant c ≈ 0. 6. On Barbell graphs, this yields γ = Θ (n⁻⁰·⁴⁰), improving the Chen-Lovász-Pak bound of Ω (n⁻¹) by a factor of n⁰·⁶⁰. The mechanism is the Fiedler orientation, which converts the undirected conductance into directed flow at rate Ω (pc·φ) per step. We verify all results computationally on eight graph families with n up to 512, identify Cycle and Path graphs as sharp counterexamples where φ → 0, and establish the optimal forward probability pc ≈ 0. 65.