The asymptotic lower-bound conjecture for edge-coloring components

From papers

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 nrn\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 kr+1k\geq r+1,

f(n,k,r)=n(1rzk,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.

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

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

Solutions 0

No solutions have been posted yet.