Group Actions

Undirected graphs as orbits

An undirected graph G on the vertex set V={1,2,..,n} is a set of $E \subseteq \binom{V}{2}$ of edges, where each edge is a subset of V of cardinality 2.

Then $S_n$ acts on V, and consequently on edges, and consequently on the set of graphs on V.

The orbits of the latter action is isomorphism classes of graphs. How many non-isomorphic graphs on 4 vertices are there? List them!

n=4
G = libgap.SymmetricGroup(n)
E = Subsets([1..n],2)
print(E)
GR = Subsets(E)
# print(GR)
GRE=[sorted(list([sorted(list(f)) for f in e])) for e in sorted(GR)]
# print(GRE)
print()
print()
graphsiso=G.Orbits(GRE,libgap.OnSetsSets)
for gr in graphsiso:
    print(len(gr[0]),len(gr))
    print('representant:',gr[0])
    print()

Subsets of {1, 2, 3, 4} of size 2


6 1
representant: [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ]

0 1
representant: [  ]

1 6
representant: [ [ 1, 2 ] ]

2 12
representant: [ [ 1, 2 ], [ 1, 3 ] ]

3 4
representant: [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ] ]

4 12
representant: [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ] ]

5 6
representant: [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ] ]

3 4
representant: [ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ]

3 12
representant: [ [ 1, 2 ], [ 1, 3 ], [ 2, 4 ] ]

4 3
representant: [ [ 1, 2 ], [ 1, 3 ], [ 2, 4 ], [ 3, 4 ] ]

2 3
representant: [ [ 1, 2 ], [ 3, 4 ] ]

Interpretation: on 4 vertices there are

1 graph with 0 edges
1 isoclass of graphs with 1 edges (6 isomorphic graphs)
2 isoclasses of graphs wtih 2 edges, representatives {{1,2},{1,3}} and {{1,2},{3,4}}
3 isoclasses of graphs with 3 edges,
2 isoclasses of graphs with 4 edges
1 isoclass of graphs with 5 edgeds
1 isoclass of graphs with 6 edges

Do this analysis for n=5, n=6

We can generalise from simple graphs, where "potential edges" are

colored black (included) or
colored white (not included)

to the case where each potential edge is given one of k colors. Permuting the vertices permutes these k-"colored edges". We set up a permutation subgroup of $S(N)$ with $N=\binom{n}{2}$ and look at the cycle type of these permutations. Here, we list the $N$ pairs ${i,j}$ in some order, so the induced permutation on pairs becomes a permutation on $1..N$ . This is purely for technical computer reasons.

a = lambda s,x: {s(x[0]),s(x[1])}
n = 4
                           
N = binomial(n,2)
SUBn = sorted(Subsets(n,2))
Sn = SymmetricGroup(n)

#for g in Sn:

Hn = PermutationGroup(
    [Permutation([SUBn.index(a(g,p))+1 for p in SUBn]) 
     for g in Sn])    
   
CycleIndexHn = Hn.cycle_index()    
print(CycleIndexHn)    
R=PolynomialRing(QQ,'x',N)

SS= sum([(i[1]*prod([R.gens()[j-1] for j in i[0]])) for i in CycleIndexHn])
print(SS)
R1.<k>= PolynomialRing(QQ)
f1 = R.hom([k for j in range(N)],R1)
GF1 = f1(SS)
print(GF1)
print(GF1(2))

1/24*p[1, 1, 1, 1, 1, 1] + 3/8*p[2, 2, 1, 1] + 1/3*p[3, 3] + 1/4*p[4, 2]
1/24*x0^6 + 3/8*x0^2*x1^2 + 1/3*x2^2 + 1/4*x1*x3
1/24*k^6 + 3/8*k^4 + 7/12*k^2
11

Necklaces

Find the number of different necklaces on n beads of k colors, for n=2,3,4,5,6 under

cyclic symmetry
dihedral symmetry

Also find the number of colorings using a beads of color one and b = n-a of color two

n=6
G = CyclicPermutationGroup(n)
N = G.order()
S = G.cycle_index()
print(S)
R=PolynomialRing(QQ,'x',n)
print(R)
SS= sum([(i[1]*prod([R.gens()[j-1] for j in i[0]])) for i in S])
print(SS)
R1.<k>= PolynomialRing(QQ)
f1 = R.hom([k for j in range(n)],R1)
GF1 = f1(SS)
print(GF1)

f2 = R.hom([(1 + k^(j+1)) for j in range(n)],R1)
GF2 = f2(SS)
print(GF2)

1/6*p[1, 1, 1, 1, 1, 1] + 1/6*p[2, 2, 2] + 1/3*p[3, 3] + 1/3*p[6]
Multivariate Polynomial Ring in x0, x1, x2, x3, x4, x5 over Rational Field
1/6*x0^6 + 1/6*x1^3 + 1/3*x2^2 + 1/3*x5
1/6*k^6 + 1/6*k^3 + 1/3*k^2 + 1/3*k
k^6 + k^5 + 3*k^4 + 4*k^3 + 3*k^2 + k + 1

Acting on triangles embedded in regular n-gon

Choose three of the vertices of a regular n-gon A rotation or reflection moves the points, and turns the tripple into another tripple Find the number of orbits under cyclic and dihedral symmetry for n=4,5,6,7,8 Describe the orbits

See https://en.wikipedia.org/wiki/Cycle_index#Example

