BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Joint seminar in COMBINATORIAL GEOMETRY AND OPTIMIZATION:
DTSTART:20121018T160000
DTEND:20121018T170000
DTSTAMP:20260408T055533Z
UID:dc2b2c0f95a7030ef329bfa855b6290cf4700438e5a199e4d4f11b90
CATEGORIES:Conferences - Seminars
DESCRIPTION:Bartosz Walczak\nThe chromatic number of geometric intersectio
 n graphs and related problems\n\nIn 1965\, Burling found a construction of
  triangle-free intersection\ngraphs of three-dimensional boxes with arbitr
 arily large chromatic\nnumber. Recently\, Pawlik et al. proved\, using ess
 entially the same\nconstruction\, that triangle-free intersection graphs o
 f segments in\nthe plane have unbounded chromatic number. This works as we
 ll for\nother types of plane geometric objects\, e.g. L-shapes\, rectangul
 ar\nboundaries\, or even square boundaries. A natural question arises: Is\
 nthe construction optimal?\nWhat is the maximum chromatic number of triang
 le-free segment\nintersection graphs? What is the minimum size of an indep
 endent set in\nthese graphs?\n\nThe graphs obtained from the construction 
 have chromatic number\nTheta(log log n) and linear independence number. On
  the other hand\,\nthe upper bound of O(log n) for the chromatic number an
 d the lower\nbound of Omega(n/log n) for the independence number follow fr
 om\nresults of McGuinness from 2000.\n\nWe establish a relation between ge
 ometric intersection graphs and\nstrategies in some specific games on grap
 hs\, which gives us a new\ninsight into the problems. Consequently\, we sh
 ow the upper bound of\nO(log log n) on the chromatic number of triangle-fr
 ee intersection\ngraphs of axis-aligned rectangular boundaries. We also sh
 ow the linear\nlower bound on the independence number of such graphs satis
 fying an\nadditional technical condition. Hopefully\, this will bring us c
 loser\nto the solution of the original problems for segments.\n\nThis is a
  joint work with Tomasz Krawczyk and Arkadiusz Pawlik.
LOCATION:MA B1 524
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR