The supersaturation conjecture for independent transversals

Let GG be a graph with maximum degree Δ\Delta and let U\mathcal{U} be a (2Δ)(2\Delta)-thick partition of V(G)V(G). An independent transversal is a set containing exactly one vertex from each part of U\mathcal{U} and inducing no edges in GG. Supersaturation conjecture. The number of independent transversals of (G,U)(G,\mathcal{U}) is minimised when GG is a disjoint union of U|\mathcal{U}| copies of KΔ,ΔK_{\Delta,\Delta}. This conjecture proposes a sharp supersaturation-type strengthening of Haxell's theorem; the supplied text gives no resolution, so its status remains open.

Sources & referencesView supporting material

Primary source

Pjotr Buys, Ross J. Kang and Kenta Ozeki, “Reconfiguration of Independent Transversals”, arXiv:2407.04367 (2024).

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.