Saturation problems in the Ramsey theory of graphs, posets and point sets

Gábor Damásdi, Balázs Keszegh, David Malec, Casey Tompkins, Zhiyu Wang, Oscar Zamora

Published 2020-04-13Version 1

In 1964, Erd\H{o}s, Hajnal and Moon introduced a saturation version of Tur\'an's classical theorem in extremal graph theory. In particular, they determined the minimum number of edges in a $K_r$-free, $n$-vertex graph with the property that the addition of any further edge yields a copy of $K_r$. We consider analogues of this problem in other settings. We prove a saturation version of the Erd\H{o}s-Szekeres theorem about monotone subsequences and saturation versions of some Ramsey-type theorems on graphs and Dilworth-type theorems on posets. We also consider semisaturation problems, wherein we allow the family to have the forbidden configuration, but insist that any addition to the family yields a new copy of the forbidden configuration. In this setting, we prove a semisaturation version of the Erd\H{o}s-Szekeres theorem on convex $k$-gons, as well as multiple semisaturation theorems for sequences and posets.