***********************************
* Princeton Discrete Math Seminar *
***********************************
Speaker: StÃ©phan ThomassÃ© (Lyon)
Thursday 18th March, 3:00 via Zoom.
Title: The factorial gap
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.
----------------------------------
Next week: Pawel Rzazewski
Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)