Twin-width II: small classes
Twin-width II: small classes
复制标题
双宽II：小班授课
DOI：
10.1137/1.9781611976465.118
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Rémi Watrigant
中科院分区：
文献类型：
--
作者：
Édouard Bonnet;Colin Geniet;Eun Jung Kim;Stéphan Thomassé;Rémi Watrigant
图G的孪生宽度是使G有d-收缩序列的最小整数d，即G有d-收缩序列|V（G）|-1 $迭代顶点标识，其中入射到单个顶点的红边的总最大数量至多为$d$，其中红边出现在两组标识的顶点之间，如果它们在$G$中不是齐次的。本文证明了如果一个图有d-压缩序列，那么对于某个函数f，它也有f（d）-压缩的线性度树。首先，这允许表明，每一个有界双宽度类是小的，即，最多有$n！c^n$图标记为$[n]$，对于某个常数$c$。这统一并扩展了有界树宽图[Beineke和Pippert，JCT '69]，置换图的适当子类[Marcus和Tardos，JCTA '04]和适当的无小类[Norine等人，JCTB '06]。第二个结果是有界双宽度图的O（\log n）$-邻接标号方案，证实了隐图猜想的几种情况。然后，我们探讨“小猜想”，相反，每一个小的遗传类有界双宽度。受对数深度排序网络的启发，我们证明了$K_n$的$\log_{\Theta（\log \log d）}n$-细分（当$d$为常数时是一个小类）的twin宽度至多为$d$。我们得到了一个相当尖锐的匡威与一个令人惊讶的直接证明：$K_n$的$\log_{d+1}n$-细分有孪生宽度至少$d$。第二，具有有界堆栈或队列数的图（也是小类）具有有界孪生宽度。第三，我们证明了从$K_4$~[Bilu and Linial，Combinatorica '06]迭代随机2-提升得到的三次展开式也具有有界的孪生宽度。我们建议一个有前途的小猜想和群论之间的联系。最后，我们定义了一个强大的概念稀疏双宽度，并讨论它如何与其他稀疏类比较。
The twin-width of a graph $G$ is the minimum integer $d$ such that $G$ has a $d$-contraction sequence, that is, a sequence of $|V(G)|-1$ iterated vertex identifications for which the overall maximum number of red edges incident to a single vertex is at most $d$, where a red edge appears between two sets of identified vertices if they are not homogeneous in $G$. We show that if a graph admits a $d$-contraction sequence, then it also has a linear-arity tree of $f(d)$-contractions, for some function $f$. First this permits to show that every bounded twin-width class is small, i.e., has at most $n!c^n$ graphs labeled by $[n]$, for some constant $c$. This unifies and extends the same result for bounded treewidth graphs [Beineke and Pippert, JCT '69], proper subclasses of permutations graphs [Marcus and Tardos, JCTA '04], and proper minor-free classes [Norine et al., JCTB '06]. The second consequence is an $O(\log n)$-adjacency labeling scheme for bounded twin-width graphs, confirming several cases of the implicit graph conjecture. We then explore the "small conjecture" that, conversely, every small hereditary class has bounded twin-width. Inspired by sorting networks of logarithmic depth, we show that $\log_{\Theta(\log \log d)}n$-subdivisions of $K_n$ (a small class when $d$ is constant) have twin-width at most $d$. We obtain a rather sharp converse with a surprisingly direct proof: the $\log_{d+1}n$-subdivision of $K_n$ has twin-width at least $d$. Secondly graphs with bounded stack or queue number (also small classes) have bounded twin-width. Thirdly we show that cubic expanders obtained by iterated random 2-lifts from $K_4$~[Bilu and Linial, Combinatorica '06] have bounded twin-width, too. We suggest a promising connection between the small conjecture and group theory. Finally we define a robust notion of sparse twin-width and discuss how it compares with other sparse classes.
DOI：
10.2168/lmcs-6(2:2)2010
发表时间：
2010
期刊：
Log. Methods Comput. Sci.
影响因子：
--
作者：
A. Blumensath;B. Courcelle
通讯作者：
B. Courcelle