Constellations

A constellation is a tuple \((g_0, g_1, \dots, g_k)\) of permutations such that the product \(g_0 g_1 ... g_k\) is the identity. One often assumes that the group generated by \(g_0, g_1, \dots, g_k\) acts transitively ([LZ2004] definition 1). Geometrically, it corresponds to a covering of the 2-sphere ramified over \(k\) points (the transitivity condition corresponds to the connectivity of the covering).

EXAMPLES:

sage: c = Constellation(['(1,2)', '(1,3)', None])
sage: c
Constellation of length 3 and degree 3
g0 (1,2)(3)
g1 (1,3)(2)
g2 (1,3,2)
sage: C = Constellations(3,4); C
Connected constellations of length 3 and degree 4 on {1, 2, 3, 4}
sage: C.cardinality()  # long time
426

sage: C = Constellations(3, 4, domain=('a', 'b', 'c', 'd'))
sage: C
Connected constellations of length 3 and degree 4 on {'a', 'b', 'c', 'd'}
sage: c = C(('a','c'),(('b','c'),('a','d')), None)
sage: c
Constellation of length 3 and degree 4
g0 ('a','c')('b')('d')
g1 ('a','d')('b','c')
g2 ('a','d','c','b')
sage: c.is_connected()
True
sage: c.euler_characteristic()
2
sage: TestSuite(C).run()

>>> from sage.all import *
>>> c = Constellation(['(1,2)', '(1,3)', None])
>>> c
Constellation of length 3 and degree 3
g0 (1,2)(3)
g1 (1,3)(2)
g2 (1,3,2)
>>> C = Constellations(Integer(3),Integer(4)); C
Connected constellations of length 3 and degree 4 on {1, 2, 3, 4}
>>> C.cardinality()  # long time
426

>>> C = Constellations(Integer(3), Integer(4), domain=('a', 'b', 'c', 'd'))
>>> C
Connected constellations of length 3 and degree 4 on {'a', 'b', 'c', 'd'}
>>> c = C(('a','c'),(('b','c'),('a','d')), None)
>>> c
Constellation of length 3 and degree 4
g0 ('a','c')('b')('d')
g1 ('a','d')('b','c')
g2 ('a','d','c','b')
>>> c.is_connected()
True
>>> c.euler_characteristic()
2
>>> TestSuite(C).run()
sage.combinat.constellation.Constellation(g=None, mutable=False, connected=True, check=True)[source]

Constellation.

INPUT:

  • g – list of permutations

  • mutable – boolean (default: False); whether the result is mutable or not

  • connected – boolean (default: True); whether the result should be connected

  • check – boolean (default: True); whether or not to check. If it is True, then the list g must contain no None.

EXAMPLES:

Simple initialization:

sage: Constellation(['(0,1)','(0,3)(1,2)','(0,3,1,2)'])
Constellation of length 3 and degree 4
g0 (0,1)(2)(3)
g1 (0,3)(1,2)
g2 (0,3,1,2)

>>> from sage.all import *
>>> Constellation(['(0,1)','(0,3)(1,2)','(0,3,1,2)'])
Constellation of length 3 and degree 4
g0 (0,1)(2)(3)
g1 (0,3)(1,2)
g2 (0,3,1,2)

One of the permutation can be omitted:

sage: Constellation(['(0,1)', None, '(0,4)(1,2,3)'])
Constellation of length 3 and degree 5
g0 (0,1)(2)(3)(4)
g1 (0,3,2,1,4)
g2 (0,4)(1,2,3)

>>> from sage.all import *
>>> Constellation(['(0,1)', None, '(0,4)(1,2,3)'])
Constellation of length 3 and degree 5
g0 (0,1)(2)(3)(4)
g1 (0,3,2,1,4)
g2 (0,4)(1,2,3)

One can define mutable constellations:

sage: Constellation(([0,2,1], [2,1,0], [1,2,0]), mutable=True)
Constellation of length 3 and degree 3
g0 (0)(1,2)
g1 (0,2)(1)
g2 (0,1,2)

>>> from sage.all import *
>>> Constellation(([Integer(0),Integer(2),Integer(1)], [Integer(2),Integer(1),Integer(0)], [Integer(1),Integer(2),Integer(0)]), mutable=True)
Constellation of length 3 and degree 3
g0 (0)(1,2)
g1 (0,2)(1)
g2 (0,1,2)
class sage.combinat.constellation.Constellation_class(parent, g, connected, mutable, check)[source]

Bases: Element

Constellation.

A constellation or a tuple of permutations \((g_0,g_1,...,g_k)\) such that the product \(g_0 g_1 ... g_k\) is the identity.

braid_group_action(i)[source]

Act on self as the braid group generator that exchanges position \(i\) and \(i+1\).

INPUT:

  • i – integer in \([0, n-1]\) where \(n\) is the length of self

EXAMPLES:

sage: sigma = lambda c, i: c.braid_group_action(i)

sage: c = Constellation(['(0,1)(2,3,4)','(1,4)',None]); c
Constellation of length 3 and degree 5
g0 (0,1)(2,3,4)
g1 (0)(1,4)(2)(3)
g2 (0,1,3,2,4)
sage: sigma(c, 1)
Constellation of length 3 and degree 5
g0 (0,1)(2,3,4)
g1 (0,1,3,2,4)
g2 (0,3)(1)(2)(4)

