Three-dimensional graph products with unbounded stack-number
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913320534016000 |
|---|---|
| author | Eppstein, David Hickingbotham, Robert Merker, Laura Norin, Sergey Seweryn, Michał T. Wood, David R. |
| author_facet | Eppstein, David Hickingbotham, Robert Merker, Laura Norin, Sergey Seweryn, Michał T. Wood, David R. |
| contents | We prove that the stack-number of the strong product of three $n$-vertex paths is $Θ(n^{1/3})$. The best previously known upper bound was $O(n)$. No non-trivial lower bound was known. This is the first explicit example of a graph family with bounded maximum degree and unbounded stack-number.
The main tool used in our proof of the lower bound is the topological overlap theorem of Gromov. We actually prove a stronger result in terms of so-called triangulations of Cartesian products. We conclude that triangulations of three-dimensional Cartesian products of any sufficiently large connected graphs have large stack-number.
The upper bound is a special case of a more general construction based on families of permutations derived from Hadamard matrices.
The strong product of three paths is also the first example of a bounded degree graph with bounded queue-number and unbounded stack-number. A natural question that follows from our result is to determine the smallest $Δ_0$ such that there exist a graph family with unbounded stack-number, bounded queue-number and maximum degree $Δ_0$. We show that $Δ_0\in \{6,7\}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2202_05327 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Three-dimensional graph products with unbounded stack-number Eppstein, David Hickingbotham, Robert Merker, Laura Norin, Sergey Seweryn, Michał T. Wood, David R. Combinatorics Discrete Mathematics We prove that the stack-number of the strong product of three $n$-vertex paths is $Θ(n^{1/3})$. The best previously known upper bound was $O(n)$. No non-trivial lower bound was known. This is the first explicit example of a graph family with bounded maximum degree and unbounded stack-number. The main tool used in our proof of the lower bound is the topological overlap theorem of Gromov. We actually prove a stronger result in terms of so-called triangulations of Cartesian products. We conclude that triangulations of three-dimensional Cartesian products of any sufficiently large connected graphs have large stack-number. The upper bound is a special case of a more general construction based on families of permutations derived from Hadamard matrices. The strong product of three paths is also the first example of a bounded degree graph with bounded queue-number and unbounded stack-number. A natural question that follows from our result is to determine the smallest $Δ_0$ such that there exist a graph family with unbounded stack-number, bounded queue-number and maximum degree $Δ_0$. We show that $Δ_0\in \{6,7\}$. |
| title | Three-dimensional graph products with unbounded stack-number |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2202.05327 |