Ruskey's Hamiltonian-path conjecture for the graph of linear extensions

About 3 years old · traced to

Let PP be a finite sign-balanced poset, and let G(P)\mathcal G(P) be the graph whose vertices are the linear extensions of PP and whose edges correspond to adjacent switches. Ruskey’s conjecture. The graph G(P)\mathcal G(P) has a Hamiltonian path. This conjecture concerns Gray-code generation of linear extensions; the source cites algorithmic work and surveys but does not report a resolution.

References

Primary source

Swee Hong Chan and Igor Pak, “Linear extensions of finite posets”, arXiv:2311.02743 (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.