>>> from sage.all import *
>>> sigma = lambda c, i: c.braid_group_action(i)

>>> c = Constellation(['(0,1)(2,3,4)','(1,4)',None]); c
Constellation of length 3 and degree 5
g0 (0,1)(2,3,4)
g1 (0)(1,4)(2)(3)
g2 (0,1,3,2,4)
>>> sigma(c, Integer(1))
Constellation of length 3 and degree 5
g0 (0,1)(2,3,4)
g1 (0,1,3,2,4)
g2 (0,3)(1)(2)(4)

Check the commutation relation:

sage: c = Constellation(['(0,1)(2,3,4)','(1,4)','(2,5)(0,4)',None])
sage: d = Constellation(['(0,1,3,5)','(2,3,4)','(0,3,5)',None])
sage: c13 = sigma(sigma(c, 0), 2)
sage: c31 = sigma(sigma(c, 2), 0)
sage: c13 == c31
True
sage: d13 = sigma(sigma(d, 0), 2)
sage: d31 = sigma(sigma(d, 2), 0)
sage: d13 == d31
True

>>> from sage.all import *
>>> c = Constellation(['(0,1)(2,3,4)','(1,4)','(2,5)(0,4)',None])
>>> d = Constellation(['(0,1,3,5)','(2,3,4)','(0,3,5)',None])
>>> c13 = sigma(sigma(c, Integer(0)), Integer(2))
>>> c31 = sigma(sigma(c, Integer(2)), Integer(0))
>>> c13 == c31
True
>>> d13 = sigma(sigma(d, Integer(0)), Integer(2))
>>> d31 = sigma(sigma(d, Integer(2)), Integer(0))
>>> d13 == d31
True

Check the braid relation:

sage: c121 = sigma(sigma(sigma(c, 1), 2), 1)
sage: c212 = sigma(sigma(sigma(c, 2), 1), 2)
sage: c121 == c212
True
sage: d121 = sigma(sigma(sigma(d, 1), 2), 1)
sage: d212 = sigma(sigma(sigma(d, 2), 1), 2)
sage: d121 == d212
True

>>> from sage.all import *
>>> c121 = sigma(sigma(sigma(c, Integer(1)), Integer(2)), Integer(1))
>>> c212 = sigma(sigma(sigma(c, Integer(2)), Integer(1)), Integer(2))
>>> c121 == c212
True
>>> d121 = sigma(sigma(sigma(d, Integer(1)), Integer(2)), Integer(1))
>>> d212 = sigma(sigma(sigma(d, Integer(2)), Integer(1)), Integer(2))
>>> d121 == d212
True
braid_group_orbit()[source]

Return the graph of the action of the braid group.

The action is considered up to isomorphism of constellation.

EXAMPLES:

sage: c = Constellation(['(0,1)(2,3,4)','(1,4)',None]); c
Constellation of length 3 and degree 5
g0 (0,1)(2,3,4)
g1 (0)(1,4)(2)(3)
g2 (0,1,3,2,4)
sage: G = c.braid_group_orbit()
sage: G.num_verts()
4
sage: G.num_edges()
12

>>> from sage.all import *
>>> c = Constellation(['(0,1)(2,3,4)','(1,4)',None]); c
Constellation of length 3 and degree 5
g0 (0,1)(2,3,4)
g1 (0)(1,4)(2)(3)
g2 (0,1,3,2,4)
>>> G = c.braid_group_orbit()
>>> G.num_verts()
4
>>> G.num_edges()
12
connected_components()[source]

Return the connected components.

OUTPUT: list of connected constellations

EXAMPLES:

sage: c = Constellation(['(0,1)(2)', None, '(0,1)(2)'], connected=False)
sage: cc = c.connected_components(); cc
[Constellation of length 3 and degree 2
g0 (0,1)
g1 (0)(1)
g2 (0,1),
Constellation of length 3 and degree 1
g0 (0)
g1 (0)
g2 (0)]
sage: all(c2.is_connected() for c2 in cc)
True

sage: c = Constellation(['(0,1,2)', None], connected=False)
sage: c.connected_components()
[Constellation of length 2 and degree 3
g0 (0,1,2)
g1 (0,2,1)]

>>> from sage.all import *
>>> c = Constellation(['(0,1)(2)', None, '(0,1)(2)'], connected=False)
>>> cc = c.connected_components(); cc
[Constellation of length 3 and degree 2
g0 (0,1)
g1 (0)(1)
g2 (0,1),
Constellation of length 3 and degree 1
g0 (0)
g1 (0)
g2 (0)]
>>> all(c2.is_connected() for c2 in cc)
True

>>> c = Constellation(['(0,1,2)', None], connected=False)
>>> c.connected_components()
[Constellation of length 2 and degree 3
g0 (0,1,2)
g1 (0,2,1)]
copy()[source]

Return a copy of self.

degree()[source]

Return the degree of the constellation.

The degree of a constellation is the number \(n\) that corresponds to the symmetric group \(S(n)\) in which the permutations of the constellation are defined.

EXAMPLES:

sage: c = Constellation([])
sage: c.degree()
0
sage: c = Constellation(['(0,1)',None])
sage: c.degree()
2
sage: c = Constellation(['(0,1)','(0,3,2)(1,5)',None,'(4,3,2,1)'])
sage: c.degree()
6

