The quadratic double-flip distance conjecture for acyclic orientations

From papers

Let GG be an nn-vertex graph, and let α,αAcyc(G)\alpha,\alpha”\in\operatorname{Acyc}(G) be double-flip equivalent, meaning that they can be connected by a sequence of allowed double-flips. The quadratic double-flip distance conjecture asserts that it is possible to go from α\alpha to α\alpha” in O(n2)O(n^2) double-flips. This is described as an unresolved strengthening of the paper's existing distance bound; together with the preceding cycle-diameter conjecture, it concerns efficient connectivity within double-flip equivalence classes.

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.