For every integer k≥ 2, there exists a convex function f_k:[0,∞)→[0,1] satisfying f_k(x)=(1-o_x(1))(fraclog x(k-1)x)^1/(k-1) as x→∞, such that every uncrowded k-uniform hypergraph H admits a local-demand fractional coloring with demand function phi:V(H)→[0,1] whenever phi(v)≤ f_k(deg_H(v)) for every vertex v. Here a local-demand fractional coloring means a weighted collection of independent sets whose total weight covering each vertex v is at least phi(v), and uncrowded means that H has girth at least 5.

Yu–Zhang local-demand coloring conjecture

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

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

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

References

Primary source

arXiv

Additional references

Random independent sets in uncrowded hypergraphs — arXiv — Abhishek Dhawan, Lina Li, Abhishek Methuku, Minh-Quan Vo, Kewen Yuan

extremal-combinatorics hypergraph-theory

Posted 12 hours ago · edited 12 hours ago

Progress summary

Refreshed 12 hours ago

Claimed solved

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.7$ asserts that for every integer $k\geq 2$ , there is a convex function $f_k$ with asymptotic behavior $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 $k$ -uniform hypergraph when $\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

No solutions have been posted yet.