Lassos: Pushing Tree Decompositions Forward Along Homomorphisms
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918051509698560 |
|---|---|
| author | Bumpus, Benjamin Merlin Fairbanks, James Turner, Will J. |
| author_facet | Bumpus, Benjamin Merlin Fairbanks, James Turner, Will J. |
| contents | It is folklore that tree-width is monotone under taking subgraphs (i.e. injective graph homomorphisms) and contractions (certain kinds of surjective graph homomorphisms). However, although tree-width is obviously not monotone under any surjective graph homomorphism, it is not clear whether contractions are canonically the only class of surjections with respect to which it is monotone. Under the requirement that the decomposition shape must be preserved, we prove that this is indeed the case.
Our results provide a framework for answering questions of this sort for many other kinds of combinatorial data structures (such as directed multigraphs, hypergraphs, Petri nets, circular port graphs, half-edge graphs, databases, simplicial sets etc.) for which natural analogues of tree decompositions can be defined. Furthermore and of independent interest, we prove these results by introducing the notion of a lasso, a generalization of contractions of graphs to arbitrary categories with pushouts of monomorphisms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_15184 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Lassos: Pushing Tree Decompositions Forward Along Homomorphisms Bumpus, Benjamin Merlin Fairbanks, James Turner, Will J. Combinatorics Discrete Mathematics Category Theory 05C83, 18B50 G.2.2 It is folklore that tree-width is monotone under taking subgraphs (i.e. injective graph homomorphisms) and contractions (certain kinds of surjective graph homomorphisms). However, although tree-width is obviously not monotone under any surjective graph homomorphism, it is not clear whether contractions are canonically the only class of surjections with respect to which it is monotone. Under the requirement that the decomposition shape must be preserved, we prove that this is indeed the case. Our results provide a framework for answering questions of this sort for many other kinds of combinatorial data structures (such as directed multigraphs, hypergraphs, Petri nets, circular port graphs, half-edge graphs, databases, simplicial sets etc.) for which natural analogues of tree decompositions can be defined. Furthermore and of independent interest, we prove these results by introducing the notion of a lasso, a generalization of contractions of graphs to arbitrary categories with pushouts of monomorphisms. |
| title | Lassos: Pushing Tree Decompositions Forward Along Homomorphisms |
| topic | Combinatorics Discrete Mathematics Category Theory 05C83, 18B50 G.2.2 |
| url | https://arxiv.org/abs/2408.15184 |