simple_graph_binding_number
def
bind(G) = min{|N_G(S)|/|S| : ∅ ≠ S ⊆ V(G), N_G(S) ≠ V(G)}, where N_G(S) is the union of the neighbourhoods of the vertices of S.
Statement
noncomputable def simple_graph_binding_number {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : ℝ
- Defined in
- arXiv:2610.28536 (A sharp bound on the binding number of K_k-free graphs and the Brandt conjecture), Sec. 1, definition of bind(G)
- Verified
- 21 Oct 2026
- Axioms
- none listed
- Used by 3
- simple_graph_binding_number_completeThe complete graph K_n (n ≥ 2) has binding number n − 1: a singleton {v} has N = V∖{v}, and any S with two vertices has N(S) = V.
- simple_graph_binding_number_le_iffFor a graph on a nonempty finite vertex set, bind(G) ≤ c iff some nonempty S with N(S) ≠ V has |N(S)| ≤ c|S| (the infimum is a minimum…
- simple_graph_binding_number_complete_four_partiteThe complete 4-partite graph with four parts of size m ≥ 1 is K_5-free and has binding number exactly 3, so the bound 3 conjectured for…
Lean source view module on GitHub
/-- The binding number of a finite graph: the least ratio |N(S)|/|S| over nonempty vertex sets S whose neighbourhood N(S) (the union of the open neighbourhoods of the vertices of S) is not the whole vertex set (0 on the empty vertex type). -/ noncomputable def simple_graph_binding_number {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : ℝ := ⨅ S : {S : Finset V // S.Nonempty ∧ S.biUnion (fun v => G.neighborFinset v) ≠ Finset.univ}, ((S.1.biUnion (fun v => G.neighborFinset v)).card : ℝ) / S.1.card