Generalized double-flip decomposition conjecture for friends-and-strangers graphs

At least 3 years old · documented by

Let YY be a graph, let Y‾\overline{Y} be its complement, and let Acyc⁡(Y‾)\operatorname{Acyc}(\overline{Y}) denote the acyclic orientations of Y‾\overline{Y}. Let α≈ijα′\alpha\approx_{ij}\alpha' mean that the acyclic orientations are related by a sequence of good {i,j}\{i,j\}-double-flips, and let Path⁡nij\operatorname{Path}_n^{ij} be obtained by appending the edge {i,j}\{i,j\} to Path⁡n\operatorname{Path}_n. For each equivalence class [α]≈ij[\alpha]_{\approx_{ij}}, choose a linear extension σ[α]≈ij∈L([α]≈ij)\sigma_{[\alpha]_{\approx_{ij}}}\in\mathcal L([\alpha]_{\approx_{ij}}), and let H[α]≈ijH_{[\alpha]_{\approx_{ij}}} be the connected component of FS(Path⁡nij,Y)\mathsf{FS}(\operatorname{Path}_n^{ij},Y) containing it. Generalized double-flip decomposition conjecture. The component H[α]≈ijH_{[\alpha]_{\approx_{ij}}} depends only on [α]≈ij[\alpha]_{\approx_{ij}}, has vertex set L([α]≈ij)\mathcal L([\alpha]_{\approx_{ij}}), and

FS(Path⁡nij,Y)=⨁α∈Acyc⁡(Y‾)/≈ijH[α]≈ij.\mathsf{FS}(\operatorname{Path}_n^{ij},Y)=\bigoplus_{\alpha\in\operatorname{Acyc}(\overline{Y})/\approx_{ij}}H_{[\alpha]_{\approx_{ij}}}.

This is presented as a suspected generalization of an earlier theorem; the paper does not establish it.

References

Primary source

Ryan Jeong, “On Structural Aspects of Friends-And-Strangers Graphs”, arXiv:2203.10337 (2022).

Additional references

2 papers in this index state this conjecture (2022). The statement above is taken from the most recent of them; the others are arXiv:2201.00665.

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.