论文标题
双宽度II：小课
Twin-width II: small classes
论文作者
论文摘要
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$.我们表明，如果图形允许$ d $ - 征收序列，那么它还具有$ f（d）$ - 收缩为$ f（d）$ f $的线性树木。首先，这允许证明每个有界的双宽度类都很小，即，对于某些常数$ c $，最多具有$ n！c^n $图形。这统一并扩展了有界的树宽图[Beineke and Pippert，JCT '69]，适当的置换子类图[Marcus和Tardos，JCTA '04]和适当的无次小型类[Norine等人，JCTB '06]。第二个结果是$ O（\ log n）$ - 用于有限的双宽度图的邻接标签方案，确认了隐式图形构件的几种情况。然后，我们探讨了“小型猜想”，相反，每个小遗传阶级都构成了双宽度。受对数深度的分类网络的启发，我们表明$ \ log_ {θ（\ log \ log \ log d \ log d）} n $ -subdivisions的$ k_n $（$ d $是常数时的小类）在最多$ d $。我们获得了一个相当尖锐的交谈，并具有令人惊讶的直接证明：$ \ log_ {d+1} n $ -subdivision $ k_n $的ubdivision具有至少$ d $的双宽度。其次，具有有界堆栈或队列编号（也小类）的图形图具有界限。第三，我们表明，通过迭代的随机2升级获得的立方扩展器也从$ k_4 $〜[bilu and linial，combinatorica '06]也界定了双宽度。我们建议在小型猜想和群体理论之间有一个有希望的联系。最后，我们定义了稀疏双宽度的强大概念，并讨论它与其他稀疏类别的比较。
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_{Θ(\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.
