Bosek's asymptotic harmonious coloring conjecture for hypergraphs

From papers

Let k,Δ2k,\Delta\geq 2. A harmonious coloring of a kk-uniform hypergraph HH is a vertex coloring that is rainbow on every edge and assigns distinct color sets to distinct edges; let h(H)h(H) be the least number of colors in such a coloring. If HH has mm edges and maximum degree Δ\Delta, then Bosek's conjecture. There exists a constant c=c(k,Δ)c=c(k,\Delta) such that

h(H)k!mk+c.h(H)\leq \sqrt[k]{k!m}+c.

The lower bound (rk)m\binom{r}{k}\leq m for a harmonious coloring using rr colors gives the leading-order term k!mk\sqrt[k]{k!m}, so the conjecture asks whether the known upper bound can be sharpened to this term up to an additive constant depending only on kk and Δ\Delta.

Progress summary

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

Sources & referencesView supporting material

Primary source

Sebastian Czerwiński, “On harmonious coloring of hypergraphs”, arXiv:2301.00302 (2024).

Solutions 0

No solutions have been posted yet.