Ramsey numbers and monotone colorings
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10384927" target="_blank" >RIV/00216208:11320/19:10384927 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=cCZIMzbrJ8" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=cCZIMzbrJ8</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.jcta.2018.11.013" target="_blank" >10.1016/j.jcta.2018.11.013</a>
Alternative languages
Result language
angličtina
Original language name
Ramsey numbers and monotone colorings
Original language description
For positive integers N and r >= 2, an r-monotone coloring of ({1,...,N} choose 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 ({1,...,N} choose r+1). Let R(n;r) be the minimum N such that every r-monotone coloring of ({1,...,N} choose r) contains a monochromatic copy of ({1,...,n} choose r). For every r >= 3, it is known that R(n;r) <= 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 >= 2. The Erdős-Szekeres Lemma and the Erdős-Szekeres Theorem imply R(n;2) = (n-1)^2+1 and R(n;3) = (2n-4 choose n-2) + 1, respectively. It follows from a result of Eliáš and Matoušek that R(n;4) >= tow_3(Omega(n)). We show that R(n;r) >= tow_(r-1)(Omega(n)) for every r >= 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 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 ({1,...,N} choose r) is 2^(N^(r-1)/r^(Theta(r))) for N >= r >= 3, which generalizes the well-known fact that the number of simple arrangements of N pseudolines is 2^(Theta(N^2)).
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
<a href="/en/project/GJ18-13685Y" target="_blank" >GJ18-13685Y: Model thoery and extremal combinatorics</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Journal of Combinatorial Theory - Series A
ISSN
0097-3165
e-ISSN
—
Volume of the periodical
2019
Issue of the periodical within the volume
163
Country of publishing house
US - UNITED STATES
Number of pages
25
Pages from-to
34-58
UT code for WoS article
000456358100002
EID of the result in the Scopus database
2-s2.0-85056829998