CAYLEY GRAPHS AND APPLICATIONS OF POWER SUM SYMMETRIC FUNCTION

Abstract

We consider the Cayley graph on the symmetric group Sn generated by di fferent generating sets and we are interested in finding eigenvalues of the graph. With the eigenvalues, we are able to bound its largest independent set by using Delsarte-Ho man Bound. It is well known that the eigenvalues of this graph are indexed by partitions of n. We study the formula developed by Renteln and Ku and Wong to determine the eigenvalues of this graph. By investigating property of power sum symmetric function, we derive some new Cayley graphs and determine their eigenvalues so that we can bound the largest independent set. With manipulations of different choice of power sum symmetric function, we are able to produce new graphs and calculate their eigenvalues. We also look at some subgraphs of derangement graph and generalize properties in derangement graph into these subgraphs by analysis of order of eigenvalues.