Ramsey numbers and monotone colorings
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Ramsey numbers and monotone colorings
Popis výsledku v původním jazyce
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)).
Název v anglickém jazyce
Ramsey numbers and monotone colorings
Popis výsledku anglicky
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)).
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10101 - Pure mathematics
Návaznosti výsledku
Projekt
<a href="/cs/project/GJ18-13685Y" target="_blank" >GJ18-13685Y: Teorie modelů a extrémální kombinatorika</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2019
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
Journal of Combinatorial Theory - Series A
ISSN
0097-3165
e-ISSN
—
Svazek periodika
2019
Číslo periodika v rámci svazku
163
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
25
Strana od-do
34-58
Kód UT WoS článku
000456358100002
EID výsledku v databázi Scopus
2-s2.0-85056829998