BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: For positive integers N and r >\;= 2\, an r-monotone colorin
g of r-tuples from [N] 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 [
N]. Let ORS(n\;r) be the minimum N such that every r-monotone coloring of r
tuples from [N] contains n elements with all r-tuples of the same color. F
or every r >\;= 3\, it is known that ORS(n\;r) is bounded from above by a
tower function of height r-2 with O(n) on the top. The Erdős--Szekeres Lem
ma and the Erdős--Szekeres Theorem imply ORS(n\;2)=(n-1) ^2 +1 and ORS(n\;3
) = ((2n-4) choose (n-2))+1\, respectively. It follows from a result of Eli
áš and Matoušek that ORS (n\;4) grows as o tower of height 2. We show that
ORS(n\;r) grows at least as a tower of height r-2 for every r >\;= 3. Thi
s\, 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 ORS(n\;r) and two Ramsey
-type problems that have been recently considered by several researchers. W
e also prove asymptotically tight estimates on the number of r-monotone col
orings.
DTSTAMP:20181105T173600
DTSTART:20180716T160000
CLASS:PUBLIC
LOCATION:Technische Universität Berlin Institut für Mathematik Straße des 1
7. Juni 136 10623 Berlin Room MA 041 (ground floor)
SEQUENCE:0
SUMMARY:Martin Balko (Charles University of Prague): Ramsey numbers and mon
otone colorings
UID:89793311@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20180716-C-Balko.html
END:VEVENT
END:VCALENDAR