>>> from sage.all import *
>>> c = Constellation([])
>>> c.degree()
0
>>> c = Constellation(['(0,1)',None])
>>> c.degree()
2
>>> c = Constellation(['(0,1)','(0,3,2)(1,5)',None,'(4,3,2,1)'])
>>> c.degree()
6
euler_characteristic()[source]

Return the Euler characteristic of the surface.

ALGORITHM:

Hurwitz formula

EXAMPLES:

sage: c = Constellation(['(0,1)', '(0,2)', None])
sage: c.euler_characteristic()
2

sage: c = Constellation(['(0,1,2,3)','(1,3,0,2)', '(0,3,1,2)', None])
sage: c.euler_characteristic()
-4

>>> from sage.all import *
>>> c = Constellation(['(0,1)', '(0,2)', None])
>>> c.euler_characteristic()
2

>>> c = Constellation(['(0,1,2,3)','(1,3,0,2)', '(0,3,1,2)', None])
>>> c.euler_characteristic()
-4
g(i=None)[source]

Return the permutation \(g_i\) of the constellation.

INPUT:

  • i – integer or None (default)

If None , return instead the list of all \(g_i\).

EXAMPLES:

sage: c = Constellation(['(0,1,2)(3,4)','(0,3)',None])
sage: c.g(0)
(0,1,2)(3,4)
sage: c.g(1)
(0,3)
sage: c.g(2)
(0,4,3,2,1)
sage: c.g()
[(0,1,2)(3,4), (0,3), (0,4,3,2,1)]

>>> from sage.all import *
>>> c = Constellation(['(0,1,2)(3,4)','(0,3)',None])
>>> c.g(Integer(0))
(0,1,2)(3,4)
>>> c.g(Integer(1))
(0,3)
>>> c.g(Integer(2))
(0,4,3,2,1)
>>> c.g()
[(0,1,2)(3,4), (0,3), (0,4,3,2,1)]
genus()[source]

Return the genus of the surface.

EXAMPLES:

sage: c = Constellation(['(0,1)', '(0,2)', None])
sage: c.genus()
0

sage: c = Constellation(['(0,1)(2,3,4)','(1,3,4)(2,0)', None])
sage: c.genus()
1

>>> from sage.all import *
>>> c = Constellation(['(0,1)', '(0,2)', None])
>>> c.genus()
0

>>> c = Constellation(['(0,1)(2,3,4)','(1,3,4)(2,0)', None])
>>> c.genus()
1
is_connected()[source]

Test of connectedness.

EXAMPLES:

sage: c = Constellation(['(0,1)(2)', None, '(0,1)(2)'], connected=False)
sage: c.is_connected()
False
sage: c = Constellation(['(0,1,2)', None], connected=False)
sage: c.is_connected()
True

>>> from sage.all import *
>>> c = Constellation(['(0,1)(2)', None, '(0,1)(2)'], connected=False)
>>> c.is_connected()
False
>>> c = Constellation(['(0,1,2)', None], connected=False)
>>> c.is_connected()
True
is_isomorphic(other, return_map=False)[source]

Test of isomorphism.

Return True if the constellations are isomorphic (i.e. related by a common conjugacy) and return the permutation that conjugate the two permutations if return_map is True in such a way that self.relabel(m) == other.

ALGORITHM:

uses canonical labels obtained from the method relabel().

EXAMPLES:

sage: c = Constellation([[1,0,2],[2,1,0],[0,2,1],None])
sage: d = Constellation([[2,1,0],[0,2,1],[1,0,2],None])
sage: answer, mapping = c.is_isomorphic(d,return_map=True)
sage: answer
True
sage: c.relabel(mapping) == d
True

>>> from sage.all import *
>>> c = Constellation([[Integer(1),Integer(0),Integer(2)],[Integer(2),Integer(1),Integer(0)],[Integer(0),Integer(2),Integer(1)],None])
>>> d = Constellation([[Integer(2),Integer(1),Integer(0)],[Integer(0),Integer(2),Integer(1)],[Integer(1),Integer(0),Integer(2)],None])
>>> answer, mapping = c.is_isomorphic(d,return_map=True)
>>> answer
True
>>> c.relabel(mapping) == d
True
is_mutable()[source]

Return False as self is immutable.

EXAMPLES:

sage: c = Constellation(([0,2,1],[2,1,0],[1,2,0]), mutable=False)
sage: c.is_mutable()
False

>>> from sage.all import *
>>> c = Constellation(([Integer(0),Integer(2),Integer(1)],[Integer(2),Integer(1),Integer(0)],[Integer(1),Integer(2),Integer(0)]), mutable=False)
>>> c.is_mutable()
False
length()[source]

Return the number of permutations.

EXAMPLES:

sage: c = Constellation(['(0,1)','(0,2)','(0,3)',None])
sage: c.length()
4
sage: c = Constellation(['(0,1,3)',None,'(1,2)'])
sage: c.length()
3

>>> from sage.all import *
>>> c = Constellation(['(0,1)','(0,2)','(0,3)',None])
>>> c.length()
4
>>> c = Constellation(['(0,1,3)',None,'(1,2)'])
>>> c.length()
3
mutable_copy()[source]

Return a mutable copy of self.

EXAMPLES:

