The twin-width gap conjecture for random Latin square graphs
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.