- FindStat

edit this statistic or download as text // json

Identifier

St001765: Graphs ⟶ ℤ

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

>>> Load all 208 entries. <<<

search for individual values

searching the database for the individual values of this statistic

/ search for generating function

searching the database for statistics with the same generating function

click to show known generating functions

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()

Created

Jan 21, 2022 at 17:44 by Martin Rubey

Updated

Jan 21, 2022 at 17:44 by Martin Rubey