Lax12.ShallowTopologicalMinors

Shallow topological minors

concepts/Lax12/ShallowTopologicalMinors.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

    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

    1import Mathlib.Combinatorics.SimpleGraph.Walk.Basic
    2import Mathlib.Data.Set.Card
    3
    4/-!
    5---
    6title: Shallow topological minors
    7type: definition
    8---
    9A graph *H* is a depth-*r* topological minor of a graph *G* if the graph
    10obtained from *H* by subdividing every edge at most 2*r* times is a
    11subgraph of *G*: the vertices of *H* are realized by distinct principal
    12vertices of *G*, and every edge of *H* by a path of length at most
    132*r*+1 between the principal vertices of its endpoints, these paths
    14being internally disjoint from each other and from all principal
    15vertices. A graph *G* has depth-*r* topological density at most *d* if
    16every depth-*r* topological minor *H* of *G* has at most *d* · |V(H)|
    17edges.
    18
    19In the source lecture notes these are Definitions 2.15 and 2.16 of
    20Chapter 1 (2019/20 edition): the topological minor relation is written
    21*H* ⪯^top_*r* *G*, and the topological grad ∇̃_*r*(*G*) is the supremum
    22of |E(H)|/|V(H)| over the depth-*r* topological minors *H* of *G*, so
    23the density predicate here says ∇̃_*r*(*G*) ≤ *d*. The length bound
    242*r*+1 is the notes' own convention, chosen so that a depth-*r*
    25topological minor is in particular a depth-*r* minor.
    26
    27# Formalization notes
    28
    29The subdivision reading and the model stated here are the same notion:
    30subdividing an edge *k* times replaces it by a path of length *k*+1, so
    31a 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
    33principal vertices of *G* and the edges to connecting paths of length at
    34most 2*r*+1 that are pairwise internally disjoint and avoid all
    35principal vertices internally. The model carries that data directly.
    36
    37Connecting walks are indexed by *adjacent pairs* of vertices of `H`
    38rather than by the edge set, which keeps `Sym2` and its membership
    39plumbing off the surface. The two orientations of one edge therefore
    40each carry a walk, and the two are deliberately not required to be
    41reverses of each other: the `disjoint` field concludes that the two
    42edges agree, so it never fires on the two orientations of a single edge
    43and forces nothing between them. Either orientation's walk witnesses
    44that edge of the subdivision, and a model in the usual edge-indexed form
    45gives one here by sending the reversed orientation to the reversed walk.
    46
    47Walks rather than paths, as everywhere in this submission: bypassing a
    48walk to a path shortens it and shrinks its support, so it preserves both
    49the length bound and the disjointness conditions, and the two readings
    50define the same relation. `principal_inj` is not derivable from the
    51other fields — nothing constrains vertices of `H` that share no edge —
    52and it is exactly the notes' requirement that principal vertices be
    53distinct.
    54
    55No numeric topological grad is introduced, for the reason the
    56ordinary-minor density concept gives: every statement of this submission
    57supplies a concrete bound *d* rather than consuming a number, so a
    58`sInf`-defined ∇̃ would be review surface that no claim uses. Edges are
    59counted as the natural cardinality (`Set.ncard`) of `edgeSet`, and
    60minors range over the canonical carriers `Fin m`, as in the
    61ordinary-minor concepts.
    62-/
    63
    64namespace Lax12.ShallowTopologicalMinors
    65
    66/-- A model of `H` as a depth-`r` topological minor of `G`: an injective
    67choice of a principal vertex of `G` for each vertex of `H`, together
    68with 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
    70of their own two endpoints and meet each other only in principal
    71vertices. -/
    72structure 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`. -/
    96def 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
    101most `d · m` edges. -/
    102def 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
    107end 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 HH rather than by the edge set, which keeps Sym2Sym2 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 disjointdisjoint 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. principalinjprincipal_inj is not derivable from the other fields — nothing constrains vertices of HH 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 sInfsInf-defined ∇̃ would be review surface that no claim uses. Edges are counted as the natural cardinality (Set.ncardSet.ncard) of edgeSetedgeSet, and minors range over the canonical carriers FinmFin m, as in the ordinary-minor concepts.

    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…