The twin-width gap conjecture for random Latin square graphs
Let be a random Latin square graph, meaning the graph obtained from a randomly chosen Latin square. Write for its twin-width and for its -collapsibility parameter.
Twin-width gap conjecture. The twin-width of is asymptotically larger than , that is,
as tends to infinity.
This conjecture predicts that the upper bound obtained from -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.
References
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
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.