Random 1-factorisation substructure conjecture
Random 1-factorisation substructure conjecture
Let be the Latin square representing a uniformly random 1-factorisation of . Let be the length of its longest row cycle, and let be the size of its largest proper sub-1-factorisation. Random 1-factorisation conjecture. With probability ,
If true, this analogue of the proposed Steiner-quasigroup property would imply average-case polynomial-time canonical labelling for these 1-factorisations. The source gives no evidence of a resolution, so the conjecture remains open.
Sources & referencesView supporting material
Primary source
Michael J. Gill, Adam Mammoliti and Ian M. Wanless, “Canonical labelling of Latin squares in average-case polynomial time”, arXiv:2402.06205 (2024).
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.