When investigating classes of structures, a particularly prominent line of research is to study transitions from a regime to another. For instance the computational complexity of some problem can be either easy or hard, the number of structures of size n can grow either slow or fast, some structural parameter can be bounded/unbounded, or model theorists can say NIP or not.

When many points of view agree, this is a good sign that some meaningful gap is at work: for instance, in classes of 01 matrices, bounded VC-dimension corresponds to the growth gap between 2^o(n^2) and 2^(n^2) and in the same time matches the integrality gap of the hitting set problem. For the sparse point of view bounded treewidth accounts for the tractability of MSOL.

In this talk, we will be interested in classes of ordered 01 matrices (that is columns and rows are totally ordered, and "classes" are meant to be closed with respect to submatrices). A key-example are (sub)permutation matrices where every row and column contains at most a "1". The celebrated Stanley-Wilf conjecture / Marcus-Tardos theorem asserts that the growth function (number of nxn matrices in the class) of a class C of subpermutation matrices is either at least n! or at most c^n.

Our main result is that we can drop "subpermutation" in this statement: indeed every class of 01-matrices has either (super)factorial or (sub)exponential growth. This answers (with more work for an exact threshold) in particular a conjecture of Balogh, Bollobas and Morris on ordered graphs. Moreover, this "factorial gap" also appears from other points of view: Theorem. (Bonnet, De Mendez, Giocanti, T.) For a class C of 01 matrices, are equivalent: i) twin-width is bounded / unbounded ii) growth is O(exp n) / >n! iii) FO-model checking is fixed parameter tractable / W-hard iv) C is NIP / not NIP (this was independently proved equivalent to i) by Simon and Torunczyk). Also, we were able to prove that one can approximate twin-width in FPT time for ordered structures, in particular we can efficiently find the twin-decomposition needed for model checking.

So how do we easily tell that a class of matrices C is complex? The answer is surprisingly very simple: this is when one can find for every k some matrix Mk in C which can be divided into kxk blocks each of them having rank at least k. Hence a "grid-theorem" is also at work here. In this talk, I will give an overview of these results, and discuss the (numerous!) questions which are left open.