sage: c = Constellation(([0,2,1],[2,1,0],[1,2,0]), mutable=False)
sage: d = c.mutable_copy()
sage: d.is_mutable()
True

>>> from sage.all import *
>>> c = Constellation(([Integer(0),Integer(2),Integer(1)],[Integer(2),Integer(1),Integer(0)],[Integer(1),Integer(2),Integer(0)]), mutable=False)
>>> d = c.mutable_copy()
>>> d.is_mutable()
True
passport(i=None)[source]

Return the profile of self.

The profile of a constellation is the tuple of partitions associated to the conjugacy classes of the permutations of the constellation.

This is also called the passport.

EXAMPLES:

sage: c = Constellation(['(0,1,2)(3,4)','(0,3)',None])
sage: c.profile()
([3, 2], [2, 1, 1, 1], [5])

>>> from sage.all import *
>>> c = Constellation(['(0,1,2)(3,4)','(0,3)',None])
>>> c.profile()
([3, 2], [2, 1, 1, 1], [5])
profile(i=None)[source]

Return the profile of self.

The profile of a constellation is the tuple of partitions associated to the conjugacy classes of the permutations of the constellation.

This is also called the passport.

EXAMPLES:

sage: c = Constellation(['(0,1,2)(3,4)','(0,3)',None])
sage: c.profile()
([3, 2], [2, 1, 1, 1], [5])

>>> from sage.all import *
>>> c = Constellation(['(0,1,2)(3,4)','(0,3)',None])
>>> c.profile()
([3, 2], [2, 1, 1, 1], [5])
relabel(perm=None, return_map=False)[source]

Relabel self.

If perm is provided then relabel with respect to perm. Otherwise use canonical labels. In that case, if return_map is provided, the return also the map used for canonical labels.

Algorithm:

the cycle for g(0) are adjacent and the cycle are joined with respect to the other permutations. The minimum is taken for all possible renumerotations.

EXAMPLES:

sage: c = Constellation(['(0,1)(2,3,4)','(1,4)',None]); c
Constellation of length 3 and degree 5
g0 (0,1)(2,3,4)
g1 (0)(1,4)(2)(3)
g2 (0,1,3,2,4)
sage: c2 = c.relabel(); c2
Constellation of length 3 and degree 5
g0 (0,1)(2,3,4)
g1 (0)(1,2)(3)(4)
g2 (0,1,4,3,2)

>>> from sage.all import *
>>> c = Constellation(['(0,1)(2,3,4)','(1,4)',None]); c
Constellation of length 3 and degree 5
g0 (0,1)(2,3,4)
g1 (0)(1,4)(2)(3)
g2 (0,1,3,2,4)
>>> c2 = c.relabel(); c2
Constellation of length 3 and degree 5
g0 (0,1)(2,3,4)
g1 (0)(1,2)(3)(4)
g2 (0,1,4,3,2)

The map returned when the option return_map is set to True can be used to set the relabelling:

sage: c3, perm = c.relabel(return_map=True)
sage: c3 == c2 and c3 == c.relabel(perm=perm)
True

sage: S5 = SymmetricGroup(range(5))
sage: d = c.relabel(S5([4,3,1,0,2])); d
Constellation of length 3 and degree 5
g0 (0,2,1)(3,4)
g1 (0)(1)(2,3)(4)
g2 (0,1,2,4,3)
sage: d.is_isomorphic(c)
True

>>> from sage.all import *
>>> c3, perm = c.relabel(return_map=True)
>>> c3 == c2 and c3 == c.relabel(perm=perm)
True

>>> S5 = SymmetricGroup(range(Integer(5)))
>>> d = c.relabel(S5([Integer(4),Integer(3),Integer(1),Integer(0),Integer(2)])); d
Constellation of length 3 and degree 5
g0 (0,2,1)(3,4)
g1 (0)(1)(2,3)(4)
g2 (0,1,2,4,3)
>>> d.is_isomorphic(c)
True

We check that after a random relabelling the new constellation is isomorphic to the initial one:

sage: c = Constellation(['(0,1)(2,3,4)','(1,4)',None])
sage: p = S5.random_element()
sage: cc = c.relabel(perm=p)
sage: cc.is_isomorphic(c)
True

>>> from sage.all import *
>>> c = Constellation(['(0,1)(2,3,4)','(1,4)',None])
>>> p = S5.random_element()
>>> cc = c.relabel(perm=p)
>>> cc.is_isomorphic(c)
True

Check that it works for “non standard” labels:

sage: c = Constellation([(('a','b'),('c','d','e')),('b','d'), None])
sage: c.relabel()
Constellation of length 3 and degree 5
g0 ('a','b')('c','d','e')
g1 ('a')('b','c')('d')('e')
g2 ('a','b','e','d','c')

>>> from sage.all import *
>>> c = Constellation([(('a','b'),('c','d','e')),('b','d'), None])
>>> c.relabel()
Constellation of length 3 and degree 5
g0 ('a','b')('c','d','e')
g1 ('a')('b','c')('d')('e')
g2 ('a','b','e','d','c')
set_immutable()[source]

Do nothing, as self is already immutable.

EXAMPLES:

sage: c = Constellation(([0,2,1],[2,1,0],[1,2,0]), mutable=False)
sage: c.set_immutable()
sage: c.is_mutable()
False

