Generalized covering conjecture for complete (r,)(r,\ell)-partite hypergraphs

Let r3r\geq 3, 1r1\leq \ell\leq r, and k1+rk\geq 1+r-\ell. A complete rr-uniform (r,)(r,\ell)-partite hypergraph has its vertices partitioned into rr nonempty classes, and contains every rr-set meeting each class in at most \ell vertices. For a spanning kk-coloring, let cov(r,,k)\mathrm{cov}(r,\ell,k) be the maximum, over such colorings, of the minimum number of monochromatic connected components needed to cover the vertex set.

Generalized covering conjecture.

cov(r,,k)=1+kr+1\mathrm{cov}(r,\ell,k)=1+\Bigl\lfloor \frac{k-r+\ell-1}{\ell}\Bigr\rfloor

for every r3r\geq 3, k1+rk\geq 1+r-\ell, and 1r1\leq \ell\leq r.

The paper proves the formula except when =1\ell=1 and k2rk\geq 2r, where only bounds differing by one are established. Thus the unresolved cases coincide with the missing cases of the complete rr-partite conjecture.

Sources & referencesView supporting material

Primary source

András Gyárfás and Zoltán Király, “Covering complete partite hypergraphs by monochromatic components”, arXiv:1604.02791 (2016).

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.