Lax12.ShallowTopologicalMinors
Shallow topological minors
concepts/Lax12/ShallowTopologicalMinors.lean · lax-12
No public endorsements yet.
Loading review…
Sign in with ORCIDConcept map
Definition
A graph H is a depth-r topological minor of a graph G if the graph obtained from H by subdividing every edge at most 2r times is a subgraph of G: the vertices of H are realized by distinct principal vertices of G, and every edge of H by a path of length at most 2r+1 between the principal vertices of its endpoints, these paths being internally disjoint from each other and from all principal vertices. A graph G has depth-r topological density at most d if every depth-r topological minor H of G has at most d · |V(H)| edges.
In the source lecture notes these are Definitions 2.15 and 2.16 of Chapter 1 (2019/20 edition): the topological minor relation is written H ⪯^top_r G, and the topological grad ∇̃_r(G) is the supremum of |E(H)|/|V(H)| over the depth-r topological minors H of G, so the density predicate here says ∇̃_r(G) ≤ d. The length bound 2r+1 is the notes' own convention, chosen so that a depth-r topological minor is in particular a depth-r minor.
Lean source view on GitHub
| 1 | import Mathlib.Combinatorics.SimpleGraph.Walk.Basic |
| 2 | import Mathlib.Data.Set.Card |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Shallow topological minors |
| 7 | type: definition |
| 8 | --- |
| 9 | A graph *H* is a depth-*r* topological minor of a graph *G* if the graph |
| 10 | obtained from *H* by subdividing every edge at most 2*r* times is a |
| 11 | subgraph of *G*: the vertices of *H* are realized by distinct principal |
| 12 | vertices of *G*, and every edge of *H* by a path of length at most |
| 13 | 2*r*+1 between the principal vertices of its endpoints, these paths |
| 14 | being internally disjoint from each other and from all principal |
| 15 | vertices. A graph *G* has depth-*r* topological density at most *d* if |
| 16 | every depth-*r* topological minor *H* of *G* has at most *d* · |V(H)| |
| 17 | edges. |
| 18 | |
| 19 | In the source lecture notes these are Definitions 2.15 and 2.16 of |
| 20 | Chapter 1 (2019/20 edition): the topological minor relation is written |
| 21 | *H* ⪯^top_*r* *G*, and the topological grad ∇̃_*r*(*G*) is the supremum |
| 22 | of |E(H)|/|V(H)| over the depth-*r* topological minors *H* of *G*, so |
| 23 | the density predicate here says ∇̃_*r*(*G*) ≤ *d*. The length bound |
| 24 | 2*r*+1 is the notes' own convention, chosen so that a depth-*r* |
| 25 | topological minor is in particular a depth-*r* minor. |
| 26 | |
| 27 | # Formalization notes |
| 28 | |
| 29 | The subdivision reading and the model stated here are the same notion: |
| 30 | subdividing an edge *k* times replaces it by a path of length *k*+1, so |
| 31 | a subdivision of *H* with at most 2*r* subdivisions per edge embeds into |
| 32 | *G* exactly when the vertices of *H* can be sent injectively to |
| 33 | principal vertices of *G* and the edges to connecting paths of length at |
| 34 | most 2*r*+1 that are pairwise internally disjoint and avoid all |
| 35 | principal vertices internally. The model carries that data directly. |
| 36 | |
| 37 | Connecting walks are indexed by *adjacent pairs* of vertices of `H` |
| 38 | rather than by the edge set, which keeps `Sym2` and its membership |
| 39 | plumbing off the surface. The two orientations of one edge therefore |
| 40 | each carry a walk, and the two are deliberately not required to be |
| 41 | reverses of each other: the `disjoint` field concludes that the two |
| 42 | edges agree, so it never fires on the two orientations of a single edge |
| 43 | and forces nothing between them. Either orientation's walk witnesses |
| 44 | that edge of the subdivision, and a model in the usual edge-indexed form |
| 45 | gives one here by sending the reversed orientation to the reversed walk. |
| 46 | |
| 47 | Walks rather than paths, as everywhere in this submission: bypassing a |
| 48 | walk to a path shortens it and shrinks its support, so it preserves both |
| 49 | the length bound and the disjointness conditions, and the two readings |
| 50 | define the same relation. `principal_inj` is not derivable from the |
| 51 | other fields — nothing constrains vertices of `H` that share no edge — |
| 52 | and it is exactly the notes' requirement that principal vertices be |
| 53 | distinct. |
| 54 | |
| 55 | No numeric topological grad is introduced, for the reason the |
| 56 | ordinary-minor density concept gives: every statement of this submission |
| 57 | supplies a concrete bound *d* rather than consuming a number, so a |
| 58 | `sInf`-defined ∇̃ would be review surface that no claim uses. Edges are |
| 59 | counted as the natural cardinality (`Set.ncard`) of `edgeSet`, and |
| 60 | minors range over the canonical carriers `Fin m`, as in the |
| 61 | ordinary-minor concepts. |
| 62 | -/ |
| 63 | |
| 64 | namespace Lax12.ShallowTopologicalMinors |
| 65 | |
| 66 | /-- A model of `H` as a depth-`r` topological minor of `G`: an injective |
| 67 | choice of a principal vertex of `G` for each vertex of `H`, together |
| 68 | with a connecting walk of length at most `2 * r + 1` for each edge of |
| 69 | `H`, where the walks pass through no principal vertex other than those |
| 70 | of their own two endpoints and meet each other only in principal |
| 71 | vertices. -/ |
| 72 | structure ShallowTopologicalMinorModel {V W : Type*} (r : ℕ) (H : SimpleGraph W) |
| 73 | (G : SimpleGraph V) where |
| 74 | /-- The principal vertex of `G` realizing each vertex of `H`. -/ |
| 75 | principal : W → V |
| 76 | /-- Distinct vertices of `H` have distinct principal vertices. -/ |
| 77 | principal_inj : Function.Injective principal |
| 78 | /-- The walk of `G` connecting the principal vertices of an edge of |
| 79 | `H`. -/ |
| 80 | walk : ∀ (u v : W), H.Adj u v → G.Walk (principal u) (principal v) |
| 81 | /-- Connecting walks have length at most `2 * r + 1`: they subdivide |
| 82 | the edge at most `2 * r` times. -/ |
| 83 | length_le : ∀ (u v : W) (h : H.Adj u v), (walk u v h).length ≤ 2 * r + 1 |
| 84 | /-- A principal vertex lying on a connecting walk is one of the two |
| 85 | endpoints of that edge. -/ |
| 86 | principal_eq : ∀ (u v : W) (h : H.Adj u v) (w : W), |
| 87 | principal w ∈ (walk u v h).support → w = u ∨ w = v |
| 88 | /-- Connecting walks meet only in principal vertices: a vertex lying |
| 89 | on two connecting walks and on none of the principal vertices forces |
| 90 | the two edges to agree. -/ |
| 91 | disjoint : ∀ (u v : W) (h : H.Adj u v) (u' v' : W) (h' : H.Adj u' v') (x : V), |
| 92 | x ∈ (walk u v h).support → x ∈ (walk u' v' h').support → |
| 93 | x ∉ Set.range principal → (u = u' ∧ v = v') ∨ (u = v' ∧ v = u') |
| 94 | |
| 95 | /-- `H` is a topological minor of `G` at depth `r`. -/ |
| 96 | def HasShallowTopologicalMinor {V W : Type*} (G : SimpleGraph V) (r : ℕ) |
| 97 | (H : SimpleGraph W) : Prop := |
| 98 | Nonempty (ShallowTopologicalMinorModel r H G) |
| 99 | |
| 100 | /-- Every depth-`r` topological minor of `G`, on `m` vertices, has at |
| 101 | most `d · m` edges. -/ |
| 102 | def HasTopologicalDensityAtMost {n : ℕ} (G : SimpleGraph (Fin n)) (r d : ℕ) : |
| 103 | Prop := |
| 104 | ∀ (m : ℕ) (H : SimpleGraph (Fin m)), HasShallowTopologicalMinor G r H → |
| 105 | H.edgeSet.ncard ≤ d * m |
| 106 | |
| 107 | end Lax12.ShallowTopologicalMinors |
| 108 |
Formalization notes
The subdivision reading and the model stated here are the same notion: subdividing an edge k times replaces it by a path of length k+1, so a subdivision of H with at most 2r subdivisions per edge embeds into G exactly when the vertices of H can be sent injectively to principal vertices of G and the edges to connecting paths of length at most 2r+1 that are pairwise internally disjoint and avoid all principal vertices internally. The model carries that data directly.
Connecting walks are indexed by adjacent pairs of vertices of rather than by the edge set, which keeps and its membership plumbing off the surface. The two orientations of one edge therefore each carry a walk, and the two are deliberately not required to be reverses of each other: the field concludes that the two edges agree, so it never fires on the two orientations of a single edge and forces nothing between them. Either orientation's walk witnesses that edge of the subdivision, and a model in the usual edge-indexed form gives one here by sending the reversed orientation to the reversed walk.
Walks rather than paths, as everywhere in this submission: bypassing a walk to a path shortens it and shrinks its support, so it preserves both the length bound and the disjointness conditions, and the two readings define the same relation. is not derivable from the other fields — nothing constrains vertices of that share no edge — and it is exactly the notes' requirement that principal vertices be distinct.
No numeric topological grad is introduced, for the reason the ordinary-minor density concept gives: every statement of this submission supplies a concrete bound d rather than consuming a number, so a -defined ∇̃ would be review surface that no claim uses. Edges are counted as the natural cardinality () of , and minors range over the canonical carriers , as in the ordinary-minor concepts.
Builds on
none
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