>>> from sage.all import *
>>> c = Constellation(([Integer(0),Integer(2),Integer(1)],[Integer(2),Integer(1),Integer(0)],[Integer(1),Integer(2),Integer(0)]), mutable=False)
>>> c.set_immutable()
>>> c.is_mutable()
False
switch(i, j0, j1)[source]

Perform the multiplication by the transposition \((j0, j1)\) between the permutations \(g_i\) and \(g_{i+1}\).

The modification is local in the sense that it modifies \(g_i\) and \(g_{i+1}\) but does not modify the product \(g_i g_{i+1}\). The new constellation is

\[(g_0, \ldots, g_{i-1}, g_{i} (j0 j1), (j0 j1) g_{i+1}, g_{i+2}, \ldots, g_k)\]

EXAMPLES:

sage: c = Constellation(['(0,1)(2,3,4)','(1,4)',None], mutable=True); c
Constellation of length 3 and degree 5
g0 (0,1)(2,3,4)
g1 (0)(1,4)(2)(3)
g2 (0,1,3,2,4)
sage: c.is_mutable()
True
sage: c.switch(1,2,3); c
Constellation of length 3 and degree 5
g0 (0,1)(2,3,4)
g1 (0)(1,4)(2,3)
g2 (0,1,3,4)(2)
sage: c._check()
sage: c.switch(2,1,3); c
Constellation of length 3 and degree 5
g0 (0,1,4,2,3)
g1 (0)(1,4)(2,3)
g2 (0,3,4)(1)(2)
sage: c._check()
sage: c.switch(0,0,1); c
Constellation of length 3 and degree 5
g0 (0)(1,4,2,3)
g1 (0,4,1)(2,3)
g2 (0,3,4)(1)(2)
sage: c._check()

>>> from sage.all import *
>>> c = Constellation(['(0,1)(2,3,4)','(1,4)',None], mutable=True); c
Constellation of length 3 and degree 5
g0 (0,1)(2,3,4)
g1 (0)(1,4)(2)(3)
g2 (0,1,3,2,4)
>>> c.is_mutable()
True
>>> c.switch(Integer(1),Integer(2),Integer(3)); c
Constellation of length 3 and degree 5
g0 (0,1)(2,3,4)
g1 (0)(1,4)(2,3)
g2 (0,1,3,4)(2)
>>> c._check()
>>> c.switch(Integer(2),Integer(1),Integer(3)); c
Constellation of length 3 and degree 5
g0 (0,1,4,2,3)
g1 (0)(1,4)(2,3)
g2 (0,3,4)(1)(2)
>>> c._check()
>>> c.switch(Integer(0),Integer(0),Integer(1)); c
Constellation of length 3 and degree 5
g0 (0)(1,4,2,3)
g1 (0,4,1)(2,3)
g2 (0,3,4)(1)(2)
>>> c._check()
sage.combinat.constellation.Constellations(*data, **options)[source]

Build a set of constellations.

INPUT:

  • profile – an optional profile

  • length – an optional length

  • degree – an optional degree

  • connected – an optional boolean

EXAMPLES:

sage: Constellations(4,2)
Connected constellations of length 4 and degree 2 on {1, 2}

sage: Constellations([[3,2,1],[3,3],[3,3]])
Connected constellations with profile ([3, 2, 1], [3, 3], [3, 3]) on {1, 2, 3, 4, 5, 6}

>>> from sage.all import *
>>> Constellations(Integer(4),Integer(2))
Connected constellations of length 4 and degree 2 on {1, 2}

>>> Constellations([[Integer(3),Integer(2),Integer(1)],[Integer(3),Integer(3)],[Integer(3),Integer(3)]])
Connected constellations with profile ([3, 2, 1], [3, 3], [3, 3]) on {1, 2, 3, 4, 5, 6}
class sage.combinat.constellation.Constellations_ld(length, degree, sym=None, connected=True)[source]

Bases: UniqueRepresentation, Parent

Constellations of given length and degree.

EXAMPLES:

sage: C = Constellations(2,3); C
Connected constellations of length 2 and degree 3 on {1, 2, 3}
sage: C([[2,3,1],[3,1,2]])
Constellation of length 2 and degree 3
g0 (1,2,3)
g1 (1,3,2)
sage: C.cardinality()
2
sage: Constellations(2,3,connected=False).cardinality()
6

>>> from sage.all import *
>>> C = Constellations(Integer(2),Integer(3)); C
Connected constellations of length 2 and degree 3 on {1, 2, 3}
>>> C([[Integer(2),Integer(3),Integer(1)],[Integer(3),Integer(1),Integer(2)]])
Constellation of length 2 and degree 3
g0 (1,2,3)
g1 (1,3,2)
>>> C.cardinality()
2
>>> Constellations(Integer(2),Integer(3),connected=False).cardinality()
6
Element[source]

alias of Constellation_class

braid_group_action()[source]

Return a list of graphs that corresponds to the braid group action on self up to isomorphism.

OUTPUT: list of graphs

EXAMPLES:

sage: C = Constellations(3,3)
sage: C.braid_group_action()
[Looped multi-digraph on 3 vertices,
 Looped multi-digraph on 1 vertex,
 Looped multi-digraph on 3 vertices]

>>> from sage.all import *
>>> C = Constellations(Integer(3),Integer(3))
>>> C.braid_group_action()
[Looped multi-digraph on 3 vertices,
 Looped multi-digraph on 1 vertex,
 Looped multi-digraph on 3 vertices]
