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 >\; 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.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20220627-L-Wolfgang.html
END:VEVENT
END:VCALENDAR