3
$\begingroup$

I want the cycle index of the group of automorphisms of a (say 3 X 3) grid graph. I can produce the elements of the group with:

GroupElements[GraphData[{"Grid", {3, 3}}, "AutomorphismGroup"]]

This gives me: 

{Cycles[{}], Cycles[{{2, 4}, {3, 7}, {6, 8}}], 
 Cycles[{{1, 3}, {4, 6}, {7, 9}}], 
 Cycles[{{1, 3, 9, 7}, {2, 6, 8, 4}}], 
 Cycles[{{1, 7, 9, 3}, {2, 4, 8, 6}}], 
 Cycles[{{1, 7}, {2, 8}, {3, 9}}], Cycles[{{1, 9}, {2, 6}, {4, 8}}], 
 Cycles[{{1, 9}, {2, 8}, {3, 7}, {4, 6}}]}

What I want is something like: $1/8(s_1^9 + 4s_2^3 4s_1^3 + 2s_4^2 s_1 + s_2^4 s_1) $.

The problem seems to be that CycleIndex Needs["Combinatorica"]`.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ Take a look at CycleIndexPolynomial, which is a builtin. $\endgroup$ – Szabolcs Aug 9 '16 at 19:14
4
$\begingroup$

You can use CycleIndexPolynomial like so:

CycleIndexPolynomial[
 GraphAutomorphismGroup@GridGraph[{3, 3}],
 Array[Subscript[s, #] &, 4]
]

$$ \frac{s_1^9}{8}+\frac{1}{2} s_2^3 s_1^3+\frac{1}{8} s_2^4 s_1+\frac{1}{4} s_4^2 s_1 $$

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ OK Thank you. I will mention the following as a "possible issue" because it happened to me and caused much aggravation. It is sometimes necessary to specify the "domain of action" (see help section for CycleIndexPolynomial). For example: CycleIndexPolynomial[GraphData[{5, 32}, "AutomorphismGroup"], Table[Subscript[s, i], {i, 1, 8}]] does NOT return the correct polynomial. A 5 must be added as a third argument in CylceIndexPolynomial. $\endgroup$ – Geoffrey Critzer Aug 10 '16 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.