# MIT-Harvard-MSR Combinatorics Seminar

Wednesday, October 20, 2021 at 4:15pm to 5:15pm

MIT-77 Massachusetts Avenue, Math Dept / Room 2-139

**Speaker**: Colin Defant (Harvard/Princeton)

**Title**: Friends and strangers walking on graphs

**Abstract**:

Let* X* and *Y* be simple graphs on n vertices. Identify the vertices of* Y* with *n* people, any two of whom are either friends or strangers (according to the edges and non-edges in *Y*), and imagine that the people sit on distinct vertices of *X*. Two people are allowed to swap places with each other if they are friends with each other and they are sitting on adjacent vertices of X. The friends-and-strangers graph FS(*X*,*Y*) has as its vertex set the collection of all configurations of people sitting on the vertices of *X*, where two configurations are adjacent when they are related via a single swap of this form. It is natural to study the connected components of FS(*X*,*Y*), which correspond to the equivalence classes of mutually-reachable configurations. This framework provides a common generalization for the famous 15-puzzle, transposition Cayley graphs of symmetric groups, and earlier works of Stanley and Wilson.

We will explicitly describe the connected components of FS(*X*,*Y*) in the special cases where *X* is a path or a cycle; the results for the latter are closely related to toric partial orders. We will also discuss minimum degree conditions on *X* and *Y *that guarantee FS(*X*,*Y*) is connected. Finally, we will show that if *X* and *Y* are *n*-vertex random graphs with edge probability *p*, then the threshold probability for the connectedness of FS(*X*,*Y*) is *p*=*n*^-1/2+o(1).

This talk is based on join work with Noga Alon and Noah Kravitz, and it will touch upon recent (separate) works of Kiril Bangachev and Ryan Jeong.

- Event Type
- Events By Interest
- Events By Audience
- Events By School
- Website

- Department
- Department of Mathematics
- Contact Email
- Add to my calendar

#### Recent Activity

No recent activity