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

Damásdi, Gábor and Keszegh, Balázs and Malec, D. and Tompkins, Casey and Wang, Z. Y. (2021) Saturation problems in the Ramsey theory of graphs, posets and point sets. EUROPEAN JOURNAL OF COMBINATORICS, 95. ISSN 0195-6698

Preview

Text 2004.06097.pdf Download (635kB) | Preview

Abstract

In 1964, Erdos, Hajnal and Moon introduced a saturation version of Tur & aacute;n's classical theorem in extremal graph theory. In particular, they determined the minimum number of edges in a Kr-free, n-vertex graph with the property that the addition of any further edge yields a copy of Kr. We consider analogues of this problem in other settings. We prove a saturation version of the Erdos-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 Erdos-Szekeres theorem on convex k-gons, as well as multiple semisaturation theorems for sequences and posets. (c) 2021 Elsevier Ltd. All rights reserved.

Actions (login required)

Edit Item