simple_graph_is_far_colorable
A finite simple graph G on vertex type V is ε-far from being k-colorable if for every edge subset E' ⊆ E(G), whenever deleting E' from G leaves a k-colorable graph, the cardinality of E' is at least ε |V|².
Statement
def simple_graph_is_far_colorable {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) (ε : ℝ) : Prop
- Defined in
- combinatorics/2610-31489-near-optimal-bounds-for-testing-k-colorability.md:126
- Verified
- 25 Oct 2026
- Axioms
- none listed
- Used by 1
- simple_graph_is_far_colorable_iffA finite simple graph G on a type V with decidable equality and decidable adjacency is ε-far from being k-colorable if and only if every…
Read back from the Lean
A definition simple_graph_is_far_colorable parameterized by:
- a type V with [Fintype V] and [DecidableEq V]
- a simple graph G : SimpleGraph V with [DecidableRel G.Adj]
- a natural number k : ℕ
- a real number ε : ℝ
which asserts that:
for every finset of edges E' : Finset (Sym2 V) such that E' ⊆ G.edgeFinset,
if the graph obtained by deleting the edges of E' from G is k-colorable (i.e., has a proper vertex coloring with at most k colors),
then ε * (Fintype.card V : ℝ)^2 ≤ (E'.card : ℝ).
In other words, at least ε * |V|^2 edges must be deleted from G in order to make it k-colorable.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A finite simple graph G is ε-far from being k-colorable if at least ε |V|² edges must be deleted from G to make it k-colorable. -/ def simple_graph_is_far_colorable {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) (ε : ℝ) : Prop := ∀ E' ⊆ G.edgeFinset, (G.deleteEdges (E' : Set (Sym2 V))).Colorable k → ε * (Fintype.card V : ℝ) ^ 2 ≤ (E'.card : ℝ)