The twin-width gap conjecture for random Latin square graphs

Let GG be a random Latin square graph, meaning the graph obtained from a randomly chosen n×nn\times n Latin square. Write tww(G)\operatorname{tww}(G) for its twin-width and lb1(G)\operatorname{lb}_1(G) for its lb1\operatorname{lb}_1-collapsibility parameter.

Twin-width gap conjecture. The twin-width of GG is asymptotically larger than lb1(G)\operatorname{lb}_1(G), that is,

tww(G)lb1(G)\operatorname{tww}(G)\gg \operatorname{lb}_1(G)

as nn tends to infinity.

This conjecture predicts that the upper bound obtained from lb1\operatorname{lb}_1-collapsibility is not asymptotically tight for random Latin square graphs, and that twin-width and this collapsibility parameter can have substantially different asymptotic behavior. The supplied text gives no resolution, so the conjecture remains open.

Sources & referencesView supporting material

Primary source

Irene Heinrich, Ferdinand Ihringer, Simon Raßmann and Lena Volk, “On the twin-width of near-regular graphs”, arXiv:2504.02342 (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.