While this submission is a draft, it cannot be used by other submissions.

Graphs of bounded treewidth

Lax119563.TreewidthClasses · concepts/Lax119563/TreewidthClasses.lean · lax-119563

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.

    Natural Language Statement

    Definition

    For k≥0k \geq 0, the class Tk\mathcal T_k consists of all finite simple graphs of treewidth at most kk. It is closed under isomorphism, so it is a graph class.

    Concept map
    3 concepts; 1 descendant hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Lax228581.Treewidth
    2import Lax871432.GraphClasses
    3
    4/-!
    5---
    6title: Graphs of bounded treewidth
    7type: definition
    8---
    9For k≥0k \geq 0, the class Tk\mathcal T_k consists of all finite simple graphs of treewidth at
    10most kk. It is closed under isomorphism, so it is a graph class.
    11
    12# Implementation notes
    13
    14Tree decompositions and treewidth are those of `Lax228581.Treewidth`, and graph classes those
    15of `Lax871432.GraphClasses`. Isomorphism invariance holds since an isomorphism carries a tree
    16decomposition to one with the same tree and bags of the same sizes.
    17-/
    18
    19open Lax228581.Treewidth Lax871432.GraphClasses
    20
    21namespace Lax119563.TreewidthClasses
    22
    23/-- An isomorphism `e : F ≃g F'` carries a tree decomposition of `F` to one of `F'` with the
    24same tree and the images of the bags. -/
    25private def mapTreeDecomposition {V W : Type} {F : SimpleGraph V} {F' : SimpleGraph W} (e : F ≃g F')
    26 (D : TreeDecomposition F) : TreeDecomposition F' where
    27 Node := D.Node
    28 nodeFintype := D.nodeFintype
    29 tree := D.tree
    30 isTree := D.isTree
    31 bag i := (D.bag i).map e.toEquiv.toEmbedding
    32 vertex_mem_bag v := by
    33 obtain ⟨i, hi⟩ := D.vertex_mem_bag (e.symm v)
    34 exact ⟨i, Finset.mem_map.2 ⟨e.symm v, hi, by simp⟩⟩
    35 edge_mem_bag u v huv := by
    36 obtain ⟨i, hu, hv⟩ := D.edge_mem_bag (e.symm.map_adj_iff.2 huv)
    37 exact ⟨i, Finset.mem_map.2 ⟨e.symm u, hu, by simp⟩, Finset.mem_map.2 ⟨e.symm v, hv, by simp⟩⟩
    38 bag_indices_connected v := by
    39 have h : {i | v ∈ (D.bag i).map e.toEquiv.toEmbedding} = {i | e.symm v ∈ D.bag i} := by
    40 ext i
    41 simp only [Set.mem_ofPred_eq, Finset.mem_map_equiv]
    42 rfl
    43 rw [h]
    44 exact D.bag_indices_connected (e.symm v)
    45
    46private theorem hasTreewidthAtMost_congr {V W : Type} {F : SimpleGraph V} {F' : SimpleGraph W}
    47 (e : F ≃g F') (w : ℕ) : HasTreewidthAtMost F w → HasTreewidthAtMost F' w := by
    48 rintro ⟨D, hD⟩
    49 exact ⟨mapTreeDecomposition e D, fun i => by
    50 simpa [mapTreeDecomposition] using hD i⟩
    51
    52/-- The class `𝒯_k` of finite simple graphs of treewidth at most `k`. -/
    53def treewidthClass (k : ℕ) : GraphClass where
    54 Mem F := HasTreewidthAtMost F k
    55 mem_congr := by
    56 rintro V W _ _ F F' ⟨e⟩
    57 exact ⟨hasTreewidthAtMost_congr e k, hasTreewidthAtMost_congr e.symm k⟩
    58
    59end Lax119563.TreewidthClasses
    60

    Implementation notes

    Tree decompositions and treewidth are those of Lax228581.TreewidthLax228581.Treewidth, and graph classes those of Lax871432.GraphClassesLax871432.GraphClasses. Isomorphism invariance holds since an isomorphism carries a tree decomposition to one with the same tree and bags of the same sizes.

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…