The coprime forest conjecture for friends-and-strangers graphs

Let XX and YY be graphs on nn vertices. A graph is biconnected if it is connected and has no cut vertex. Write Y\overline{Y} for the complement of YY, and let FS(X,Y)\operatorname{FS}(X,Y) denote the friends-and-strangers graph associated to XX and YY. Suppose that

Y=T1Tr\overline{Y}=\mathscr T_1\sqcup\cdots\sqcup\mathscr T_r

is a forest whose components are trees, with

gcd(V(T1),,V(Tr))=1.\gcd\bigl(|V(\mathscr T_1)|,\ldots,|V(\mathscr T_r)|\bigr)=1.

Coprime forest conjecture. If XX is biconnected, then FS(X,Y)\operatorname{FS}(X,Y) is connected.

This conjecture asserts that the necessary condition obtained from the cycle case is also sufficient for every biconnected graph XX. The paper verifies the property for several choices of YY, including when the complement is a tree on n1n-1 vertices together with an isolated vertex, but the general assertion is left open.

Sources & referencesView supporting material

Primary source

Colin Defant and Noah Kravitz, “Friends and Strangers Walking on Graphs”, arXiv:2009.05040 (2021).

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.