The asymptotic lower-bound conjecture for edge-coloring components

About 24 years old · traced to

Let KnrK_n^r be the complete rr-uniform hypergraph, let f(n,k,r)f(n,k,r) denote the minimum possible number of monochromatic components in an edge-coloring using at most kk colors, and let zk,rz_{k,r} be the infimum, over all n≥rn\geq r, of the minimum possible maximum fraction of vertices incident with an edge of a single color in such a coloring.

Asymptotic lower-bound conjecture. For k≥r+1k\geq r+1,

f(n,k,r)=n(1r−zk,rr)(1+on(1)).f(n,k,r)=n\left(\frac{1}{r}-\frac{z_{k,r}}{r}\right)(1+o_n(1)).

The conjecture asserts that the lower bound in the preceding asymptotic theorem is asymptotically sharp. Infinitely many values of zk,rz_{k,r} are known, while the values of infinitely many others remain open problems.

References

Primary source

Yair Caro and Raphael Yuster, “Edge coloring complete uniform hypergraphs with many components”, arXiv:math/0202231 (2002).

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.