n=6
GS = CyclicPermutationGroup(n)
G = GS.gap()
E = Subsets([1..n],3)
print(E)


GRE=[sorted(list(e)) for e in sorted(E)]
print(GRE)
print()
print()
triangles=G.Orbits(GRE,libgap.OnSets)
for gr in triangles:
    print(len(gr[0]),len(gr))
    print('representant:',gr[0])
    print()

Subsets of {1, 2, 3, 4, 5, 6, 7, 8} of size 3
[[6, 7, 8], [5, 7, 8], [5, 6, 8], [5, 6, 7], [4, 7, 8], [4, 6, 8], [4, 6, 7], [4, 5, 8], [4, 5, 7], [4, 5, 6], [3, 7, 8], [3, 6, 8], [3, 6, 7], [3, 5, 8], [3, 5, 7], [3, 5, 6], [3, 4, 8], [3, 4, 7], [3, 4, 6], [3, 4, 5], [2, 7, 8], [2, 6, 8], [2, 6, 7], [2, 5, 8], [2, 5, 7], [2, 5, 6], [2, 4, 8], [2, 4, 7], [2, 4, 6], [2, 4, 5], [2, 3, 8], [2, 3, 7], [2, 3, 6], [2, 3, 5], [2, 3, 4], [1, 7, 8], [1, 6, 8], [1, 6, 7], [1, 5, 8], [1, 5, 7], [1, 5, 6], [1, 4, 8], [1, 4, 7], [1, 4, 6], [1, 4, 5], [1, 3, 8], [1, 3, 7], [1, 3, 6], [1, 3, 5], [1, 3, 4], [1, 2, 8], [1, 2, 7], [1, 2, 6], [1, 2, 5], [1, 2, 4], [1, 2, 3]]


3 8
representant: [ 6, 7, 8 ]

3 8
representant: [ 1, 2, 4 ]

3 8
representant: [ 1, 2, 5 ]

3 8
representant: [ 1, 2, 6 ]

3 8
representant: [ 1, 2, 7 ]

3 8
representant: [ 1, 3, 5 ]

3 8
representant: [ 1, 3, 6 ]

n=6
GS = DihedralGroup(n)
G = GS.gap()
E = Subsets([1..n],3)
print(E)


GRE=[sorted(list(e)) for e in sorted(E)]
print(GRE)
print()
print()
triangles=G.Orbits(GRE,libgap.OnSets)
for gr in triangles:
    print(len(gr[0]),len(gr))
    print('representant:',gr[0])
    print()

Subsets of {1, 2, 3, 4, 5, 6} of size 3
[[4, 5, 6], [3, 5, 6], [3, 4, 6], [3, 4, 5], [2, 5, 6], [2, 4, 6], [2, 4, 5], [2, 3, 6], [2, 3, 5], [2, 3, 4], [1, 5, 6], [1, 4, 6], [1, 4, 5], [1, 3, 6], [1, 3, 5], [1, 3, 4], [1, 2, 6], [1, 2, 5], [1, 2, 4], [1, 2, 3]]


3 6
representant: [ 4, 5, 6 ]

3 12
representant: [ 1, 2, 4 ]

3 2
representant: [ 1, 3, 5 ]

Colorings of the cube

The (full) symmetry group of the cube acts faithfully on

the vertex set V={1,2,3,4,5,6,7,8}, V has 8 elements
the edge set $E \subset \binom{V}{2}$ of edges of the cube; E has 12 elements
the face set $F \subset \binom{V}{4}$ of faces of the cube; F has 6 elements

What symmetries stabilize a given vertex, a given edge, a given face?
What are the fixpoints of the group elements for the given actions?
Find the number of non-equivalent colorings using k colors for these 3 actions.
Also find the number of black-white colorings using r black and s white colors

# Action on vertices
antipod = Permutation([(1,7),(2,8),(3,5),(4,6)])
antipod
rot1 = Permutation([(1,4,8,5),(2,3,7,6)])
rot2 = Permutation([(1,2,3,4),(5,6,7,8)])

G=PermutationGroup([antipod,rot1,rot2])
G
G.order()

G.orbits()

[[1, 2, 4, 7, 3, 8, 6, 5]]

antipod.fixed_points()

[]

sorted(G.stabilizer(1))

[(), (3,6)(4,5), (2,4)(6,8), (2,4,5)(3,8,6), (2,5,4)(3,6,8), (2,5)(3,8)]

n=8
S = G.cycle_index()
print(S)
R=PolynomialRing(QQ,'x',n)
#print(R)
SS= sum([(i[1]*prod([R.gens()[j-1] for j in i[0]])) for i in S])
#print(SS)
R1.<k>= PolynomialRing(QQ)
f1 = R.hom([k for j in range(n)],R1)
GF1 = f1(SS)
#print(GF1)

f2 = R.hom([(1 + k^(j+1)) for j in range(n)],R1)
GF2 = f2(SS)
print(GF2)

1/48*p[1, 1, 1, 1, 1, 1, 1, 1] + 1/8*p[2, 2, 1, 1, 1, 1] + 13/48*p[2, 2, 2, 2] + 1/6*p[3, 3, 1, 1] + 1/4*p[4, 4] + 1/6*p[6, 2]
k^8 + k^7 + 3*k^6 + 3*k^5 + 6*k^4 + 3*k^3 + 3*k^2 + k + 1