braid_group_orbits()[source]

Return the orbits under the action of braid group.

EXAMPLES:

sage: C = Constellations(3,3)
sage: O = C.braid_group_orbits()
sage: len(O)
3
sage: [x.profile() for x in O[0]]
[([1, 1, 1], [3], [3]), ([3], [1, 1, 1], [3]), ([3], [3], [1, 1, 1])]
sage: [x.profile() for x in O[1]]
[([3], [3], [3])]
sage: [x.profile() for x in O[2]]
[([2, 1], [2, 1], [3]), ([2, 1], [3], [2, 1]), ([3], [2, 1], [2, 1])]

>>> from sage.all import *
>>> C = Constellations(Integer(3),Integer(3))
>>> O = C.braid_group_orbits()
>>> len(O)
3
>>> [x.profile() for x in O[Integer(0)]]
[([1, 1, 1], [3], [3]), ([3], [1, 1, 1], [3]), ([3], [3], [1, 1, 1])]
>>> [x.profile() for x in O[Integer(1)]]
[([3], [3], [3])]
>>> [x.profile() for x in O[Integer(2)]]
[([2, 1], [2, 1], [3]), ([2, 1], [3], [2, 1]), ([3], [2, 1], [2, 1])]
is_empty()[source]

Return whether this set of constellations is empty.

EXAMPLES:

sage: Constellations(2, 3).is_empty()
False
sage: Constellations(1, 2).is_empty()
True
sage: Constellations(1, 2, connected=False).is_empty()
False

>>> from sage.all import *
>>> Constellations(Integer(2), Integer(3)).is_empty()
False
>>> Constellations(Integer(1), Integer(2)).is_empty()
True
>>> Constellations(Integer(1), Integer(2), connected=False).is_empty()
False
random_element(mutable=False)[source]

Return a random element.

This is found by trial and rejection, starting from a random list of permutations.

EXAMPLES:

sage: const = Constellations(3,3)
sage: const.random_element()
Constellation of length 3 and degree 3
...
...
...
sage: c = const.random_element()
sage: c.degree() == 3 and c.length() == 3
True

>>> from sage.all import *
>>> const = Constellations(Integer(3),Integer(3))
>>> const.random_element()
Constellation of length 3 and degree 3
...
...
...
>>> c = const.random_element()
>>> c.degree() == Integer(3) and c.length() == Integer(3)
True
class sage.combinat.constellation.Constellations_p(profile, domain=None, connected=True)[source]

Bases: UniqueRepresentation, Parent

Constellations with fixed profile.

EXAMPLES:

sage: C = Constellations([[3,1],[3,1],[2,2]]); C
Connected constellations with profile ([3, 1], [3, 1], [2, 2]) on {1, 2, 3, 4}
sage: C.cardinality()
24
sage: C.first()
Constellation of length 3 and degree 4
g0 (1)(2,3,4)
g1 (1,2,3)(4)
g2 (1,2)(3,4)
sage: C.last()
Constellation of length 3 and degree 4
g0 (1,4,3)(2)
g1 (1,4,2)(3)
g2 (1,2)(3,4)

>>> from sage.all import *
>>> C = Constellations([[Integer(3),Integer(1)],[Integer(3),Integer(1)],[Integer(2),Integer(2)]]); C
Connected constellations with profile ([3, 1], [3, 1], [2, 2]) on {1, 2, 3, 4}
>>> C.cardinality()
24
>>> C.first()
Constellation of length 3 and degree 4
g0 (1)(2,3,4)
g1 (1,2,3)(4)
g2 (1,2)(3,4)
>>> C.last()
Constellation of length 3 and degree 4
g0 (1,4,3)(2)
g1 (1,4,2)(3)
g2 (1,2)(3,4)

Note that the cardinality can also be computed using characters of the symmetric group (Frobenius formula):

sage: P = Partitions(4)
sage: p1 = Partition([3,1])
sage: p2 = Partition([3,1])
sage: p3 = Partition([2,2])
sage: i1 = P.cardinality() - P.rank(p1) - 1
sage: i2 = P.cardinality() - P.rank(p2) - 1
sage: i3 = P.cardinality() - P.rank(p3) - 1
sage: s = 0
sage: for c in SymmetricGroup(4).irreducible_characters():
....:     v = c.values()
....:     s += v[i1] * v[i2] * v[i3] / v[0]
sage: c1 = p1.conjugacy_class_size()
sage: c2 = p2.conjugacy_class_size()
sage: c3 = p3.conjugacy_class_size()
sage: c1 * c2 * c3 / factorial(4)**2 * s
1

>>> from sage.all import *
>>> P = Partitions(Integer(4))
>>> p1 = Partition([Integer(3),Integer(1)])
>>> p2 = Partition([Integer(3),Integer(1)])
>>> p3 = Partition([Integer(2),Integer(2)])
>>> i1 = P.cardinality() - P.rank(p1) - Integer(1)
>>> i2 = P.cardinality() - P.rank(p2) - Integer(1)
>>> i3 = P.cardinality() - P.rank(p3) - Integer(1)
>>> s = Integer(0)
>>> for c in SymmetricGroup(Integer(4)).irreducible_characters():
...     v = c.values()
...     s += v[i1] * v[i2] * v[i3] / v[Integer(0)]
>>> c1 = p1.conjugacy_class_size()
>>> c2 = p2.conjugacy_class_size()
>>> c3 = p3.conjugacy_class_size()
>>> c1 * c2 * c3 / factorial(Integer(4))**Integer(2) * s
1

