← All problems

Yu–Zhang local-demand coloring conjecture

For every integer k≥2k\ge 2, there exists a convex function fk:[0,∞)→[0,1]f_k:[0,\infty)\to[0,1] satisfying

fk(x)=(1−ox(1))(log⁡x(k−1)x)1/(k−1)f_k(x)=(1-o_{x}(1))\left(\frac{\log x}{(k-1)x}\right)^{1/(k-1)}

as x→∞x\to\infty, such that every uncrowded kk-uniform hypergraph HH admits a local-demand fractional coloring with demand function ϕ:V(H)→[0,1]\phi:V(H)\to[0,1] whenever ϕ(v)≤fk(deg⁡H(v))\phi(v)\le f_k(\deg_H(v)) for every vertex vv. Here a local-demand fractional coloring means a weighted collection of independent sets whose total weight covering each vertex vv is at least ϕ(v)\phi(v), and uncrowded means that HH has girth at least 55.

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

A new preprint claims to prove the conjecture, but the result has not been independently checked.

The conjecture concerns local-demand colorings of uncrowded uniform hypergraphs. A recent preprint explicitly claims to resolve Yu–Zhang’s conjecture by constructing an admissible demand function and an independent-set sampling algorithm.

Recent preprint claim

Theorem 1.71.7 asserts that for every integer k≥2k\geq 2, there is a convex function fkf_k with asymptotic behavior fk(x)=(1−ox(1))(log⁡x(k−1)x)1/(k−1)f_k(x)=(1-o_x(1))\left(\frac{\log x}{(k-1)x}\right)^{1/(k-1)}, guaranteeing a ϕ\phi-coloring of every uncrowded kk-uniform hypergraph when ϕ(v)≤fk(deg⁡(v))\phi(v)\leq f_k(\deg(v)). The authors state that this resolves Yu–Zhang [49, Conjecture 4.3], while noting that Yu and Zhang independently obtained the result. No independent verification, correction, or referee assessment was found.

Current status (as of October 2026): The conjecture is claimed solved by an unrefereed preprint, but its proof has not been independently verified.

Sources

Solutions 0

No solutions have been posted yet.