Twin-width II: small classes

• Published in: arXiv.org 2020-06
• Main Authors: Bonnet, Édouard, Geniet, Colin, Eun Jung Kim, Thomassé, Stéphan, Watrigant, Rémi
• Format: Article
• Language: English
• Subjects: Apexes; Expanders; Graph theory; Graphs; Group theory; Permutations; Queues; Subdivisions
• ISSN: 2331-8422

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.