The number obtained above is up to isomorphism. And we can check:

sage: len(C.isomorphism_representatives())
1

>>> from sage.all import *
>>> len(C.isomorphism_representatives())
1
isomorphism_representatives()[source]

Return a set of isomorphism representative of self.

EXAMPLES:

sage: C = Constellations([[5], [4,1], [3,2]])
sage: C.cardinality()
240
sage: ir = sorted(C.isomorphism_representatives())
sage: len(ir)
2
sage: ir[0]
Constellation of length 3 and degree 5
g0 (1,2,3,4,5)
g1 (1)(2,3,4,5)
g2 (1,5,3)(2,4)
sage: ir[1]
Constellation of length 3 and degree 5
g0 (1,2,3,4,5)
g1 (1)(2,5,3,4)
g2 (1,5)(2,3,4)

>>> from sage.all import *
>>> C = Constellations([[Integer(5)], [Integer(4),Integer(1)], [Integer(3),Integer(2)]])
>>> C.cardinality()
240
>>> ir = sorted(C.isomorphism_representatives())
>>> len(ir)
2
>>> ir[Integer(0)]
Constellation of length 3 and degree 5
g0 (1,2,3,4,5)
g1 (1)(2,3,4,5)
g2 (1,5,3)(2,4)
>>> ir[Integer(1)]
Constellation of length 3 and degree 5
g0 (1,2,3,4,5)
g1 (1)(2,5,3,4)
g2 (1,5)(2,3,4)
sage.combinat.constellation.perm_conjugate(p, s)[source]

Return the conjugate of the permutation \(p\) by the permutation \(s\).

INPUT:

  • p, s – two permutations of {0,..,n-1} given by lists of values

OUTPUT: a permutation of {0,..,n-1} given by a list of values

EXAMPLES:

sage: from sage.combinat.constellation import perm_conjugate
sage: perm_conjugate([3,1,2,0], [3,2,0,1])
[0, 3, 2, 1]

>>> from sage.all import *
>>> from sage.combinat.constellation import perm_conjugate
>>> perm_conjugate([Integer(3),Integer(1),Integer(2),Integer(0)], [Integer(3),Integer(2),Integer(0),Integer(1)])
[0, 3, 2, 1]
sage.combinat.constellation.perm_invert(p)[source]

Return the inverse of the permutation \(p\).

INPUT:

  • p – a permutation of {0,..,n-1} given by a list of values

OUTPUT: a permutation of {0,..,n-1} given by a list of values

EXAMPLES:

sage: from sage.combinat.constellation import perm_invert
sage: perm_invert([3,2,0,1])
[2, 3, 1, 0]

>>> from sage.all import *
>>> from sage.combinat.constellation import perm_invert
>>> perm_invert([Integer(3),Integer(2),Integer(0),Integer(1)])
[2, 3, 1, 0]
sage.combinat.constellation.perm_sym_domain(g)[source]

Return the domain of a single permutation (before initialization).

EXAMPLES:

sage: from sage.combinat.constellation import perm_sym_domain
sage: perm_sym_domain([1,2,3,4])
{1, 2, 3, 4}
sage: perm_sym_domain(((1,2),(0,4)))
{0, 1, 2, 4}
sage: sorted(perm_sym_domain('(1,2,0,5)'))
[0, 1, 2, 5]

>>> from sage.all import *
>>> from sage.combinat.constellation import perm_sym_domain
>>> perm_sym_domain([Integer(1),Integer(2),Integer(3),Integer(4)])
{1, 2, 3, 4}
>>> perm_sym_domain(((Integer(1),Integer(2)),(Integer(0),Integer(4))))
{0, 1, 2, 4}
>>> sorted(perm_sym_domain('(1,2,0,5)'))
[0, 1, 2, 5]
sage.combinat.constellation.perms_are_connected(g, n)[source]

Check that the action of the generated group is transitive.

INPUT:

  • g – list of permutations of \([0, n-1]\) (in a SymmetricGroup)

  • n – integer

EXAMPLES:

sage: from sage.combinat.constellation import perms_are_connected
sage: S = SymmetricGroup(range(3))
sage: perms_are_connected([S([0,1,2]),S([0,2,1])],3)
False
sage: perms_are_connected([S([0,1,2]),S([1,2,0])],3)
True

>>> from sage.all import *
>>> from sage.combinat.constellation import perms_are_connected
>>> S = SymmetricGroup(range(Integer(3)))
>>> perms_are_connected([S([Integer(0),Integer(1),Integer(2)]),S([Integer(0),Integer(2),Integer(1)])],Integer(3))
False
>>> perms_are_connected([S([Integer(0),Integer(1),Integer(2)]),S([Integer(1),Integer(2),Integer(0)])],Integer(3))
True
sage.combinat.constellation.perms_canonical_labels(p, e=None)[source]

Relabel a list with a common conjugation such that two conjugated lists are relabeled the same way.

INPUT:

  • p – list of at least 2 permutations

  • e – None or a list of integer in the domain of the permutations. If provided, then the renumbering algorithm is only performed from the elements of e.

