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

Homomorphism counts and treewidth of colored graphs

Lax119563.ColoredHomomorphisms · concepts/Lax119563/ColoredHomomorphisms.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

    A homomorphism from a colored graph FF to a colored graph GG is a map h ⁣:V(F)→V(G)h \colon V(F) \to V(G) that sends edges to edges and preserves colors: h(u)h(v)∈E(G)h(u) h(v) \in E(G) for every edge uv∈E(F)uv \in E(F), and χG(h(v))=χF(v)\chi_G(h(v)) = \chi_F(v) for every v∈V(F)v \in V(F). We write hom⁡(F,G)\hom(F, G) for the number of homomorphisms from FF to GG.

    The treewidth tw⁡(F)\operatorname{tw}(F) of a colored graph FF is the treewidth of its underlying graph, i.e., the least ww such that the underlying graph has a tree decomposition whose bags have at most w+1w + 1 vertices.

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

    Lean source view on GitHub

    1import Mathlib.Combinatorics.SimpleGraph.Maps
    2import Mathlib.SetTheory.Cardinal.Finite
    3import Lax228581.Treewidth
    4import Lax119563.ColoredGraphs
    5
    6/-!
    7---
    8title: Homomorphism counts and treewidth of colored graphs
    9type: definition
    10---
    11A *homomorphism* from a colored graph FF to a colored graph GG is a map
    12h ⁣:V(F)→V(G)h \colon V(F) \to V(G) that sends edges to edges and preserves colors:
    13h(u)h(v)∈E(G)h(u) h(v) \in E(G) for every edge uv∈E(F)uv \in E(F), and χG(h(v))=χF(v)\chi_G(h(v)) = \chi_F(v) for every
    14v∈V(F)v \in V(F). We write hom⁡(F,G)\hom(F, G) for the number of homomorphisms from FF to GG.
    15
    16The *treewidth* tw⁡(F)\operatorname{tw}(F) of a colored graph FF is the treewidth of its
    17underlying graph, i.e., the least ww such that the underlying graph has a tree decomposition
    18whose bags have at most w+1w + 1 vertices.
    19
    20# Implementation notes
    21
    22Tree decompositions and treewidth are those of `Lax228581.Treewidth`.
    23-/
    24
    25open Lax119563.ColoredGraphs Lax228581.Treewidth
    26
    27namespace Lax119563.ColoredHomomorphisms
    28
    29/-- hom⁡(F,G)\hom(F, G): the number of color-preserving homomorphisms from `F` to `G`. -/
    30noncomputable def hom (F G : ColoredGraph) : ℕ :=
    31 Nat.card {h : F.graph →g G.graph // ∀ v, G.color (h v) = F.color v}
    32
    33/-- tw⁡(F)≤w\operatorname{tw}(F) \le w: the underlying graph of `F` has a tree decomposition whose
    34bags have at most `w + 1` vertices. -/
    35def TreewidthAtMost (F : ColoredGraph) (w : ℕ) : Prop :=
    36 HasTreewidthAtMost F.graph w
    37
    38end Lax119563.ColoredHomomorphisms
    39

    Implementation notes

    Tree decompositions and treewidth are those of Lax228581.TreewidthLax228581.Treewidth.

    Discussion

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

    Loading discussion…