Tata Institute of Fundamental Research
Coloring Simple Hypergraphs
Seminar
Speaker:
Dhruv Mubayi
University of Illinois at Chicago
Dept. of Mathematics, Statistics, and Computer Science
322 Science
Date:
Wednesday, 11 Aug 2010 (all day)
Venue:
AG-69
(Scan to add to calendar)
Abstract:
Many problems in number theory, discrete geometry, coding theory and combinatorics can be phrased as problems about finding the independence number of certain hypergraphs. 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 in combinatorial geometry.
After a brief introduction to these topics, I will show an upper bound on the chromatic number of certain hypergraphs. This implies the above result on independence number as well as more general theorems due to Ajtai-Komlos-Pintz-Spencer-Szemeredi, and Duke-Lefmann-Rodl. The proof technique is inspired by work of Johansson on graph coloring and uses the semi-random or nibble method. This talk will be accessible to a general mathematical audience.
| Speaker: | Dhruv Mubayi University of Illinois at Chicago Dept. of Mathematics, Statistics, and Computer Science 322 Science |
| Date: | Wednesday, 11 Aug 2010 (all day) |
| Venue: | AG-69 |
(Scan to add to calendar)
Abstract:
Many problems in number theory, discrete geometry, coding theory and combinatorics can be phrased as problems about finding the independence number of certain hypergraphs. 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 in combinatorial geometry.
After a brief introduction to these topics, I will show an upper bound on the chromatic number of certain hypergraphs. This implies the above result on independence number as well as more general theorems due to Ajtai-Komlos-Pintz-Spencer-Szemeredi, and Duke-Lefmann-Rodl. The proof technique is inspired by work of Johansson on graph coloring and uses the semi-random or nibble method. This talk will be accessible to a general mathematical audience.
After a brief introduction to these topics, I will show an upper bound on the chromatic number of certain hypergraphs. This implies the above result on independence number as well as more general theorems due to Ajtai-Komlos-Pintz-Spencer-Szemeredi, and Duke-Lefmann-Rodl. The proof technique is inspired by work of Johansson on graph coloring and uses the semi-random or nibble method. This talk will be accessible to a general mathematical audience.