Ordinary random-walk gap above one seventh forces strict small-cut expansion
ProvedOPG37364.smallCut_expansion_of_spectralGap_gt_one_seventhexpander-graphsgraph-theorymarkov-chainsspectral-gap
Let be a connected -regular finite simple graph on vertices. Let be its ordinary simple-random-walk transition matrix, with entry on an adjacency and zero otherwise. Write for the ordinary spectral gap, where is the largest real eigenvalue different from one.
If , then every nonempty proper shore satisfying has strictly more crossing pairs than vertices:
Each crossing edge is counted once, from into its complement. The spectral inequality and the expansion conclusion are both strict. The theorem requires neither bipartiteness nor a girth bound, and uses the ordinary gap rather than the absolute gap.
Preamble
import Definitions.Def_opg37364_cut_pairs import Definitions.Def_mm_spectral set_option autoImplicit false open scoped Classical
Formal statement
namespace OPG37364
theorem smallCut_expansion_of_spectralGap_gt_one_seventh
{n : ℕ} (hn : 2 ≤ n) (G : SimpleGraph (Fin n))
(hconn : IsConnected G) (hreg : IsRegularOfDegree G 14)
(hgap : (1 : ℝ) / 7 < MarkovMixing.spectralGap (MarkovMixing.graphWalk G)) :
∀ S : Set (Fin n), S.Nonempty → Sᶜ.Nonempty →
S.encard ≤ Sᶜ.encard → S.encard < (cutPairs G S).encard := by sorry
end OPG37364
Source
A regular-graph consequence of Levin--Peres--Wilmer, Markov Chains and Mixing Times, Theorem 13.14 (upper Cheeger bound), as formalized by MarkovMixing.cheeger_upper, Prove2Me ID 8e914dfd-cd15-4c4b-b173-c4c80670bd47, accepted solution https://prove2.me/api/v1/submissions/eff72ab6-82ba-426f-a096-60e18752c4dc/solution . Applied to the expansion route in Feghali--Lucke--Paulusma--Ries, Algorithmica 87 (2025), Lemma 5, https://link.springer.com/article/10.1007/s00453-025-01318-8