Constellations#

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 ([LanZvo04] 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).

Note

The permutations are on [0, n-1] and not on [1, n] for algorithmic and practical reasons.

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellation, Constellations
sage: c = Constellation(['(0,1)', '(0,2)', None])
sage: c
Constellation of length 3 and degree 3
g0 (0,1)(2)
g1 (0,2)(1)
g2 (0,2,1)
sage: C = Constellations(3,4); C
Connected constellations of length 3 and degree 4
sage: C.cardinality()
426

surface_dynamics.misc.constellation.Constellation(g=None, mutable=False, connected=True, check=True)[source]#

INPUT:

g – a list of permutations
mutable – whether the result is mutable or not. Default is False.
connected – whether the result should be connected. Default is True.
check – whether or not to check. If it is True, then the list g must contains no None.

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellation

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)

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)

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)

class surface_dynamics.misc.constellation.Constellation_class(parent, g, check=True, connected=True, mutable=False)[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]#

Acts 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: from surface_dynamics.misc.constellation import Constellation

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)

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

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

braid_group_orbit()[source]#

Returns the graph of the action of the braid group.

The action is considered up to isomorphism of constellation.

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellation

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

connected_components()[source]#

Returns the connected components ?

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellation

sage: c = Constellation(['(0,1)(2)', None, '(0,1)(2)'], connected=False)
sage: c.connected_components()
[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: 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)]

copy()#

TESTS:

sage: from surface_dynamics import *
sage: c = Constellation([[0,2,1],[1,0,2],[2,1,0],None])
sage: c == copy(c)
True
sage: c is copy(c)
False
sage: c = Constellation([[0,2,1],[1,0,2],[2,1,0],None],mutable=True)
sage: c == copy(c)
True
sage: c is copy(c)
False

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: from surface_dynamics.misc.constellation import Constellation

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

euler_characteristic()[source]#

Return the Euler characteristic of the surface

ALGORITHM:

Hurwitz formula

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellation

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

g(i=None)[source]#

Return the permutation i of the constellation as a list

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellation

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

g_cycle_string(i, singletons=False)[source]#

Return the permutations of a constellation, as cycles

If i is None, return all of them

Otherwise, return just the permutation g_i as a cycle

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellation

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

g_cycle_tuples(i, singletons=False)[source]#

Return the tuples associated to the cycles of the permutations of self

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellation

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

g_next(i, j)[source]#

Return the image of j for the permutation g_i in constant time

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellation

sage: c = Constellation(['(1,2,0,5)','(2,3,4)(5,1)',None])
sage: c.g_next(0,0)
5
sage: all(c.g(i)[j] == c.g_next(i,j) for i in range(3) for j in range(6))
True

g_orbit(i, j)[source]#

Returns the orbit of j under g_i

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellation

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

g_prev(i, j)[source]#

Return the image of j for the permutation g_i in constant time

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellation

sage: c = Constellation(['(0,1,2)(3,4)','(0,4,2)',None])
sage: c.g_prev(0,0)
2
sage: all(c.g(i)[c.g_prev(i,j)] == j for i in range(3) for j in range(5))
True

genus()[source]#

Returns the genus of the surface

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellation
sage: c = Constellation(['(0,1)', '(0,2)', None])
sage: c.genus()
0

is_connected()[source]#

Test of connectedness

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellation

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

is_isomorphic(other, return_map=False)[source]#

Test of isomorphism

Returns True if the constellations are isomorphic (i.e. common conjugacy) and returns 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: from surface_dynamics.misc.constellation import Constellation

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

is_mutable()[source]#

Return False as self is immutable

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellation

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

length()[source]#

Number of permutations

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellation

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

mutable_copy()[source]#

Return a mutable copy of self

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellation

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

passport(i=None)#

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.

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellation

sage: c = Constellation(['(0,1,2)(3,4)','(0,3)',None])
sage: 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.

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellation

