Integral circulant Ramanujan graphs via multiplicativity and ultrafriable integers

Any integral circulant graph  ICG(n,D)ICG(n,D) is characterised by its order n   and a set DD of positive divisors of n   in such a way that it has vertex set Z/nZZ/nZ and edge set {(a,b):a,b∈Z/nZ,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 Xn:=ICG(n,{1})Xn:=ICG(n,{1}) having the Ramanujan property. Recently, Le and the author classified all Ramanujan graphs ICG(ps,D)ICG(ps,D) for prime powers psps and arbitrary divisor sets DD. We greatly extend the established results to graphs ICG(n,D)ICG(n,D) with arbitrary n   and multiplicative divisor set DD: (i) We derive a criterion (in terms of Euler's totient function) for ICG(n,D)ICG(n,D) to be Ramanujan. (ii) We prove that for all even integers n>2n>2 and a positive proportion of the odd integers n  , namely those having a “dominating” prime power factor, there exists a multiplicative divisor set DD such that ICG(n,D)ICG(n,D) is Ramanujan. (iii) We show that the set of odd n   for which no Ramanujan graph ICG(n,D)ICG(n,D) with multiplicative divisor set DD exists, viz. ultrafriable integers, has positive density as well. The proofs of (ii) and (iii) use methods from analytic number theory.