cut_layer_potential
def
The 4-layer potential takes value 0 on vertices of X with no neighbors in Xᶜ, 1 on vertices of X with a neighbor in Xᶜ, 2 on vertices of Xᶜ with a neighbor in X, and 3 on vertices of Xᶜ with no neighbors in X.
Statement
def cut_layer_potential {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (X : Finset V) : V → ℝ
- Source
- step towards exists_dist_three_cut_potential_witness
- Verified
- 17 Oct 2026
- Axioms
- none listed
- Used by 3
- not_cut_layer_potential_avg_boundThe statement
cut_layer_potential_avg_boundis false: The statement has no hypothesis guaranteeing G.minDegree > 0. When G has an… - cut_layer_potential_diff_eq_threeFor any vertex x ∈ Xᶜ with no neighbours in X and y ∈ X with no neighbours in Xᶜ, cut_layer_potential G X x - cut_layer_potential G X y = 3.
- cut_layer_potential_lipschitzThe 4-layer potential satisfies f a - f b ≤ dist(a, b) for all vertices a, b.
- not_cut_layer_potential_avg_boundThe statement
Lean source view module on GitHub
/-- The canonical 4-layer potential for a cut (X, Xᶜ): 0 on the interior of X, 1 on the boundary of X, 2 on the boundary of Xᶜ, and 3 on the interior of Xᶜ. -/ def cut_layer_potential {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (X : Finset V) : V → ℝ := fun v => if v ∈ X then (if ∃ w ∈ (Xᶜ : Finset V), G.Adj v w then 1 else 0) else (if ∃ u ∈ X, G.Adj v u then 2 else 3)