sage: c = Constellation(['(0,1,2)(3,4)','(0,3)',None])
sage: 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: from surface_dynamics.misc.constellation import Constellation

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)

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: d = c.relabel([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

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 = SymmetricGroup(c.degree()).random_element()
sage: cc = c.relabel([x-1 for x in p.domain()]).relabel()
sage: cc.is_isomorphic(c)
True

set_immutable()[source]#

Does nothing, as self is already immutable

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellation

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

switch(i, j0, j1)[source]#

Switch the vertices and edges at i and 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}.

j0 – g_i –> k0 – g_i0 –> l0

j1 – g_i+1 –> k1 – g_i+1 –> l1

becomes

j0 – g_i –> k1 – g_i –> l0

j1 – g_i+1 –> k1 – g_i+1 –> l1

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellation

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

surface_dynamics.misc.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: from surface_dynamics.misc.constellation import Constellation, Constellations

The set of all constellations:

sage: Constellations()
Connected constellations

Constellations with constrained length and degree:

sage: Constellations(4,2)
Connected constellations of length 4 and degree 2

class surface_dynamics.misc.constellation.Constellations_all(connected=True)[source]#

Bases: UniqueRepresentation, Parent

Element#: alias of Constellation_class

an_element()[source]#

Return a constellation.

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellations

sage: Constellations().an_element()
Constellation of length 2 and degree 2
g0 (0,1)
g1 (0,1)

class surface_dynamics.misc.constellation.Constellations_ld(length, degree, connected=True)[source]#

Bases: UniqueRepresentation, Parent

Constellations of given length and degree.

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellations

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

an_element()[source]#

Return a constellation in self.

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellations

sage: Constellations(2,3).an_element()
Constellation of length 2 and degree 3
g0 (0,2,1)
g1 (0,1,2)
sage: Constellations(7,3).an_element()
Constellation of length 7 and degree 3
g0 (0,2,1)
g1 (0,1,2)
g2 (0)(1)(2)
g3 (0)(1)(2)
g4 (0)(1)(2)
g5 (0)(1)(2)
g6 (0)(1)(2)

braid_group_action()[source]#

List of graphs that corresponds to the braid group action on self up to isomorphism.

OUTPUT:

list of graphs

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellations

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

braid_group_orbits()[source]#

Orbits under the action of braid group.

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellations

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]]
[([2, 1], [2, 1], [3]), ([2, 1], [3], [2, 1]), ([3], [2, 1], [2, 1])]
sage: [x.profile() for x in O[2]]
[([3], [3], [3])]

first()[source]#

Returns the first element in lexicographic order

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellations

sage: const = Constellations(3,3);const
Connected constellations of length 3 and degree 3
sage: const.first()
Constellation of length 3 and degree 3
g0 (0,1,2)
g1 (0,1,2)
g2 (0,1,2)

last()[source]#

Returns the last element in lexicographic order

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellations

sage: const=Constellations(3,3);const
Connected constellations of length 3 and degree 3
sage: const.last()
Constellation of length 3 and degree 3
g0 (0,2,1)
g1 (0,2,1)
g2 (0,2,1)

random_element(mutable=False)[source]#

a random element

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellations

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

class surface_dynamics.misc.constellation.Constellations_p(profile, connected=True)[source]#

Bases: UniqueRepresentation, Parent

Constellations with fixed profile.

EXAMPLES:

    sage: from surface_dynamics.misc.constellation import Constellations

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

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

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

sage: len(C.isomorphism_representatives())
1

braid_group_action()[source]#

List of graphs that corresponds to the braid group action on self up to isomorphism.

OUTPUT:

list of graphs

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellations

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

braid_group_orbits()[source]#

Orbits under the action of braid group.

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellations

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]]
[([2, 1], [2, 1], [3]), ([2, 1], [3], [2, 1]), ([3], [2, 1], [2, 1])]
sage: [x.profile() for x in O[2]]
[([3], [3], [3])]

isomorphism_representatives()[source]#

Return a set of isomorphism representative of self.

EXAMPLES:

sage: from surface_dynamics.misc.constellation import Constellations

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 (0,1,2,3,4)
g1 (0)(1,2,3,4)
g2 (0,4,2)(1,3)
sage: ir[1]
Constellation of length 3 and degree 5
g0 (0,1,2,3,4)
g1 (0)(1,4,2,3)
g2 (0,4)(1,2,3)