Δ-forestwidth
Lax461425.Forestwidth · concepts/Lax461425/Forestwidth.lean · lax-461425
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
A tree decomposition of a graph is a tree with bags for such that every vertex of lies in some bag, both endpoints of every edge lie in a common bag, and, for every vertex of , the nodes whose bags contain induce a connected subtree of . Edge multiplicities play no role.
Let . The -forestwidth of is the least such that admits a tree decomposition with root such that has depth at most , , and for all . Equivalently, deleting yields a forest decomposition of in which every root-leaf path has at most nodes. This is a modification of the -treewidth, for which this forest decomposition is required to be a tree decomposition.
We formalise the statement as the existence of such a decomposition. A rooted tree of depth at most is given by its finite set of nodes, its root , and the parent map, extended by , such that for every node . In such a tree, a set of nodes induces a connected subtree if, and only if, at most one node is the root or has its parent outside . As the root bag is empty, it suffices to require for every vertex that at most one node has and .
Concept map
Lean source view on GitHub
| 1 | import Mathlib.Data.Fintype.Sum |
| 2 | import Mathlib.Logic.Function.Iterate |
| 3 | import Lax461425.HomomorphismPolynomials |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Δ-forestwidth |
| 8 | type: definition |
| 9 | --- |
| 10 | A *tree decomposition* of a graph is a tree with bags for |
| 11 | such that every vertex of lies in some bag, both endpoints of every edge lie |
| 12 | in a common bag, and, for every vertex of , the nodes whose bags contain induce a |
| 13 | connected subtree of . Edge multiplicities play no role. |
| 14 | |
| 15 | Let . The *-forestwidth* of is the least |
| 16 | such that admits a tree decomposition with root such that |
| 17 | has depth at most , , and for all |
| 18 | . Equivalently, deleting yields a forest decomposition of in which every |
| 19 | root-leaf path has at most nodes. This is a modification of the -treewidth, |
| 20 | for which this forest decomposition is required to be a tree decomposition. |
| 21 | |
| 22 | We formalise the statement as the existence of such a |
| 23 | decomposition. A rooted tree of depth at most is given by its finite set of nodes, |
| 24 | its root , and the parent map, extended by , such that |
| 25 | for every node . In such a tree, a set of nodes induces |
| 26 | a connected subtree if, and only if, at most one node is the root or has its parent |
| 27 | outside . As the root bag is empty, it suffices to require for every vertex that at |
| 28 | most one node has and . |
| 29 | -/ |
| 30 | |
| 31 | namespace Lax461425.Forestwidth |
| 32 | |
| 33 | open HomomorphismPolynomials |
| 34 | |
| 35 | /-- A tree decomposition of the pattern `F` whose tree has depth at most `Δ` and an empty root |
| 36 | bag, and whose bags have at most `k` elements. -/ |
| 37 | structure DepthDecomposition (F : Pattern) (Δ k : ℕ) where |
| 38 | /-- The nodes of the tree. -/ |
| 39 | Node : Type |
| 40 | [fintypeNode : Fintype Node] |
| 41 | /-- The root of the tree. -/ |
| 42 | root : Node |
| 43 | /-- The parent of each node; the root is its own parent. -/ |
| 44 | parent : Node → Node |
| 45 | parent_root : parent root = root |
| 46 | /-- Every node is at distance at most `Δ` from the root. -/ |
| 47 | depth_le : ∀ t, parent^[Δ] t = root |
| 48 | /-- The bag of each node. -/ |
| 49 | bag : Node → Finset (F.A ⊕ F.B) |
| 50 | bag_root : bag root = ∅ |
| 51 | card_bag_le : ∀ t, (bag t).card ≤ k |
| 52 | /-- Every vertex lies in some bag. -/ |
| 53 | exists_mem_bag : ∀ v, ∃ t, v ∈ bag t |
| 54 | /-- Both endpoints of every edge lie in a common bag. -/ |
| 55 | exists_edge_mem_bag : ∀ a b, F.mult a b ≠ 0 → ∃ t, Sum.inl a ∈ bag t ∧ Sum.inr b ∈ bag t |
| 56 | /-- The nodes whose bags contain a vertex `v` induce a connected subtree: at most one of |
| 57 | them has a parent whose bag does not contain `v`. -/ |
| 58 | connected : ∀ v t t', v ∈ bag t → v ∉ bag (parent t) → v ∈ bag t' → v ∉ bag (parent t') → |
| 59 | t = t' |
| 60 | |
| 61 | attribute [instance] DepthDecomposition.fintypeNode |
| 62 | |
| 63 | /-- `fw_Δ(F) ≤ w`: the pattern `F` has a tree decomposition of depth at most `Δ` with empty |
| 64 | root bag and bags of size at most `w + 1`. -/ |
| 65 | def ForestwidthLE (Δ w : ℕ) (F : Pattern) : Prop := |
| 66 | Nonempty (DepthDecomposition F Δ (w + 1)) |
| 67 | |
| 68 | end Lax461425.Forestwidth |
| 69 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments