论文标题
带有无界堆栈数的三维图形产品
Three-dimensional graph products with unbounded stack-number
论文作者
论文摘要
我们证明，三个$ n $ vertex路径的强产物的堆叠数为$θ（n^{1/3}）$。最佳以前已知的上限是$ O（n）$。没有众所周知的非平凡的下限。这是图形家族的第一个明确示例，具有最大程度和无限的堆栈数。 在我们的下限证明中使用的主要工具是Gromov的拓扑重叠定理。实际上，就所谓的笛卡尔产品三角剖分而言，我们证明了更强的结果。我们得出的结论是，任何足够大的连接图的三维笛卡尔产物的三角剖分都具有较大的堆栈数量。 上限是基于Hadamard矩阵衍生的置换家族的更通用结构的特殊情况。 三个路径的强产物也是有界排队数和无界堆栈数字的有界度图的第一个示例。从我们的结果来看，一个自然的问题是确定最小的$Δ_0$，以便存在一个图形家族，该图具有无界的堆栈数，有限的排队数量和最高度$δ_0$。我们证明$Δ_0\ in \ {6,7 \} $。
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\}$.
