论文标题
拉姆西图，poset和点集的饱和问题
Saturation problems in the Ramsey theory of graphs, posets and point sets
论文作者
论文摘要
1964年，Erdős，Hajnal和Moon引入了Turán在极端图理论中的经典定理的饱和版本。特别是，他们确定了$ k_r $ - free，$ n $ vertex图中的最小边数，并带有任何进一步的边缘产生$ k_r $的副本。我们在其他设置中考虑了此问题的类似物。我们证明了有关单调子序列和饱和版本的Erdős-Szekeres定理的饱和版本，以及某些Ramsey-Type定理在图形上和posets上的dilworth型定理。 我们还考虑了半饱和问题，其中我们允许家庭具有禁止的配置，但坚持认为，家庭的任何添加都会产生禁止配置的新副本。在这种情况下，我们证明了在凸$ k $ - gons上的Erdős-Szekeres定理的半饱和版本，以及用于序列和POSETS的多个半饱和定理。
In 1964, Erdős, Hajnal and Moon introduced a saturation version of Turán'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ő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ős-Szekeres theorem on convex $k$-gons, as well as multiple semisaturation theorems for sequences and posets.
