All Articles

Speaker: Ryan Jeong, University of Pennsylvania

Abstract:
Given two simple graphs $X$ and $Y$ on $n$ vertices, the friends-and-strangers graph $\mathsf{FS}(X, Y)$ has as its vertices all $n!$ bijections from $V(X)$ to $V(Y)$, with bijections $\sigma, \tau$ adjacent if and only if they differ on two adjacent elements of $V(X)$ whose mappings are adjacent in $V(Y)$. These can be thought of as reconfiguration problems that generalize the famous $15$-puzzle. As such, two natural directions of inquiry are connectivity (which configurations are reachable from which other configurations) and diameters (worst-case guarantees on solution length for any particular solvable puzzle).

We explore a number of problems in both directions in this talk. We determine exactly which graphs $Y$ guarantee that $\mathsf{FS}(X,Y)$ is connected for any biconnected graph $X$, leading to the resolution of a conjecture of Defant and Kravitz. We also discuss the diameters of friends-and-strangers graphs: friends-and-strangers graphs have small diameter whenever $X$ or $Y$ is taken to be a path or a cycle, but in general, diameters of connected components of friends-and-strangers graphs fail to be polynomially bounded in the size of $X$ and $Y$, settling a conjecture of Alon, Defant, and Kravitz in the negative. Our construction yields the existence of infinitely many values of $n$ for which there are $n$-vertex graphs $X$ and $Y$ with the diameter of a component of $\mathsf{FS}(X, Y)$ being at least $n^{(\log n)/(\log \log n)}$. We conclude by discussing several exciting conjectures and problems for future research.

 

 

**If you’re around, come join us in 401 Carver to watch the talk together!**
If you can’t join the watch party, know that it’s nice for speakers to see some of the audience, so we encourage you to leave your camera on during the talk.