OUTPUT: a pair made of a list of permutations (as a list of lists) and a list that corresponds to the conjugacy used.

EXAMPLES:

sage: from sage.combinat.constellation import perms_canonical_labels
sage: l0 = [[2,0,3,1], [3,1,2,0], [0,2,1,3]]
sage: l, m = perms_canonical_labels(l0); l
[[1, 2, 3, 0], [0, 3, 2, 1], [2, 1, 0, 3]]

sage: S = SymmetricGroup(range(4))
sage: [~S(m) * S(u) * S(m) for u in l0] == list(map(S, l))
True

sage: perms_canonical_labels([])
Traceback (most recent call last):
...
ValueError: input must have length >= 2

>>> from sage.all import *
>>> from sage.combinat.constellation import perms_canonical_labels
>>> l0 = [[Integer(2),Integer(0),Integer(3),Integer(1)], [Integer(3),Integer(1),Integer(2),Integer(0)], [Integer(0),Integer(2),Integer(1),Integer(3)]]
>>> l, m = perms_canonical_labels(l0); l
[[1, 2, 3, 0], [0, 3, 2, 1], [2, 1, 0, 3]]

>>> S = SymmetricGroup(range(Integer(4)))
>>> [~S(m) * S(u) * S(m) for u in l0] == list(map(S, l))
True

>>> perms_canonical_labels([])
Traceback (most recent call last):
...
ValueError: input must have length >= 2
sage.combinat.constellation.perms_canonical_labels_from(x, y, j0, verbose=False)[source]

Return canonical labels for x, y that starts at j0.

Warning

The group generated by x and the elements of y should be transitive.

INPUT:

  • x – list; a permutation of \([0, ..., n]\) as a list

  • y – list of permutations of \([0, ..., n]\) as a list of lists

  • j0 – an index in [0, …, n]

OUTPUT: mapping: a permutation that specify the new labels

EXAMPLES:

sage: from sage.combinat.constellation import perms_canonical_labels_from
sage: perms_canonical_labels_from([0,1,2],[[1,2,0]], 0)
[0, 1, 2]
sage: perms_canonical_labels_from([1,0,2], [[2,0,1]], 0)
[0, 1, 2]
sage: perms_canonical_labels_from([1,0,2], [[2,0,1]], 1)
[1, 0, 2]
sage: perms_canonical_labels_from([1,0,2], [[2,0,1]], 2)
[2, 1, 0]

>>> from sage.all import *
>>> from sage.combinat.constellation import perms_canonical_labels_from
>>> perms_canonical_labels_from([Integer(0),Integer(1),Integer(2)],[[Integer(1),Integer(2),Integer(0)]], Integer(0))
[0, 1, 2]
>>> perms_canonical_labels_from([Integer(1),Integer(0),Integer(2)], [[Integer(2),Integer(0),Integer(1)]], Integer(0))
[0, 1, 2]
>>> perms_canonical_labels_from([Integer(1),Integer(0),Integer(2)], [[Integer(2),Integer(0),Integer(1)]], Integer(1))
[1, 0, 2]
>>> perms_canonical_labels_from([Integer(1),Integer(0),Integer(2)], [[Integer(2),Integer(0),Integer(1)]], Integer(2))
[2, 1, 0]
sage.combinat.constellation.perms_sym_init(g, sym=None)[source]

Initialize a list of permutations (in the same symmetric group).

OUTPUT:

  • sym – a symmetric group

  • gg – list of permutations

EXAMPLES:

sage: from sage.combinat.constellation import perms_sym_init
sage: S, g = perms_sym_init([[0,2,1,3], [1,3,2,0]])
sage: S.domain()
{0, 1, 2, 3}
sage: g
[(1,2), (0,1,3)]

sage: S, g = perms_sym_init(['(2,1)', '(0,3)'])
sage: S.domain()
{0, 1, 2, 3}
sage: g
[(1,2), (0,3)]

sage: S, g = perms_sym_init([(1,0), (2,1)])
sage: S.domain()
{0, 1, 2}
sage: g
[(0,1), (1,2)]

sage: S, g = perms_sym_init([((1,0),(2,3)), '(0,1,4)'])
sage: S.domain()
{0, 1, 2, 3, 4}
sage: g
[(0,1)(2,3), (0,1,4)]

>>> from sage.all import *
>>> from sage.combinat.constellation import perms_sym_init
>>> S, g = perms_sym_init([[Integer(0),Integer(2),Integer(1),Integer(3)], [Integer(1),Integer(3),Integer(2),Integer(0)]])
>>> S.domain()
{0, 1, 2, 3}
>>> g
[(1,2), (0,1,3)]

>>> S, g = perms_sym_init(['(2,1)', '(0,3)'])
>>> S.domain()
{0, 1, 2, 3}
>>> g
[(1,2), (0,3)]

>>> S, g = perms_sym_init([(Integer(1),Integer(0)), (Integer(2),Integer(1))])
>>> S.domain()
{0, 1, 2}
>>> g
[(0,1), (1,2)]

>>> S, g = perms_sym_init([((Integer(1),Integer(0)),(Integer(2),Integer(3))), '(0,1,4)'])
>>> S.domain()
{0, 1, 2, 3, 4}
>>> g
[(0,1)(2,3), (0,1,4)]