Ordering with bounded later neighbours inside a vertex set
DefinitionSparseDisc_Supplement_HasLaterBoundOngraph-degeneracygraph-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-discrepancy
The vertices of have a later-neighbour bound if they admit an ordering in which every vertex has at most later neighbours that also belong to .
Definition code
import Mathlib
namespace SparseDisc.Supplement
open Classical in
/-- The vertices in `W` admit an ordering in which every vertex has at most `d` later neighbours
also in `W`, as used for `V₁` in Theorem 8.22(d) (Zeng–Cao–Dai–Wang–Liao, *Sparse Discrepancy
Beyond Additive Functions*, STOC 2027 submission manuscript (sha256 0f09ec60…25b81), p.38). -/
noncomputable def HasLaterBoundOn {V : Type} [Fintype V]
(G : SimpleGraph V) (W : Finset V) (d : ℕ) : Prop :=
∃ r : V → ℕ, Function.Injective r ∧ ∀ v ∈ W,
(W.filter (fun w => G.Adj v w ∧ r v < r w)).card ≤ d
end SparseDisc.Supplement
Source
Zeng–Cao–Dai–Wang–Liao, Sparse Discrepancy Beyond Additive Functions, STOC 2027 submission (manuscript sha256 0f09ec60…), Theorem 8.22(d), p.38