Dhawan's multipartite hypergraph choosability conjecture

From papers

Let k2k\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 k2k\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/(k1)(\Delta/\log\Delta)^{1/(k-1)} is known, but the conjectured logarithmic bound remains unresolved.

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

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

Solutions 0

No solutions have been posted yet.