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 lb⁡1(G)\operatorname{lb}_1(G) for its lb⁡1\operatorname{lb}_1-collapsibility parameter.

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

tww⁡(G)≫lb⁡1(G)\operatorname{tww}(G)\gg \operatorname{lb}_1(G)

as nn tends to infinity.

This conjecture predicts that the upper bound obtained from lb⁡1\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.

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

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.