*****************************************************************************
* www.FindStat.org - The Combinatorial Statistic Finder *
* *
* Copyright (C) 2019 The FindStatCrew <info@findstat.org> *
* *
* This information is distributed in the hope that it will be useful, *
* but WITHOUT ANY WARRANTY; without even the implied warranty of *
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. *
*****************************************************************************
-----------------------------------------------------------------------------
Statistic identifier: St001765
-----------------------------------------------------------------------------
Collection: Graphs
-----------------------------------------------------------------------------
Description: The number of connected components of the friends and strangers graph.
Let $X$ and $Y$ be graphs with the same vertex set $\{1,\dots,n\}$. Then the friends-and-strangers graph has as vertex set the set of permutations $\mathfrak S_n$ and edges $\left(\sigma, (i, j)\circ\sigma\right)$ if $(i, j)$ is an edge of $X$ and $\left(\sigma(i), \sigma(j)\right)$ is an edge of $Y$.
This statistic is the number of connected components of the friends and strangers graphs where $X=Y$.
For example, if $X$ is a complete graph the statistic is $1$, if $X$ has no edges, the statistic is $n!$, and if $X$ is the path graph, the statistic is
$$
\sum_{k=0}^{\lfloor n/2\rfloor} (-1)^k (n-k)!\binom{n-k}{k},
$$
see [thm. 2.2, 3].
-----------------------------------------------------------------------------
References: [1] Defant, C., Kravitz, N. Friends and Strangers Walking on Graphs [[arXiv:2009.05040]]
[2] Alon, N., Defant, C., Kravitz, N. Typical and Extremal Aspects of Friends-and-Strangers Graphs [[arXiv:2009.07840]]
[3] Stanley, R. P. An equivalence relation on the symmetric group and multiplicity-free flag $h$-vectors [[MathSciNet:3029438]]
-----------------------------------------------------------------------------
Code:
def FS(X, Y):
n = X.num_verts()
assert n == Y.num_verts()
X = X.relabel(inplace=False)
Y = Y.relabel(inplace=False)
V = list(Permutations(n))
E = []
for pi in V:
for i, j in X.edges(labels=False):
a, b = pi[i], pi[j]
if Y.has_edge(a-1, b-1):
pi1 = list(pi)
pi1[i], pi1[j] = b, a
pi1 = Permutation(pi1)
E.append((pi, pi1))
return Graph([V, E]).copy(immutable=True)
def statistic(G):
return FS(G, G).connected_components_number()
-----------------------------------------------------------------------------
Statistic values:
([],1) => 1
([],2) => 2
([(0,1)],2) => 1
([],3) => 6
([(1,2)],3) => 5
([(0,2),(1,2)],3) => 2
([(0,1),(0,2),(1,2)],3) => 1
([],4) => 24
([(2,3)],4) => 22
([(1,3),(2,3)],4) => 16
([(0,3),(1,3),(2,3)],4) => 6
([(0,3),(1,2)],4) => 18
([(0,3),(1,2),(2,3)],4) => 8
([(1,2),(1,3),(2,3)],4) => 10
([(0,3),(1,2),(1,3),(2,3)],4) => 2
([(0,2),(0,3),(1,2),(1,3)],4) => 2
([(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 1
([(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 1
([],5) => 120
([(3,4)],5) => 114
([(2,4),(3,4)],5) => 96
([(1,4),(2,4),(3,4)],5) => 66
([(0,4),(1,4),(2,4),(3,4)],5) => 24
([(1,4),(2,3)],5) => 98
([(1,4),(2,3),(3,4)],5) => 68
([(0,1),(2,4),(3,4)],5) => 74
([(2,3),(2,4),(3,4)],5) => 74
([(0,4),(1,4),(2,3),(3,4)],5) => 32
([(1,4),(2,3),(2,4),(3,4)],5) => 42
([(0,4),(1,4),(2,3),(2,4),(3,4)],5) => 7
([(1,3),(1,4),(2,3),(2,4)],5) => 34
([(0,4),(1,2),(1,3),(2,4),(3,4)],5) => 8
([(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 21
([(0,4),(1,3),(2,3),(2,4),(3,4)],5) => 12
([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 2
([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4)],5) => 2
([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 1
([(0,4),(1,3),(2,3),(2,4)],5) => 42
([(0,1),(2,3),(2,4),(3,4)],5) => 46
([(0,3),(1,2),(1,4),(2,4),(3,4)],5) => 16
([(0,3),(0,4),(1,2),(1,4),(2,4),(3,4)],5) => 3
([(0,3),(0,4),(1,2),(1,4),(2,3)],5) => 20
([(0,1),(0,4),(1,3),(2,3),(2,4),(3,4)],5) => 2
([(0,3),(0,4),(1,2),(1,4),(2,3),(2,4),(3,4)],5) => 1
([(0,4),(1,2),(1,3),(2,3),(2,4),(3,4)],5) => 3
([(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 17
([(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 2
([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 1
([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4)],5) => 1
([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,4),(3,4)],5) => 1
([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 1
([(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 1
([],6) => 720
([(4,5)],6) => 696
([(3,5),(4,5)],6) => 624
([(2,5),(3,5),(4,5)],6) => 504
([(1,5),(2,5),(3,5),(4,5)],6) => 336
([(0,5),(1,5),(2,5),(3,5),(4,5)],6) => 120
([(2,5),(3,4)],6) => 628
([(2,5),(3,4),(4,5)],6) => 508
([(1,2),(3,5),(4,5)],6) => 520
([(3,4),(3,5),(4,5)],6) => 528
([(1,5),(2,5),(3,4),(4,5)],6) => 352
([(0,1),(2,5),(3,5),(4,5)],6) => 372
([(2,5),(3,4),(3,5),(4,5)],6) => 388
([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => 156
([(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 221
([(0,5),(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 33
([(2,4),(2,5),(3,4),(3,5)],6) => 356
([(0,5),(1,5),(2,4),(3,4)],6) => 400
([(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 196
([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => 220
([(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 270
([(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 228
([(0,5),(1,5),(2,4),(3,4),(4,5)],6) => 184
([(0,5),(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 36
([(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 123
([(0,5),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 65
([(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 7
([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 68
([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 72
([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 4
([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 46
([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 14
([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2
([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 2
([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1
([(0,5),(1,4),(2,3)],6) => 534
([(1,5),(2,4),(3,4),(3,5)],6) => 372
([(0,1),(2,5),(3,4),(4,5)],6) => 394
([(1,2),(3,4),(3,5),(4,5)],6) => 392
([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => 214
([(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 238
([(0,1),(2,5),(3,4),(3,5),(4,5)],6) => 254
([(0,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 79
([(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 133
([(0,5),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 11
([(1,4),(1,5),(2,3),(2,5),(3,4)],6) => 220
([(0,5),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 66
([(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 96
([(0,5),(1,2),(1,4),(2,3),(3,5),(4,5)],6) => 106
([(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 126
([(0,5),(1,4),(2,3),(3,4),(3,5),(4,5)],6) => 90
([(0,5),(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 6
([(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 21
([(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 53
([(0,5),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 2
([(0,5),(1,4),(2,3),(2,4),(3,5)],6) => 258
([(0,1),(2,4),(2,5),(3,4),(3,5)],6) => 242
([(0,5),(1,5),(2,3),(2,4),(3,4)],6) => 273
([(0,4),(1,2),(1,3),(2,5),(3,5),(4,5)],6) => 98
([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5)],6) => 139
([(0,4),(1,2),(2,5),(3,4),(3,5),(4,5)],6) => 114
([(0,1),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 143
([(0,4),(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 101
([(0,3),(0,4),(1,2),(1,5),(2,5),(3,5),(4,5)],6) => 10
([(0,3),(1,4),(1,5),(2,4),(2,5),(3,5),(4,5)],6) => 32
([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 32
([(0,1),(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3
([(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 210
([(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 12
([(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 81
([(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 7
([(0,1),(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 16
([(0,3),(0,5),(1,3),(1,5),(2,4),(2,5),(3,4),(4,5)],6) => 1
([(0,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3
([(0,5),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 2
([(0,1),(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2
([(0,4),(0,5),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 1
([(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 2
([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 30
([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 9
([(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2
([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 1
([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1
([(0,5),(1,3),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 6
([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 34
([(0,5),(1,3),(1,4),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 2
([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 27
([(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 2
([(0,4),(0,5),(1,2),(1,3),(2,5),(3,4)],6) => 156
([(0,3),(0,5),(1,2),(1,5),(2,4),(3,4),(4,5)],6) => 15
([(0,5),(1,2),(1,4),(2,3),(3,4),(3,5),(4,5)],6) => 24
([(0,1),(0,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 45
([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 36
([(0,5),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 19
([(0,1),(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2
([(0,4),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 5
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 3
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 1
([(0,4),(0,5),(1,2),(1,3),(2,4),(2,5),(3,4),(3,5)],6) => 2
([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 3
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 1
([(0,4),(0,5),(1,2),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1
([(0,5),(1,2),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2
([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 26
([(0,5),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2
([(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2
([(0,4),(0,5),(1,2),(1,4),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 1
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 1
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1
([(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1
([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)],6) => 2
([(0,1),(0,2),(0,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1
([(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 1
([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 1
([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1
([(0,4),(0,5),(1,2),(1,3),(2,3),(4,5)],6) => 164
([(0,2),(1,4),(1,5),(2,3),(3,4),(3,5),(4,5)],6) => 50
([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(4,5)],6) => 54
([(0,1),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 101
([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 5
([(0,1),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 25
([(0,1),(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3
([(0,4),(0,5),(1,2),(1,3),(2,3),(2,5),(3,4),(4,5)],6) => 6
([(0,4),(0,5),(1,2),(1,3),(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 1
([(0,3),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3
([(0,3),(0,5),(1,2),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1
([(0,1),(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2
([(0,3),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 1
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4)],6) => 2
([(0,1),(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 6
([(0,3),(0,4),(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 1
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 1
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,5),(3,4)],6) => 2
([(0,1),(0,3),(0,5),(1,2),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 1
([(0,1),(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1
([(0,2),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 1
([(0,4),(0,5),(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1
([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2
([(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 26
([(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 2
([(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1
([(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 1
([(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 1
([(0,1),(0,4),(0,5),(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1
([(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 1
([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 1
([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1
([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1
([(0,1),(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 1
-----------------------------------------------------------------------------
Created: Jan 21, 2022 at 17:44 by Martin Rubey
-----------------------------------------------------------------------------
Last Updated: Jan 21, 2022 at 17:44 by Martin Rubey