Friday, January 21, 2011 - 3:05pm
1 hour (actually 50 minutes)
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.