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ć.