Dhawan's multipartite hypergraph choosability conjecture

About 1 year old · traced to

Let k⩾2k\geqslant 2. A kk-partite kk-graph is a kk-uniform hypergraph whose vertex set has a partition into kk parts such that every edge contains exactly one vertex from each part. Let HH be such a hypergraph with maximum degree at most Δ\Delta, and let ch(H)\mathsf{ch}(H) denote its choice number.

Dhawan's conjecture. For every k⩾2k\geqslant 2, there is a constant c=c(k)>0c=c(k)>0 such that, for all sufficiently large Δ\Delta,

ch(H)⩽clog⁡Δ.\mathsf{ch}(H)\leqslant c\log \Delta.

This is a stronger uniform statement extending the bipartite-graph conjecture to all uniformities. A recent bound of order (Δ/log⁡Δ)1/(k−1)(\Delta/\log\Delta)^{1/(k-1)} is known, but the conjectured logarithmic bound remains unresolved.

References

Primary source

Peter Bradshaw, Abhishek Dhawan, Nhi Dinh, Shlok Mulye and Rohan Rathi, “Choosability of multipartite hypergraphs”, arXiv:2512.21222 (2025).

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.