The quadratic diameter conjecture for friends-and-strangers graphs on cycles

From papers

Let YY be a graph on nn vertices, and let FS(Cyclen,Y)\mathsf{FS}(\textsf{Cycle}_n,Y) denote its friends-and-strangers graph. The quadratic diameter conjecture asserts that the maximum diameter of a connected component of

FS(Cyclen,Y)\mathsf{FS}(\textsf{Cycle}_n,Y)

is O(n2)O(n^2). This would sharpen the paper's polynomial diameter bound for cycles; the conjecture is presented as an unresolved improvement, and would imply an O(n3)O(n^3) bound for the corresponding double-flip distances.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Ryan Jeong, “On the Diameters of Friends-and-Strangers Graphs”, arXiv:2201.00665 (2023).

Solutions 0

No solutions have been posted yet.