论文标题
持续的拥塞荆棘
Constant Congestion Brambles
论文作者
论文摘要
一个无向图$ g $中的武器是$ g $的连接子图的家族，使得每两个子图$ h_1 $ and $ h_1 $和$ h_2 $ bramble bramble $ v（h_1）\ cap v（h_2）\ neq \ neq \ neq \ neq \ neq \ emptyset $或一个$ g $ g $ in $ v（$ v（h_1）$ v（h_1）$ v（h_1）$ v（h_1）$ v（h_1）和v（h_1）和v（h_1）和v（h_1）和v（h_1）。烤板的顺序是与荆棘的所有元素相交的顶点集的最小尺寸。 棕褐色是对象至树宽的对象：Seymour和Thomas所示，无向图$ g $中的Bramble的最大顺序等于一个，再加上$ G $的树宽。但是，如Grohe和Marx所示，高阶的荆棘可能必须是指数尺寸的：在恒定的$ n $ n $ -vertex中，订单$ω（n^{1/2+δ}）$ subl bramble of $ω（n^{2Δ}）$ supersization used used sized sized sized sized sized use（n^{2Δ}）$ for note coption $ niven $ $ $ ex $Δ;另一方面，Grohe，Marx和Chekuri和Chuzhoy的结果的结合表明，树宽$ K $的图形订购了$ \ widetildeme（k^{1/2}）$和size $ \ \ \ \ wideTilde {\ wideTilde {\ Mathcal {\ Mathcal {o}} $ and $ \ widetilde {\ Mathcal {o}} $ hide polylogarithmic因子和除数。） 在此注释中，我们首先通过证明每个图$ g $至少$ k $包含订单$ \widetildeΩ（k^{1/2}）$和交通拥堵的$ 2 $，即$ g $的每个顶点都包含$ g $的每一个大多数元素（因此，bramble ins size ins size ins Size ins Size ins Size ins Size ins Size），我们首先首先提高了第二个限制。其次，我们为Grohe和Marx的下限提供一个紧密的上限：（0，\ frac {1} {2}] $，每个$δ\ in（\ frac {1} {2}] $，每个图$ g $ treewidth $ k $至少包含订单$ \ \ \wideTildeΩ（k^{1/2+δ} $ um \ wideTildeph $ 2^{\ widetilde {\ Mathcal {o}}（k^{2Δ}）} $。
A bramble in an undirected graph $G$ is a family of connected subgraphs of $G$ such that for every two subgraphs $H_1$ and $H_2$ in the bramble either $V(H_1) \cap V(H_2) \neq \emptyset$ or there is an edge of $G$ with one endpoint in $V(H_1)$ and the second endpoint in $V(H_2)$. The order of the bramble is the minimum size of a vertex set that intersects all elements of a bramble. Brambles are objects dual to treewidth: As shown by Seymour and Thomas, the maximum order of a bramble in an undirected graph $G$ equals one plus the treewidth of $G$. However, as shown by Grohe and Marx, brambles of high order may necessarily be of exponential size: In a constant-degree $n$-vertex expander a bramble of order $Ω(n^{1/2+δ})$ requires size exponential in $Ω(n^{2δ})$ for any fixed $δ\in (0,\frac{1}{2}]$. On the other hand, the combination of results of Grohe and Marx and Chekuri and Chuzhoy shows that a graph of treewidth $k$ admits a bramble of order $\widetildeΩ(k^{1/2})$ and size $\widetilde{\mathcal{O}}(k^{3/2})$. ($\widetildeΩ$ and $\widetilde{\mathcal{O}}$ hide polylogarithmic factors and divisors, respectively.) In this note, we first sharpen the second bound by proving that every graph $G$ of treewidth at least $k$ contains a bramble of order $\widetildeΩ(k^{1/2})$ and congestion $2$, i.e., every vertex of $G$ is contained in at most two elements of the bramble (thus the bramble is of size linear in its order). Second, we provide a tight upper bound for the lower bound of Grohe and Marx: For every $δ\in (0,\frac{1}{2}]$, every graph $G$ of treewidth at least $k$ contains a bramble of order $\widetildeΩ(k^{1/2+δ})$ and size $2^{\widetilde{\mathcal{O}}(k^{2δ})}$.
