From CanisiusmathWiki

Table of contents

1 Three ways of generating S4 2 Other pages on Cayley graphs of symmetric groups 3 Some permutation groups discussion 4 Mathematica program to find the group of permutations generated by two given permutations 5 Pages on undirected cycles and Chebyshev polynomials 6 A Page with an application of interlacing 7 Pages on cyclic groups 1 Delaunay and edge flips

Three ways of generating S4

A wiki page here with three ways of generating S4, and their Cayley graphs: Characteristic Polynomials of Cayley Graphs of the Symmetric Group

Other pages on Cayley graphs of symmetric groups

from Main page, subsection Summer 2006, find page Cayley graphs and coverings, find page Action graphs for symmetries of the cube.

from Main page, subsection Summer 2007, find page New coverings from groups, find page Action Graph or Modified Cayley Graph.

from Main page, subsection Summer 2007, find page New coverings from groups, find page Cayley Graphs, Tietze Moves, and Coverings.

Some permutation groups discussion

Here is a link [1] (http://goodmath.blogspot.com/2006/04/permutations-and-symmetry-groups.html)

Mathematica program to find the group of permutations generated by two given permutations

• To run the program, assign a value to n, for the permutation group on n things. Then assign to cayley the list of two permutations, in standard permutation form. The output will be the number of permutations generated by these two permutations. So the output will be n! if and only if you have generated the entire permutation group.

n = 3; cayley = {{2, 1, 3}, {2, 3, 1}}; PermutationMatrix[p_List] := IdentityMatrix[Length[p]][[p]]; Permutes[a_List, b_List] := Union[Flatten[ Table[{a[[aa]], a[[aa]].PermutationMatrix[b[[bb]]]}, {aa, 1, Length[a]}, {bb, 1, Length[b]}], 1]]; CayleyGraph[aa_List] := Union[Sort /@ Last[FixedPointList[ Union[Flatten[{#, Flatten[Last /@ Permutes[{#}, aa], 1]}, 1]] &, Permutes[{Range[Length[First[aa]]]}, aa]]]]; nodes = Split[ Sort[Flatten[ Map[{TraditionalForm[{Range[n], #[[1]]}], TraditionalForm[{Range[n], #[[2]]}]} &, CayleyGraph[cayley]]]]]; Length[nodes]

Pages on undirected cycles and Chebyshev polynomials

• Eigenvalues of the Laplacians of Cycles by David 2005
• Data_on_Characteristic_Polynomials_of_Cycles by emily 2008
• Characteristic Polynomials of Adjacency Matrices of Families of Graphs by emily, gabriella, brian and rachel 2008
• Covers, Laplacians, and Growth on Graphs Tricia and Jack 2005, with abstract of their talk and links to lots of other pages, including
  • Determinant of Laplacian via Chebyshev and
  • Covers and Eigenvalues and
  • Cyclic vs Dihedral Groups.

Chebyshev polynomials of the first kind are implemented in Mathematica as "ChebyshevT[n, x]". See http://mathworld.wolfram.com/ChebyshevPolynomialoftheFirstKind.html

• 
• 
• 
• 
• 
• 
• .

The are expressed by interesting determinants like the following:

The Chebyshev polynomials of the first kind satisfy a recurrence relation

Chebyshev polynomials of the second kind are implemented in Mathematica as "ChebyshevU[n, x]". See http://mathworld.wolfram.com/ChebyshevPolynomialoftheSecondKind.html

• 

• 

• 

• 

• 

• 

• 

The Chebyshev polynomials of the second kind satisfy the same recurrence relations as above:

The are expressed by interesting determinants like the following:

Characteristic polynomials of undirected cycles obey a recurrence, like .

• Note to Nathan:

A Page with an application of interlacing

• Interlacing and hamiltonian circuits

Pages on cyclic groups

• Cyclic Cayley Graphs (Spencer 2010)

• Cyclic vs Dihedral Groups (Meager 2005 and Leary 2008)

• Theorems about Cayley graphs and coverings (Lazenby, Cooper, and Davis 2006) has some info about multiplication of cyclic graphs

• Multiplying Cayley graphs of cyclic groups (Lazenby 2006)

• Spectrum of Cayley graphs of cyclic groups (Lazenby 2006)

• Proof of Theorem for cospectral graphs with alphabet of size two (Lazenby 2006)

• Cayley graphs of finite abelian groups (by Julia Lazenby 2006) abstract for talk at the Ohio State University Young Mathematicians Conference

• Skew product as the tensor product when G is cyclic (Johnston 2009)

• A Reference to Some Common Binary Operations on Graphs (Johnston 2009)

• Cayley Graphs of Semidirect Product Groups (Reynolds 2009)

• Latin square graphs and groups (Cooley 2007)

• Cayley Latin square graphs (Cooley 2007)

• Groupoids and Graphs (Leary 2008)

• Harmonic Maps on Cayley Graphs, Homomorphisms, and Groups (Abramovich 2009)

• Hamiltonian Paths in Cayley Digraphs (Reynolds 2009)

• Automata that Generate Triangular, Square, and Hexagonal Lattices (Gauthier 2009)

• Cocycles (Jannson 2009)

Delaunay and edge flips

A Delaunay triangulation (invented by Boris Delaunay in 1934) for a set P of points in the plane is a triangulation such that no point in P is inside the circumcircle of any of the triangles (other points only on the circumference). For a set of points on the same line there is no Delaunay triangulation. For four points on the same circle (e.g., the vertices of a rectangle) the Delaunay triangulation is not unique.

For two triangles ABD and BCD, if the sum of the angles at B and D is less than or equal to 180°, the triangles meet the Delaunay condition. This suggests flipping: if two triangles do not meet the Delaunay condition, switching the common edge BD for the common edge AC produces two triangles that do meet the Delaunay condition. So, start with any triangulation of the points, and then flip edges until no triangle is non-Delaunay. Unfortunately, this can take lots of edge flips.