*****************************************************************************
* 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: St001758
-----------------------------------------------------------------------------
Collection: Graphs
-----------------------------------------------------------------------------
Description: The number of orbits of promotion on a graph.
Let $(V, E)$ be a graph with $n=|V|$ vertices, and let $\sigma: V \to [n]$ be a labelling of its vertices. Let
$
\tau_{i, j}(\sigma) =
\begin{cases}
\sigma & \text{if $\{\sigma^{-1}(i), \sigma^{-1}(j)\}\in E$}\\
(i, j)\circ\sigma & \text{otherwise}.
\end{cases}
$
The promotion operator is the product $\tau_{n-1,n}\dots\tau_{1,2}$.
This statistic records the number of orbits in the orbit decomposition of promotion.
-----------------------------------------------------------------------------
References: [1] Defant, C. Toric Promotion [[arXiv:2112.06843]]
-----------------------------------------------------------------------------
Code:
from sage.combinat.cyclic_sieving_phenomenon import orbit_decomposition
def toggle_labelling(G, pi, i, j):
if G.has_edge(pi.index(i), pi.index(j)):
return pi
sigma = [j if e == i else i if e == j else e for e in pi]
return Permutation(sigma)
def promotion_labelling(G, pi):
n = G.num_verts()
assert set(G.vertices()) == set(range(n))
for i in range(1, n):
pi = toggle_labelling(G, pi, i, i+1)
return pi
def promotion_labelling_orbits(G):
G = G.canonical_label().copy(immutable=True)
return promotion_labelling_orbits_aux(G)
@cached_function
def promotion_labelling_orbits_aux(G):
n = G.num_verts()
return orbit_decomposition(Permutations(n),
lambda pi: promotion_labelling(G, pi))
def statistic(G):
return len(promotion_labelling_orbits(G))
-----------------------------------------------------------------------------
Statistic values:
([],1) => 1
([],2) => 1
([(0,1)],2) => 2
([],3) => 2
([(1,2)],3) => 2
([(0,2),(1,2)],3) => 4
([(0,1),(0,2),(1,2)],3) => 6
([],4) => 6
([(2,3)],4) => 6
([(1,3),(2,3)],4) => 4
([(0,3),(1,3),(2,3)],4) => 10
([(0,3),(1,2)],4) => 8
([(0,3),(1,2),(2,3)],4) => 10
([(1,2),(1,3),(2,3)],4) => 6
([(0,3),(1,2),(1,3),(2,3)],4) => 12
([(0,2),(0,3),(1,2),(1,3)],4) => 16
([(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 18
([(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 24
([],5) => 24
([(3,4)],5) => 24
([(2,4),(3,4)],5) => 16
([(1,4),(2,4),(3,4)],5) => 16
([(0,4),(1,4),(2,4),(3,4)],5) => 40
([(1,4),(2,3)],5) => 24
([(1,4),(2,3),(3,4)],5) => 12
([(0,1),(2,4),(3,4)],5) => 16
([(2,3),(2,4),(3,4)],5) => 24
([(0,4),(1,4),(2,3),(3,4)],5) => 24
([(1,4),(2,3),(2,4),(3,4)],5) => 16
([(0,4),(1,4),(2,3),(2,4),(3,4)],5) => 40
([(1,3),(1,4),(2,3),(2,4)],5) => 24
([(0,4),(1,2),(1,3),(2,4),(3,4)],5) => 32
([(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 24
([(0,4),(1,3),(2,3),(2,4),(3,4)],5) => 28
([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 40
([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4)],5) => 56
([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 60
([(0,4),(1,3),(2,3),(2,4)],5) => 28
([(0,1),(2,3),(2,4),(3,4)],5) => 24
([(0,3),(1,2),(1,4),(2,4),(3,4)],5) => 32
([(0,3),(0,4),(1,2),(1,4),(2,4),(3,4)],5) => 48
([(0,3),(0,4),(1,2),(1,4),(2,3)],5) => 40
([(0,1),(0,4),(1,3),(2,3),(2,4),(3,4)],5) => 48
([(0,3),(0,4),(1,2),(1,4),(2,3),(2,4),(3,4)],5) => 60
([(0,4),(1,2),(1,3),(2,3),(2,4),(3,4)],5) => 40
([(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 24
([(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 48
([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 72
([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4)],5) => 64
([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,4),(3,4)],5) => 84
([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 96
([(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 120
([],6) => 120
([(4,5)],6) => 120
([(3,5),(4,5)],6) => 80
([(2,5),(3,5),(4,5)],6) => 80
([(1,5),(2,5),(3,5),(4,5)],6) => 40
([(0,5),(1,5),(2,5),(3,5),(4,5)],6) => 148
([(2,5),(3,4)],6) => 120
([(2,5),(3,4),(4,5)],6) => 60
([(1,2),(3,5),(4,5)],6) => 80
([(3,4),(3,5),(4,5)],6) => 120
([(1,5),(2,5),(3,4),(4,5)],6) => 32
([(0,1),(2,5),(3,5),(4,5)],6) => 96
([(2,5),(3,4),(3,5),(4,5)],6) => 80
([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => 112
([(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 40
([(0,5),(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 152
([(2,4),(2,5),(3,4),(3,5)],6) => 120
([(0,5),(1,5),(2,4),(3,4)],6) => 80
([(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 32
([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => 96
([(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 120
([(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 28
([(0,5),(1,5),(2,4),(3,4),(4,5)],6) => 96
([(0,5),(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 128
([(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 40
([(0,5),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 108
([(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 140
([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 56
([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 116
([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 156
([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 60
([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 120
([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 164
([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 260
([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 276
([(0,5),(1,4),(2,3)],6) => 128
([(1,5),(2,4),(3,4),(3,5)],6) => 44
([(0,1),(2,5),(3,4),(4,5)],6) => 72
([(1,2),(3,4),(3,5),(4,5)],6) => 120
([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => 92
([(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 48
([(0,1),(2,5),(3,4),(3,5),(4,5)],6) => 96
([(0,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 120
([(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 48
([(0,5),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 160
([(1,4),(1,5),(2,3),(2,5),(3,4)],6) => 80
([(0,5),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 116
([(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 56
([(0,5),(1,2),(1,4),(2,3),(3,5),(4,5)],6) => 104
([(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 40
([(0,5),(1,4),(2,3),(3,4),(3,5),(4,5)],6) => 72
([(0,5),(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 136
([(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 116
([(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 60
([(0,5),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 152
([(0,5),(1,4),(2,3),(2,4),(3,5)],6) => 100
([(0,1),(2,4),(2,5),(3,4),(3,5)],6) => 144
([(0,5),(1,5),(2,3),(2,4),(3,4)],6) => 96
([(0,4),(1,2),(1,3),(2,5),(3,5),(4,5)],6) => 124
([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5)],6) => 112
([(0,4),(1,2),(2,5),(3,4),(3,5),(4,5)],6) => 108
([(0,1),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 144
([(0,4),(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 112
([(0,3),(0,4),(1,2),(1,5),(2,5),(3,5),(4,5)],6) => 144
([(0,3),(1,4),(1,5),(2,4),(2,5),(3,5),(4,5)],6) => 144
([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 120
([(0,1),(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 152
([(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 120
([(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 144
([(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 48
([(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 168
([(0,1),(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 156
([(0,3),(0,5),(1,3),(1,5),(2,4),(2,5),(3,4),(4,5)],6) => 196
([(0,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 168
([(0,5),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 148
([(0,1),(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 196
([(0,4),(0,5),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 216
([(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 168
([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 72
([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 136
([(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 176
([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 272
([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 288
([(0,5),(1,3),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 160
([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 64
([(0,5),(1,3),(1,4),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 172
([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 84
([(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 200
([(0,4),(0,5),(1,2),(1,3),(2,5),(3,4)],6) => 140
([(0,3),(0,5),(1,2),(1,5),(2,4),(3,4),(4,5)],6) => 180
([(0,5),(1,2),(1,4),(2,3),(3,4),(3,5),(4,5)],6) => 144
([(0,1),(0,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 156
([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 128
([(0,5),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 136
([(0,1),(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 196
([(0,4),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 160
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 184
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 208
([(0,4),(0,5),(1,2),(1,3),(2,4),(2,5),(3,4),(3,5)],6) => 224
([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 176
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 256
([(0,4),(0,5),(1,2),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 240
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 272
([(0,5),(1,2),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 192
([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 96
([(0,5),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 184
([(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 216
([(0,4),(0,5),(1,2),(1,4),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 224
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 192
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 240
([(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 312
([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)],6) => 336
([(0,1),(0,2),(0,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 352
([(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 296
([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 384
([(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) => 408
([(0,4),(0,5),(1,2),(1,3),(2,3),(4,5)],6) => 144
([(0,2),(1,4),(1,5),(2,3),(3,4),(3,5),(4,5)],6) => 136
([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(4,5)],6) => 144
([(0,1),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 144
([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 168
([(0,1),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 168
([(0,1),(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 192
([(0,4),(0,5),(1,2),(1,3),(2,3),(2,5),(3,4),(4,5)],6) => 188
([(0,4),(0,5),(1,2),(1,3),(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 232
([(0,3),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 192
([(0,3),(0,5),(1,2),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 212
([(0,1),(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 232
([(0,3),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 256
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 312
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 336
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4)],6) => 200
([(0,1),(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 184
([(0,3),(0,4),(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 240
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 280
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,5),(3,4)],6) => 264
([(0,1),(0,3),(0,5),(1,2),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 308
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 264
([(0,1),(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 344
([(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) => 408
([(0,2),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 288
([(0,4),(0,5),(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 264
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 312
([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 216
([(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 120
([(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 240
([(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) => 360
([(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) => 480
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 368
([(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 336
([(0,1),(0,4),(0,5),(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 384
([(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) => 432
([(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) => 480
([(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) => 528
([(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) => 600
([(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) => 720
-----------------------------------------------------------------------------
Created: Dec 14, 2021 at 16:03 by Martin Rubey
-----------------------------------------------------------------------------
Last Updated: Dec 14, 2021 at 16:03 by Martin Rubey