Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2312.07105 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913977387188224 |
|---|---|
| author | Huang, Wanying Hume, David Kelly, Samuel J. Lam, Ryan |
| author_facet | Huang, Wanying Hume, David Kelly, Samuel J. Lam, Ryan |
| contents | We define a range of new coarse geometric invariants based on various graph-theoretic measures of complexity for finite graphs, including: treewidth, pathwidth, cutwidth and bandwidth. We prove that, for bounded degree graphs, these invariants can be used to define functions which satisfy a strong monotonicity property, namely they are monotonically non-decreasing with respect to a large-scale geometric generalisation of graph inclusion, and as such have potential applications in coarse geometry and geometric group theory. On the graph-theoretic side, we prove asymptotically optimal bounds on most of the above widths for the family of all finite subgraphs of any bounded degree graph whose separation profile is known to be of the form $r^a\log(r)^b$ for some $a>0$. This large class includes Diestel-Leader graphs, all Cayley graphs of non-virtually cyclic polycyclic groups, uniform lattices in almost all connected unimodular Lie groups, and many hyperbolic groups. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_07105 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A coarse geometric approach to graph layout problems Huang, Wanying Hume, David Kelly, Samuel J. Lam, Ryan Metric Geometry Combinatorics 20F65, 51F30, 05C25, 05C78 We define a range of new coarse geometric invariants based on various graph-theoretic measures of complexity for finite graphs, including: treewidth, pathwidth, cutwidth and bandwidth. We prove that, for bounded degree graphs, these invariants can be used to define functions which satisfy a strong monotonicity property, namely they are monotonically non-decreasing with respect to a large-scale geometric generalisation of graph inclusion, and as such have potential applications in coarse geometry and geometric group theory. On the graph-theoretic side, we prove asymptotically optimal bounds on most of the above widths for the family of all finite subgraphs of any bounded degree graph whose separation profile is known to be of the form $r^a\log(r)^b$ for some $a>0$. This large class includes Diestel-Leader graphs, all Cayley graphs of non-virtually cyclic polycyclic groups, uniform lattices in almost all connected unimodular Lie groups, and many hyperbolic groups. |
| title | A coarse geometric approach to graph layout problems |
| topic | Metric Geometry Combinatorics 20F65, 51F30, 05C25, 05C78 |
| url | https://arxiv.org/abs/2312.07105 |