tailieunhanh - Báo cáo tin học: "On the Spectrum of the Derangement Graph"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: On the Spectrum of the Derangement Graph. | On the Spectrum of the Derangement Graph Paul Renteln Department of Physics California State University San Bernardino CA 92407 and Department of Mathematics California Institute of Technology Pasadena CA 91125 prenteln@ Submitted Apr 10 2007 Accepted Nov 1 2007 Published Nov 28 2007 Mathematics Subject Classifications 05C25 05C50 05E05 05E10 Abstract We derive several interesting formulae for the eigenvalues of the derangement graph and use them to settle affirmatively a conjecture of Ku regarding the least eigenvalue. Keywords Cayley Graph Least Eigenvalue Derangement Graph Symmetric Group Symmetric Function Theory Complete Symmetric Factorial Functions Shifted Schur Functions 1 Introduction Let G be a finite group and S c G a symmetric subset of generators s 2 S s-1 2 S satisfying 12 S. The Cayley graph r G S has the elements of G as its vertices and two elements U v 2 G are joined by an edge provided vu-1 s for some s 2 S. 1 It is clear that r G S is regular of vertex degree S . Let Sn be the symmetric group of permutations of X 1 2 . ng and let Dn ơ 2 Sn ơ x X 8x 2 Xg denote I would like to thank Cheng Ku for bringing his conjecture to my attention and for many stimulating discussions David Wales for pointing out a discrepancy in an earlier draft Rick Wilson and the mathematics department of the California Institute of Technology for their kind hospitality and the referee for suggesting several improvements in the exposition. The condition 12 S precludes loops while the symmetry condition allows us to consider the graph as being undirected. THE ELECTRONIC JOURNAL OF COMBINATORICS 14 2007 R82 1 the derangements on X namely the set of fixed point free permutations of Sn. Note that Dn is symmetric in the above sense as the inverse of a derangement is a derangement. We call rn r Sn Dn the derangement graph on X. Much is known about this graph rn is connected n 3 . This follows because every permutation can be written as the product of adjacent .