Zoom link:

https://princeton.zoom.us/j/92250659492

In 2014, Sylvain Guillemot and Daniel Marx proved that detecting a fixed permutation pattern S in a permutation P can be done in linear time f(S).|P|. When S is 12345, this amounts to detect a 5-terms increasing subsequence in P, but S can be much more tricky and many researchers believed before their proof that no f(S)n^c algorithm could solve it. They invented for this a completely new (decomposition method / dynamic programming) technique, based on the brave old treewidth-like trick: if P does not contain S, then it admits a decomposition on which we can indeed efficiently prove that P does not contain S. The engine of their method is the Marcus-Tardos theorem: if an nxn 01-matrix has c.n entries then there is an f(c) partition of its columns C1,...,Cf(c) and rows R1,...,Rf(c), each Ci and Rj being consecutive subsets, such that every submatrix CixRj contains a 1 entry (of course f goes to infinity). Since their approach was reminiscent of tree-width (also, Marcus-Tardos is strikingly close to "large linear degree implies large clique minor"), they asked for an extension of their method to other structures. We exactly follow their tracks and propose the notion of twin-width of a graph (and more generally of a matrix). Here are some quick remarks: 1) Twin-width is easy to define, it corresponds to the maximum degree of errors one can make, starting from G and iteratively contracting pairs of twins or near-twins (the sequence is called a twin-decomposition). For instance cographs are the graphs with twin width 0. More generally, bounded rank-width implies bounded twin-width. 2) A graph G has bounded twin-width k if and only if one can enumerate its vertices in such a way that its adjacency matrix A_G does not have a large partition of its columns C1,...,Cg(k) and rows R1,...,Rg(k) (all parts being consecutive) such that every submatrix CixRj is neither vertical (same column vector repeated) nor horizontal (same row vector repeated). 3) Using 2), one can prove for instance that strict minor closed classes of graphs, posets with bounded size antichains, strict classes of dimension two posets, strict classes of permutation graphs, all have bounded twin-width. Here "class" means closed under induced subgraphs. 4) Bounded twin-width is very resilient to operations, like of course taking complement, but also taking squares. For instance the square of a planar graph (add edges when distance is at most 2) has bounded twin-width. Much more generally, any first-order interpretation of a bounded twin-width graph has bounded twin width. It follows that for instance map graphs, or interval graphs with bounded number of lengths have bounded twin-width. 5) FO model checking is linear when we have the twin-decomposition. For instance deciding if G has diameter at most k, or domination number at most k, or an induced path of length k can be done in f(d,k)n time where d is the twin width of G (again if we have a decomposition). 6) The class of graphs with twin-width at most d is small, i.e. there are c^n.n! such labeled graphs on the vertex set 1,...,n. We conjecture that twin-width is exactly the right invariant to describe small classes, that is: a class is small iff its twin-width is bounded. 7) In view of 6), one can immediately derives that cubic graphs have unbounded twin-width. However, there are some (Bilu-Linial) cubic expanders with twin width at most 6, hence even for cubic graphs, the separation bounded/unbounded twin-width is unclear. In particular twin-width is an independent notion of nowhere dense. One can define the twin width of a matrix, of a finite subset of integers, of a finitely generated group, etc, etc... The goal of this talk is to share this very nice playground. Co-authors: Edouard Bonnet, Eunjung Kim, Rémi Watrigant