On the partition associated to the smallest eigenvalues of the k-point fixing graph

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 such that two vertices g, h of F(n,k) are joined if and only if gh−1 fixes exactly k points. In this paper, we show that for sufficiently large n in terms of k the smallest eigenvalue of F(n,k) occurs at the partition (n−t0,t0) where t0 is the smallest positive integer satisfying ∑r=0t0(kr)(−1)t0−r(t0−r)!<0. It was conjectured by Ellis in Ellis (2014) that if A is an independent set in F(n,k), then |A|≤(n−k−1)! for sufficiently large n. Our result implies that |A|≤Ok((n−k−12)!) for sufficiently large n.