Saturation of Ordered Graphs

Description of video

Date: 3/31/22
Speaker :Keszegh Balázs


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