On the Asymmetric Generalizations of Two Extremal Questions on Friends-and-Strangers Graphs

Abstract

For two graphs $X$ and $Y$ with vertex sets $V(X)$ and $V(Y)$ of the same cardinality $n,$ the friends-and-strangers graph $\mathsf{FS}(X,Y)$ was recently defined by Defant and Kravitz. The vertices of $\mathsf{FS}(X,Y)$ are the bijections from $V(X)$ to $V(Y),$ and two bijections $\sigma$ and $\tau$ are adjacent if they agree everywhere except at two vertices $a,b\in V(X)$ such that $a$ and $b$ are adjacent in $X$ and $\sigma (a)$ and $\sigma (b)$ are adjacent in $Y.$ We study generalized versions of two problems by Alon, Defant, and Kravitz. First, we show that if $X$ and $Y$ have minimum degrees $\delta (X)$ and $\delta (Y)$ that satisfy $\delta (X)>n/2,\delta (Y)>n/2,$ and $2\min (\delta (X),\delta (Y))+3\max (\delta (X),\delta (Y))\ge 3n,$ then $\mathsf{FS}(X,Y)$ is connected. As a corollary, we settle a recent conjecture by Alon, Defant, and Kravitz stating that there exists a number $d_n=3n/5+O(1)$ such that if both $X$ and $Y$ have minimum degrees at least $d_n,$ the graph $\mathsf{FS}(X,Y)$ is connected. When $X$ and $Y$ are bipartite, a parity obstruction prevents $\mathsf{FS}(X,Y)$ from being connected. We show that if $X$ and $Y$ are edge-subgraphs of $K_{r,r}$ that satisfy $\delta (X)+\delta (Y)\ge 3r/2+1,$ then the graph $\mathsf{FS}(X,Y)$ has exactly two connected components. As a corollary, we provide an almost complete answer to another recent question of Alon, Defant, and Kravitz asking for the minimum number $d_{r,r}^{\ast }$ such that for any edge-subgraph $X$ of $K_{r,r}$ satisfying $\delta (X)\ge d_{r,r}^{\ast },$ the graph $\mathsf{FS}(X,K_{r,r})$ has exactly two connected components. We show that $d_{r,r}^{\ast }=r/2+1$ when $r$ is even and $d_{r,r}^{\ast }\in \{\lceil r/2\rceil ,\lceil r/2\rceil +1\}$ when $r$ is odd.

28 pages, 16 figures