BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: For positive integers N and r &gt\;= 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 &gt\;= 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 &gt\;= 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.mi.fu-berlin.de
URL:https://www.mi.fu-berlin.de/en/facetsofcomplexity/monday/20180716-C-Bal
 ko.html
END:VEVENT
END:VCALENDAR