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: Cayley graphs on the symmetric group generated by initial reversals have unit spectral gap. | Cayley graphs on the symmetric group generated by initial reversals have unit spectral gap Filippo Cesi Dipartimento di Fisica Universita di Roma La Sapienza Italy and SMC INFM-CNR. Submitted Apr 11 2009 Accepted Oct 1 2009 Published Oct 12 2009 Mathematics Subject Classification 05C25 05C50 Abstract In a recent paper Gunnells Scott and Walden have determined the complete spectrum of the Schreier graph on the symmetric group corresponding to the Young subgroup Sn 2 X S2 and generated by initial reversals. In particular they find that the first nonzero eigenvalue or spectral gap of the Laplacian is always 1 and report that empirical evidence suggests that this also holds for the corresponding Cayley graph. We provide a simple proof of this last assertion based on the decomposition of the Laplacian of Cayley graphs into a direct sum of irreducible representation matrices of the symmetric group. 1 Introduction If G is a finite group H is a subgroup of G and Z is a generating set of G we can construct the Schreier graph G X G H Z whose vertices are the left-cosets G H and whose edges are the pairs gH zgH with gH G G H and z G Z. We assume that the generating set Z is symmetric . z G Z if and only if z 1 G Z. In this case the graph X G H Z is undirected. If H 1 we denote with X G Z X G 1 Z the Cayley graph of G associated to the generating set Z. If Ag is the adjacency matrix of G and Ag the corresponding Laplacian since G is Z -regular counting loops we have Ag Z I - Ag where Z stands for the cardinality of the set Z. The Laplacian is symmetric and positive-semidefinite hence its eigenvalues are real and nonnegative and can be ordered as 0 A1 AG c A2 Ag c c An Ag THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 N29 1 Since Z generates G the graph G is connected which implies that 0 is a simple eigenvalue with constant eigenvector while A2 Aợ is strictly positive. The second eigenvalue of the Laplacian is also called the spectral gap of the
