Bipartite random friends-and-strangers graph component conjecture

Let rr be a positive integer, let p[0,1]p\in[0,1], and let XX and YY be independently chosen random graphs from G(Kr,r,p)\mathcal G(K_{r,r},p), where Kr,rK_{r,r} is the complete bipartite graph with parts of size rr. Write FS(X,Y)\operatorname{\mathsf{FS}}(X,Y) for their friends-and-strangers graph. Bipartite component conjecture. There exists an absolute constant C>0C>0 such that if pCr1/2p\geq Cr^{-1/2}, then FS(X,Y)\operatorname{\mathsf{FS}}(X,Y) has exactly 22 connected components with high probability. This conjecture concerns the typical number of components in the bipartite random setting and would sharpen the paper’s estimates; its resolution is not supplied in the source.

Sources & referencesView supporting material

Primary source

Noga Alon, Colin Defant and Noah Kravitz, “Typical and Extremal Aspects of Friends-and-Strangers Graphs”, arXiv:2009.07840 (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.