Simultaneous multipartite subhypergraph conjecture

Let rr be a positive integer, and let H1,,H\mathcal{H}_1,\dots,\mathcal{H}_\ell be rr-uniform hypergraphs on the same vertex set VV, where Hi\mathcal{H}_i has mim_i hyperedges. A hyperedge meets every class of a partition when it has at least one vertex in each class.

Simultaneous multipartite subhypergraph conjecture. There exists a partition of VV into rr classes V1,,VrV_1,\dots,V_r such that, for every i=1,,i=1,\dots,\ell, at least

r!mirro(mi)\frac{r!m_i}{r^r}-o(m_i)

hyperedges of Hi\mathcal{H}_i meet each of the classes V1,,VrV_1,\dots,V_r.

For a single hypergraph, the leading term follows by randomly partitioning the vertices, and the conjecture asserts that nearly the same proportion can be achieved simultaneously for several hypergraphs. The supplied text does not indicate whether the conjecture is open or resolved.

Sources & referencesView supporting material

Primary source

Daniela Kuehn and Deryk Osthus, “Maximizing several cuts simultaneously”, arXiv:math/0503403 (2005).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.