Lax12.ColoringNumbers

Generalized coloring numbers

concepts/Lax12/ColoringNumbers.lean · lax-12

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Concept map

    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Definition

    Fix a linear ordering of the vertices of a graph G. A vertex u is weakly r-reachable from v if some path from v to u of length at most r has u as its smallest vertex, and strongly r-reachable from v if some path from v to u of length at most r has v as its smallest vertex apart from u itself. The weak r-coloring number wcol_r(G) and the strong r-coloring number scol_r(G) are the minima, over all orderings, of the largest number of vertices weakly respectively strongly r-reachable from a single vertex. A graph class has subpolynomial weak coloring numbers if for every radius r and every ε > 0 there is a constant c such that every subgraph H of a member, on m vertices, satisfies wcol_r(H) ≤ c · m^ε.

    Weak and strong reachability are Definition 2.1, and the two coloring numbers Definition 2.3, of Chapter 2 of the source lecture notes (2019/20 edition), which write scol_r where the earlier 2017/18 edition writes col_r. The subpolynomial bound is the conclusion of Theorem 3.4 of that chapter.

    Lean source view on GitHub

    1import Lax12.GraphClasses
    2import Mathlib.Combinatorics.SimpleGraph.Copy
    3import Mathlib.Combinatorics.SimpleGraph.Walk.Basic
    4import Mathlib.Data.Set.Card
    5import Mathlib.Data.Nat.Lattice
    6import Mathlib.Analysis.SpecialFunctions.Pow.Real
    7
    8/-!
    9---
    10title: Generalized coloring numbers
    11type: definition
    12---
    13Fix a linear ordering of the vertices of a graph *G*. A vertex *u* is
    14weakly *r*-reachable from *v* if some path from *v* to *u* of length at
    15most *r* has *u* as its smallest vertex, and strongly *r*-reachable from
    16*v* if some path from *v* to *u* of length at most *r* has *v* as its
    17smallest vertex apart from *u* itself. The weak *r*-coloring number
    18wcol_r(*G*) and the strong *r*-coloring number scol_r(*G*) are the
    19minima, over all orderings, of the largest number of vertices weakly
    20respectively strongly *r*-reachable from a single vertex. A graph class
    21has subpolynomial weak coloring numbers if for every radius *r* and
    22every ε > 0 there is a constant *c* such that every subgraph *H* of a
    23member, on *m* vertices, satisfies wcol_r(*H*) ≤ *c* · *m*^ε.
    24
    25Weak and strong reachability are Definition 2.1, and the two coloring
    26numbers Definition 2.3, of Chapter 2 of the source lecture notes
    27(2019/20 edition), which write scol_*r* where the earlier 2017/18
    28edition writes col_*r*. The subpolynomial bound is the conclusion of
    29Theorem 3.4 of that chapter.
    30
    31# Formalization notes
    32
    33An ordering of the vertices is a permutation `π` of `Fin m` assigning
    34each vertex its position. Both reachability sets are stated with walks,
    35as in the nowhere dense concept: shortcutting a walk to a path only
    36shrinks its support, so walks of length at most `r` reach exactly the
    37vertices that such paths do. In `wreach` the `π`-minimality of `u` on
    38the whole support already forces `π u ≤ π v`; in `sreach` only the
    39interior of the walk is constrained, so `π u ≤ π v` is a separate
    40conjunct. Both sets contain `v`.
    41
    42`wcol` and `scol` are the least achievable bounds `k`, `Nat.sInf`s over
    43nonempty sets — `k = m` works for any ordering — so the convention
    44`Nat.sInf ∅ = 0` is never exercised; the counts are `Set.ncard`. Weak
    45and strong coloring numbers are one review unit because they are the
    46same construction differing in a single clause, and every relation
    47between them is read off that contrast.
    48
    49The class-level bound is uniform over subgraph copies (`⊑`) of members,
    50each measured by its own vertex count `m`; this is the literature form
    51for subgraph-closed classes, and the uniformity is what localization
    52arguments downstream consume. At `m = 0` both sides vanish, so no
    53nonemptiness hypothesis is needed.
    54-/
    55
    56namespace Lax12.ColoringNumbers
    57
    58open scoped SimpleGraph
    59open Lax12.GraphClasses
    60
    61/-- The set of vertices weakly `r`-reachable from `v` in `G` under the
    62vertex ordering `π` (vertex `u` sits at position `π u`): the endpoints
    63`u` of walks from `v` of length at most `r` on whose support `u` is
    64`π`-minimal. Contains `v` itself. -/
    65def wreach {n : ℕ} (G : SimpleGraph (Fin n)) (π : Equiv.Perm (Fin n))
    66 (r : ℕ) (v : Fin n) : Set (Fin n) :=
    67 {u | ∃ w : G.Walk v u, w.length ≤ r ∧ ∀ y ∈ w.support, π u ≤ π y}
    68
    69/-- The set of vertices strongly `r`-reachable from `v` in `G` under the
    70vertex ordering `π`: the vertices `u` at or before `v` that are the
    71endpoint of a walk from `v` of length at most `r` all of whose other
    72vertices come strictly after `v`. Contains `v` itself. -/
    73def sreach {n : ℕ} (G : SimpleGraph (Fin n)) (π : Equiv.Perm (Fin n))
    74 (r : ℕ) (v : Fin n) : Set (Fin n) :=
    75 {u | π u ≤ π v ∧ ∃ w : G.Walk v u, w.length ≤ r ∧
    76 ∀ y ∈ w.support, y ≠ v → y ≠ u → π v < π y}
    77
    78/-- The weak `r`-coloring number of `G`: the least `k` such that under
    79some vertex ordering every vertex weakly `r`-reaches at most `k`
    80vertices. -/
    81noncomputable def wcol {n : ℕ} (G : SimpleGraph (Fin n)) (r : ℕ) : ℕ :=
    82 sInf {k | ∃ π : Equiv.Perm (Fin n), ∀ v, (wreach G π r v).ncard ≤ k}
    83
    84/-- The strong `r`-coloring number of `G`: the least `k` such that under
    85some vertex ordering every vertex strongly `r`-reaches at most `k`
    86vertices. -/
    87noncomputable def scol {n : ℕ} (G : SimpleGraph (Fin n)) (r : ℕ) : ℕ :=
    88 sInf {k | ∃ π : Equiv.Perm (Fin n), ∀ v, (sreach G π r v).ncard ≤ k}
    89
    90/-- Every subgraph of every member of the class, on `m` vertices, has
    91weak `r`-coloring number at most `c · m^ε`, where `c` depends only on
    92the radius `r` and on `ε > 0`: weak coloring numbers `m^{o(1)}`. -/
    93def HasSubpolynomialWcol (C : GraphClass) : Prop :=
    94 ∀ (r : ℕ) (ε : ℝ), 0 < ε → ∃ c : ℝ,
    95 ∀ (n : ℕ) (G : SimpleGraph (Fin n)), C n G →
    96 ∀ (m : ℕ) (H : SimpleGraph (Fin m)), H ⊑ G →
    97 (wcol H r : ℝ) ≤ c * (m : ℝ) ^ ε
    98
    99end Lax12.ColoringNumbers
    100

    Formalization notes

    An ordering of the vertices is a permutation ππ of FinmFin m assigning each vertex its position. Both reachability sets are stated with walks, as in the nowhere dense concept: shortcutting a walk to a path only shrinks its support, so walks of length at most rr reach exactly the vertices that such paths do. In wreachwreach the ππ-minimality of uu on the whole support already forces πuπvπ u ≤ π v; in sreachsreach only the interior of the walk is constrained, so πuπvπ u ≤ π v is a separate conjunct. Both sets contain vv.

    wcolwcol and scolscol are the least achievable bounds kk, Nat.sInfNat.sInfs over nonempty sets — k=mk = m works for any ordering — so the convention Nat.sInf=0Nat.sInf ∅ = 0 is never exercised; the counts are Set.ncardSet.ncard. Weak and strong coloring numbers are one review unit because they are the same construction differing in a single clause, and every relation between them is read off that contrast.

    The class-level bound is uniform over subgraph copies () of members, each measured by its own vertex count mm; this is the literature form for subgraph-closed classes, and the uniformity is what localization arguments downstream consume. At m=0m = 0 both sides vanish, so no nonemptiness hypothesis is needed.

    Community review

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.

    0 comments

    Loading discussion…