Integral circulant Ramanujan graphs via multiplicativity and ultrafriable integers

Abstract Any integral circulant graph ICG ( n , D ) is characterised by its order n and a set D of positive divisors of n in such a way that it has vertex set Z / n Z and edge set { ( a , b ) : a , b ∈ Z / n Z , gcd ⁡ ( a − b , n ) ∈ D } . Such graphs are regular, and a connected ρ -regular graph G is called Ramanujan if the second largest modulus of the eigenvalues of the adjacency matrix of G is at most 2 ρ − 1 . In 2010 Droll described all Ramanujan unitary Cayley graphs, i.e. graphs of type X n : = ICG ( n , { 1 } ) having the Ramanujan property. Recently, Le and the author classified all Ramanujan graphs ICG ( p s , D ) for prime powers p s and arbitrary divisor sets D . We greatly extend the established results to graphs ICG ( n , D ) with arbitrary n and multiplicative divisor set D : (i) We derive a criterion (in terms of Euler's totient function) for ICG ( n , D ) to be Ramanujan. (ii) We prove that for all even integers n > 2 and a positive proportion of the odd integers n , namely those having a “dominating” prime power factor, there exists a multiplicative divisor set D such that ICG ( n , D ) is Ramanujan. (iii) We show that the set of odd n for which no Ramanujan graph ICG ( n , D ) with multiplicative divisor set D exists, viz. ultrafriable integers, has positive density as well. The proofs of (ii) and (iii) use methods from analytic number theory.