Homomorphism counts and treewidth of colored graphs
Lax119563.ColoredHomomorphisms · concepts/Lax119563/ColoredHomomorphisms.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
A homomorphism from a colored graph to a colored graph is a map that sends edges to edges and preserves colors: for every edge , and for every . We write for the number of homomorphisms from to .
The treewidth of a colored graph is the treewidth of its underlying graph, i.e., the least such that the underlying graph has a tree decomposition whose bags have at most vertices.
Concept map
Lean source view on GitHub
| 1 | import Mathlib.Combinatorics.SimpleGraph.Maps |
| 2 | import Mathlib.SetTheory.Cardinal.Finite |
| 3 | import Lax228581.Treewidth |
| 4 | import Lax119563.ColoredGraphs |
| 5 | |
| 6 | /-! |
| 7 | --- |
| 8 | title: Homomorphism counts and treewidth of colored graphs |
| 9 | type: definition |
| 10 | --- |
| 11 | A *homomorphism* from a colored graph to a colored graph is a map |
| 12 | that sends edges to edges and preserves colors: |
| 13 | for every edge , and for every |
| 14 | . We write for the number of homomorphisms from to . |
| 15 | |
| 16 | The *treewidth* of a colored graph is the treewidth of its |
| 17 | underlying graph, i.e., the least such that the underlying graph has a tree decomposition |
| 18 | whose bags have at most vertices. |
| 19 | |
| 20 | # Implementation notes |
| 21 | |
| 22 | Tree decompositions and treewidth are those of `Lax228581.Treewidth`. |
| 23 | -/ |
| 24 | |
| 25 | open Lax119563.ColoredGraphs Lax228581.Treewidth |
| 26 | |
| 27 | namespace Lax119563.ColoredHomomorphisms |
| 28 | |
| 29 | /-- : the number of color-preserving homomorphisms from `F` to `G`. -/ |
| 30 | noncomputable def hom (F G : ColoredGraph) : ℕ := |
| 31 | Nat.card {h : F.graph →g G.graph // ∀ v, G.color (h v) = F.color v} |
| 32 | |
| 33 | /-- : the underlying graph of `F` has a tree decomposition whose |
| 34 | bags have at most `w + 1` vertices. -/ |
| 35 | def TreewidthAtMost (F : ColoredGraph) (w : ℕ) : Prop := |
| 36 | HasTreewidthAtMost F.graph w |
| 37 | |
| 38 | end Lax119563.ColoredHomomorphisms |
| 39 |
Implementation notes
Tree decompositions and treewidth are those of .
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments