






















For positive integers $N$ and $r \geq 2$, an $r$-monotone coloring of $\binom{\{1,\dots,N\}}{r}$ is a 2-coloring by $-1$ and $+1$ that is monotone on the lexicographically ordered sequence of $r$-tuples of every $(r+1)$-tuple from~$\binom{\{1,\dots,N\}}{r+1}$. Let ${\overline{R}_{mon}}(n;r)$ be the minimum $N$ such that every $r$-monotone coloring of $\binom{\{1,\dots,N\}}{r}$ contains a monochromatic copy of $\binom{\{1,\dots,n\}}{r}$. For every $r \geq 3$, it is known that ${\overline{R}_{mon}}(n;r) \leq tow_{r-1}(O(n))$, where $tow_h(x)$ is the tower function of height $h-1$ defined as $tow_1(x)=x$ and $tow_h(x) = 2^{tow_{h-1}(x)}$ for $h \geq 2$. The Erdős--Szekeres Lemma and the Erdős--Szekeres Theorem imply ${\overline{R}_{mon}}(n;2)=(n-1)^2+1$ and ${\overline{R}_{mon}}(n;3)=\binom{2n-4}{n-2}+1$, respectively. It follows from a result of Eliáš and Matoušek that ${\overline{R}_{mon}}(n;4)\geq tow_3(Ω(n))$. We show that ${\overline{R}_{mon}}(n;r)\geq tow_{r-1}(Ω(n))$ for every $r \geq 3$. This, in particular, solves an open problem posed by Eliáš and Matoušek and by Moshkovitz and Shapira. Using two geometric interpretations of monotone colorings, we show connections between estimating ${\overline{R}_{mon}}(n;r)$ and two Ramsey-type problems that have been recently considered by several researchers. Namely, we show connections with higher-order Erdős--Szekeres theorems and with Ramsey-type problems for order-type homogeneous sequences of points. We also prove that the number of $r$-monotone colorings of $\binom{\{1,\dots,N\}}{r}$ is $2^{N^{r-1}/r^{Θ(r)}}$ for $N \geq r \geq 3$, which generalizes the well-known fact that the number of simple arrangements of~$N$ pseudolines is $2^{Θ(N^2)}$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。