Saturation of Ordered Graphs

The well known extremal problem is to find the size of a
largest maximal object with some given property. The saturation
problem is to find the size of a smallest maximal object with some
given property, e.g., avoiding a given substructure. This notion was
introduced by Kászonyi and Tuza for graphs [86], with the earliest
result by Erdős Hajnal and Moon [64].
Recently, the saturation problem of 0-1 matrices gained a lot of
attention. This problem can be regarded as a saturation problem of
ordered bipartite graphs. Motivated by this, we initiate the study of
the saturation problem of ordered and cyclically ordered graphs.
Dichotomy holds in all three settings, i.e., the saturation function
is either bounded or linear, just like for graphs. While
characterizing the bounded cases is quite easy for graphs, in all the
ordered settings this is an open problem.
We present infinite many examples exhibiting both possible behaviours.
In particular, in the ordered case we define a natural subclass of
ordered matchings, the class of linked matchings, and we start their
systematic study, concentrating on linked matchings with at most three
links and prove that many of them have bounded saturation function.
In all three settings we consider the semisaturation problem, where
dichotomy holds as well and we can even fully characterize relatively
easily the graphs that have bounded semisaturation function.
This is a joint work with Vladimir Bošković.