Home » Subject » Graph Theory » Hypergraphs

Simultaneous partition of hypergraphs

Importance: Medium ✭✭
Author(s): Kühn, Daniella
Osthus, Deryk
Subject: Graph Theory
» Hypergraphs
Keywords:
Recomm. for undergrads: no
Posted by: fhavet
on: March 6th, 2013
Problem   Let $ H_1 $ and $ H_2 $ be two $ r $-uniform hypergraph on the same vertex set $ V $. Does there always exist a partition of $ V $ into $ r $ classes $ V_1, \dots , V_r $ such that for both $ i=1,2 $, at least $ r!m_i/r^r -o(m_i) $ hyperedges of $ H_i $ meet each of the classes $ V_1, \dots , V_r $?

The bound on the number of hyperedges is what one would expect for a random partition. For graphs, the question was answered in the affirmative in [KO]. Keevash and Sudakov observed that the answer is negative if we consider many hypergraphs instead of just 2 (see [KO] for the example).

Bibliography

*[KO] D. Kühn and D. Osthus, Maximizing several cuts simultaneously, Combinatorics, Probability and Computing 16 (2007), 277-283.


* indicates original appearance(s) of problem.
add new comment