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

About 10 years old · traced to

Let r≥3r\geq 3, 1≤ℓ≤r1\leq \ell\leq r, and k≥1+r−ℓk\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+⌊k−r+ℓ−1ℓ⌋\mathrm{cov}(r,\ell,k)=1+\Bigl\lfloor \frac{k-r+\ell-1}{\ell}\Bigr\rfloor

for every r≥3r\geq 3, k≥1+r−ℓk\geq 1+r-\ell, and 1≤ℓ≤r1\leq \ell\leq r.

The paper proves the formula except when ℓ=1\ell=1 and k≥2rk\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.

References

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.