On eigenvalues of certain cayley graphs / Terry Lau Shue Chien

Terry, Lau Shue Chien (2016) On eigenvalues of certain cayley graphs / Terry Lau Shue Chien. PhD thesis, University of Malaya.

Preview

PDF (Thesis PhD) Download (1179Kb) | Preview

Abstract

Let Sn be the symmetric group on [n] = {1,. . . ,n}. The k-point fixing graph, F(n, k) is defined to be the graph with vertex set Sn and two vertices g and h of F(n, k) are joined if and only if gh−1 fixes exactly k points. F(n, k) is a Cayley graph on Sn generated by S (n, k), the union of the conjugacy classes that fixes exactly k points. A subset I of Sn is said to be an independent set in F(n, k) if and only if any two vertices in I are not adjacent to each other. The problem of finding such a set is called the maximum independent set problem and it is an NP-hard optimization problem. We are going to determine the size of the largest independent set in F(n, k) for 0 < k << n by using the Delsarte-Hoffman Bound. In order to do so, eigenvalues of the adjacency matrix of F(n, k) are required in finding a bound for the size of a largest independent set in F(n, k). To determine the eigenvalues of the adjacency matrix of F(n, k), we use the representation theory of symmetric groups. In particular, we use the character theory of symmetric groups. We apply the branching rule and results from Foulkes to derive a recurrence formula for eigenvalues of F(n, k). Then we apply our results and some of the results regarding the eigenvalues and size of largest independent set of F(n,0) to determine the sign of the eigenvalues of F(n,1). Then, we determine the smallest eigenvalue of F(n,1) by techniques in extremal combinatorics. We use the largest and smallest eigenvalues of F(n,1) and apply the Delsarte-Hoffman Bound to determine a bound for the size of a largest independent set in F(n,1). When 0 < k << n, we determine the smallest eigenvalues of F(n, k) and the Specht module where it occurs. Similarly, we use the largest and smallest eigenvalues of F(n, k) and apply the Delsarte-Hoffman Bound to determine a bound for the size of a largest independent set in F(n, k). We also consider F(n,0), the derangement graph with generating set Dn, the derangement set. For any fixed positive integer k ≤ n, the Cayley graph on Sn generated by the subset of Dn consisting of permutations without any i-cycles for all 1 ≤ i ≤ k is a regular subgraph of the derangement graph. We determine the smallest eigenvalue of these subgraphs and show that the set of all largest independent sets in these subgraphs is equal to the set of all the largest independent sets in F(n,0) provided that k << n. h

Actions (For repository staff only : Login required)