[Colloquium] REMINDER: Talk by Dhruv Mubayi Today
Katie Casey
caseyk at cs.uchicago.edu
Mon Feb 23 09:34:27 CST 2009
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF CHICAGO
Date: Monday, February 23, 2009
Time: 3:45 p.m.
Place: RY 251
----------------------------------------------------------
Speaker: Dhruv Mubayi
From: University of Illinois at Chicago
Website: http://www.math.uic.edu/~mubayi/
Title: Coloring Simpler Hypergraphs
Abstract: Improvements of the obvious lower bounds on the
independence number
of (hyper)graphs have had impact on problems in discrete geometry,
coding theory, number theory and combinatorics. One of the most
famous examples is the result of Komlos-Pintz-Szemeredi (1982) on
the independence number of 3-uniform hypergraphs which made
important progress on the decades old Heilbronn problem.
We give a sharp upper bound on the chromatic number of simple
k-uniform hypergraphs that implies the above result as well as more
general theorems due to Ajtai-Komlos-Pintz-Spencer-Szemeredi, and
Duke-Lefmann-Rodl. Our proof technique is inspired by work of
Johansson on graph coloring and uses the semi-random or nibble
method. This is joint work with Alan Frieze.
Refreshments will be served prior to the talk in RY 255.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20090223/2a2deca4/attachment.htm
More information about the Colloquium
mailing list