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

Δ-forestwidth

Lax461425.Forestwidth · concepts/Lax461425/Forestwidth.lean · lax-461425

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

    A tree decomposition of a graph FF is a tree TT with bags β(t)⊆V(F)\beta(t) \subseteq V(F) for t∈V(T)t \in V(T) such that every vertex of FF lies in some bag, both endpoints of every edge lie in a common bag, and, for every vertex vv of FF, the nodes whose bags contain vv induce a connected subtree of TT. Edge multiplicities play no role.

    Let Δ≥1\Delta \geq 1. The Δ\Delta-forestwidth fwΔ(F)\mathrm{fw}_\Delta(F) of FF is the least w≥0w \geq 0 such that FF admits a tree decomposition (T,β)(T, \beta) with root rr such that TT has depth at most Δ\Delta, β(r)=∅\beta(r) = \emptyset, and ∣β(t)∣≤w+1|\beta(t)| \leq w + 1 for all t∈V(T)t \in V(T). Equivalently, deleting rr yields a forest decomposition of FF in which every root-leaf path has at most Δ\Delta nodes. This is a modification of the Δ\Delta-treewidth, for which this forest decomposition is required to be a tree decomposition.

    We formalise the statement fwΔ(F)≤w\mathrm{fw}_\Delta(F) \leq w as the existence of such a decomposition. A rooted tree of depth at most Δ\Delta is given by its finite set of nodes, its root rr, and the parent map, extended by parent(r)=r\mathrm{parent}(r) = r, such that parentΔ(t)=r\mathrm{parent}^\Delta(t) = r for every node tt. In such a tree, a set UU of nodes induces a connected subtree if, and only if, at most one node t∈Ut \in U is the root or has its parent outside UU. As the root bag is empty, it suffices to require for every vertex vv that at most one node tt has v∈β(t)v \in \beta(t) and v∉β(parent(t))v \notin \beta(\mathrm{parent}(t)).

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

    Lean source view on GitHub

    1import Mathlib.Data.Fintype.Sum
    2import Mathlib.Logic.Function.Iterate
    3import Lax461425.HomomorphismPolynomials
    4
    5/-!
    6---
    7title: Δ-forestwidth
    8type: definition
    9---
    10A *tree decomposition* of a graph FF is a tree TT with bags β(t)⊆V(F)\beta(t) \subseteq V(F) for
    11t∈V(T)t \in V(T) such that every vertex of FF lies in some bag, both endpoints of every edge lie
    12in a common bag, and, for every vertex vv of FF, the nodes whose bags contain vv induce a
    13connected subtree of TT. Edge multiplicities play no role.
    14
    15Let Δ≥1\Delta \geq 1. The *Δ\Delta-forestwidth* fwΔ(F)\mathrm{fw}_\Delta(F) of FF is the least
    16w≥0w \geq 0 such that FF admits a tree decomposition (T,β)(T, \beta) with root rr such that TT
    17has depth at most Δ\Delta, β(r)=∅\beta(r) = \emptyset, and ∣β(t)∣≤w+1|\beta(t)| \leq w + 1 for all
    18t∈V(T)t \in V(T). Equivalently, deleting rr yields a forest decomposition of FF in which every
    19root-leaf path has at most Δ\Delta nodes. This is a modification of the Δ\Delta-treewidth,
    20for which this forest decomposition is required to be a tree decomposition.
    21
    22We formalise the statement fwΔ(F)≤w\mathrm{fw}_\Delta(F) \leq w as the existence of such a
    23decomposition. A rooted tree of depth at most Δ\Delta is given by its finite set of nodes,
    24its root rr, and the parent map, extended by parent(r)=r\mathrm{parent}(r) = r, such that
    25parentΔ(t)=r\mathrm{parent}^\Delta(t) = r for every node tt. In such a tree, a set UU of nodes induces
    26a connected subtree if, and only if, at most one node t∈Ut \in U is the root or has its parent
    27outside UU. As the root bag is empty, it suffices to require for every vertex vv that at
    28most one node tt has v∈β(t)v \in \beta(t) and v∉β(parent(t))v \notin \beta(\mathrm{parent}(t)).
    29-/
    30
    31namespace Lax461425.Forestwidth
    32
    33open HomomorphismPolynomials
    34
    35/-- A tree decomposition of the pattern `F` whose tree has depth at most `Δ` and an empty root
    36bag, and whose bags have at most `k` elements. -/
    37structure 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
    61attribute [instance] DepthDecomposition.fintypeNode
    62
    63/-- `fw_Δ(F) ≤ w`: the pattern `F` has a tree decomposition of depth at most `Δ` with empty
    64root bag and bags of size at most `w + 1`. -/
    65def ForestwidthLE (Δ w : ℕ) (F : Pattern) : Prop :=
    66 Nonempty (DepthDecomposition F Δ (w + 1))
    67
    68end Lax461425.Forestwidth
    69

    Discussion

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

    Loading discussion…