BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: Let P be a set of 2n points in convex position\, such that n p
 oints are colored red and n points are colored blue. A non-crossing alterna
 ting path on P of length l is a sequence p_1\, ...\, p_l of l points from P
  so that (i) all points are pairwise distinct\; (ii) any two consecutive po
 ints p_i\, p_{i+1} have different colors\; and (iii) any two segments p_i p
 _{i+1} and p_j p_{j+1} have disjoint relative interiors\,  for i /= j.    W
 e show that there is an absolute constant eps &gt\; 0\, independent of n an
 d of the coloring\, such that P always admits a non-crossing alternating pa
 th of length at least (1 + eps)n. The result is obtained through a slightly
  stronger statement: there always exists a non-crossing bichromatic separat
 ed matching on at least (1 + eps)n points of P. This is a properly colored 
 matching whose segments are pairwise disjoint and intersected by a common l
 ine. For both versions\, this is the first improvement of the easily obtain
 ed lower bound of n by an additive term linear in n. The best known publish
 ed upper bounds are asymptotically of order 4n/3 + o(n).    Based on joint 
 work with Pavel Valtr.    
DTSTAMP:20220624T160800
DTSTART:20220627T141500
CLASS:PUBLIC
LOCATION:Freie Universität Berlin \n Institut für Informatik \n Takustr. 9 
 \n 14195 Berlin \n Room 005 (Ground Floor)
SEQUENCE:0
SUMMARY:Wolfgang Mulzer (Freie Universität Berlin): Long Alternating Paths 
 Exist
UID:126720453@/www.mi.fu-berlin.de
URL:https://www.mi.fu-berlin.de/en/facetsofcomplexity/monday/20220627-L-Wol
 fgang.html
END:VEVENT
END:VCALENDAR