Judicious partitions of uniform hypergraphs

Publication date: 20 January 2017

Abstract: The vertices of any graph with

m

edges may be partitioned into two parts so that each part meets at least

f r a c 2 m 3

edges. Bollob'as and Thomason conjectured that the vertices of any

r

-uniform hypergraph with

m

edges may likewise be partitioned into

r

classes such that each part meets at least

f r a c r 2 r - 1 m

edges. In this paper we prove the weaker statement that, for each

r g e 4

, a partition into

r

classes may be found in which each class meets at least

f r a c r 3 r - 4 m

edges, a substantial improvement on previous bounds.

This page was built for publication: Judicious partitions of uniform hypergraphs