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