Judicious partitions of 3-uniform hypergraphs

Combinatorics Seminar
Friday, January 21, 2011 - 15:05
1 hour (actually 50 minutes)
Skiles 006
School of Math. Georgia Tech.
Judicious partitioning problems on graphs and hypergraphs ask for partitions that optimize several quantities simultaneously. In this talk we first review the history of such problems. We will then focus on a conjecture of Bollobas and Thomason  that the vertices of any r-uniform hypergraphs with m edges can be partitioned into r sets so that each set meets at least rm/(2r-1) edges. We will show that for r=3 and  m large we can get an even better bound than what the conjecture suggests.