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

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 Pathnij\operatorname{Path}_n^{ij} be obtained by appending the edge {i,j}\{i,j\} to Pathn\operatorname{Path}_n. For each equivalence class [α]ij[\alpha]_{\approx_{ij}}, choose a linear extension σ[α]ijL([α]ij)\sigma_{[\alpha]_{\approx_{ij}}}\in\mathcal L([\alpha]_{\approx_{ij}}), and let H[α]ijH_{[\alpha]_{\approx_{ij}}} be the connected component of FS(Pathnij,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(Pathnij,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.

Sources & referencesView supporting material

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.