BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/111
DTSTAMP:20230914T125910Z
SUMMARY:Coloring Simple Hypergraphs
DESCRIPTION:Speaker: Dhruv Mubayi\nUniversity of Illinois at Chicago\nDept.
of Mathematics\, Statistics\, and Computer Science\n322 Science\n\nAbstra
ct: \nMany problems in number theory\, discrete geometry\, coding theory a
nd combinatorics can be phrased as problems about finding the independence
number of certain hypergraphs. One of the most famous examples is the res
ult of Komlos-Pintz-Szemeredi (1982) on the independence number of 3-unifo
rm hypergraphs which made important progress on the decades old Heilbronn
problem in combinatorial geometry.\n\nAfter a brief introduction to these
topics\, I will show an upper bound on the chromatic number of certain hyp
ergraphs. This implies the above result on independence number as well as
more general theorems due to Ajtai-Komlos-Pintz-Spencer-Szemeredi\, and Du
ke-Lefmann-Rodl. The proof technique is inspired by work of Johansson on g
raph coloring and uses the semi-random or nibble method. This talk will be
accessible to a general mathematical audience.\n
URL:https://www.tcs.tifr.res.in/web/events/111
DTSTART;VALUE=DATE:20100811
LOCATION:AG-69
END:VEVENT
END:VCALENDAR