Peeling by vertices of current degree at most
DefinitionSparseDisc_Supplement_PeelsToAtMostgraph-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-discrepancy
A graph peels to at most vertices when repeated deletion of a vertex having at most two neighbours in the current graph leaves a residual graph with at most vertices. An injective rank records the deletion order.
Definition code
import Mathlib
namespace SparseDisc.Supplement
open Classical in
/-- `PeelsToAtMost G k`: repeated deletion of a current vertex having at most two current
neighbours leaves at most `k` vertices (Zeng–Cao–Dai–Wang–Liao, *Sparse Discrepancy Beyond Additive
Functions*, STOC 2027 submission manuscript (sha256 0f09ec60…25b81), Theorem 8.35, p.45).
**Formalization Note** `W` is the final residual graph. Injective ranks order deleted vertices;
when `v` is deleted, its current neighbours are the later-ranked deleted vertices together with
the vertices of `W`. -/
noncomputable def PeelsToAtMost {V : Type} [Fintype V]
(G : SimpleGraph V) (k : ℕ) : Prop :=
∃ W : Finset V, W.card ≤ k ∧ ∃ r : V → ℕ, Function.Injective r ∧
∀ v, v ∉ W →
(Finset.univ.filter (fun w => G.Adj v w ∧ (w ∈ W ∨ r v < r w))).card ≤ 2
end SparseDisc.Supplement
Source
Zeng–Cao–Dai–Wang–Liao, Sparse Discrepancy Beyond Additive Functions, STOC 2027 submission (manuscript sha256 0f09ec60…), Theorem 8.35, p.45