The Pressing Game Conjecture on successful pressing sequences

About 11 years old · traced to

Let (G,c)(G,c) be a bicolored graph, where a press may be performed only at a black vertex, and call a sequence of presses successful if it transforms (G,c)(G,c) into an all-white, empty graph. Pressing Game Conjecture. Every successful pressing sequence can be reached from every other one by a sequence of edits involving at most four deletions or insertions.

This conjecture concerns the connectivity of the space of successful pressing sequences under local edits, and is motivated by the correspondence between successful pressing sequences in breakpoint graphs and minimum-length reversal-sorting sequences for signed permutations. The supplied text gives no evidence that the conjecture has been resolved.

References

Primary source

Joshua Cooper and Jeffrey Davis, “Successful Pressing Sequences for a Bicolored Graph and Binary Matrices”, arXiv:1502.07450 (2015).

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.