BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1741
DTSTAMP:20260727T100624Z
SUMMARY:Wegner's conjecture is false
DESCRIPTION:Speaker: Rajiv Raman (IIIT-Delhi)\n\nAbstract: \n\nWegner conje
 ctured in 1965 that every finite family $\\mathcal R$ of axis-parallel rec
 tangles satisfies $\\tau(\\mathcal R)\\le 2\\nu(\\mathcal R)-1$\, where $\
 \tau(\\mathcal R)$ is the minimum number of piercing points and $\\nu(\\ma
 thcal R)$ is the maximum size of a pairwise-disjoint subfamily.  We dispr
 ove the conjecture by an explicit triangle-free family of $64$ rectangles 
 with $\\nu=16$ and $\\tau\\ge 32$.More generally\, for every $\\varepsilon
 >0$\, we construct triangle-free rectangle families for which the standard
  clique-LP relaxation for maximum independent set of rectangles has integr
 ality gap at least $5/2-\\varepsilon$.  The same families satisfy $\\tau(
 \\mathcal R)\\ge (5/2-\\varepsilon)\\nu(\\mathcal R)$.  We also prove tha
 t\, on triangle-free rectangle families\, this LP has gap at most $3$.  O
 ur approach gives an example with axis-parallel segments instead of rectan
 gles with integrality gap tending to $2$. We also give a relatively small 
 $4092$-rectangle triangle-free family with chromatic number $6$ improving 
 the construction of Asplund and Gr\\"unbaum (On a coloring problem\, Mathe
 matica Scandinavica\, 1960) that required more than $10^8$ rectangles.\n 
 \nThe initial proof was found with the help of GPT-5.5 Pro with the author
 s presenting a rough outline and GPT-5.5 Pro did the hard work of working 
 out the details. The proof we present however\, is entirely human generate
 d - where we distill the key ideas in the construction of the machine gene
 rated proof. The resulting counter-example is much simpler and smaller th
 an that generated by GPT-5.5 Pro.\n \nThis is joint work with Deepak Ajwa
 ni\, Rishikesh Gajjala and Saurabh Ray.\n \nBio: Rajiv Raman is an associ
 ate professor at IIIT-Delhi. He obtained his PhD from the University of Io
 wa\, and then spent some time as a postdoc at the Max-Planck Institute in 
 Saarbrucken and at the Centre for Discrete Mathematics and Applications\, 
 University of Warwick. \n \n
URL:https://www.tcs.tifr.res.in/web/events/1741
DTSTART;TZID=Asia/Kolkata:20260804T160000
DTEND;TZID=Asia/Kolkata:20260804T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR