On the spectral Ádám property for circulant graphs (Q1613548)

This paper extends the class of graphs having the Ádám property and having the (even more general) spectral Ádám property. The methods employed in this paper are based on a combination of spectral techniques and deep results of algebraic number theory. A {circulant graph} \(G\) is a graph whose adjacency matrix \(A\) is a circulant, that is, the \(i\)th row of \(A\) is the cyclic shift of the first row by \(i-1\). If \(S\subseteq Z_n\) is the set of positions of nonzero entries of the first row of \(A\), then we write \(G=\langle S\rangle_n\). Two sets \(S\) and \(T\) are {proportional} if \(S=lT\) for some integer \(l\) where \(\gcd(n,l)=1\) and multiplication is taken over \(Z_n\). A set \(S\subseteq Z_n\) has the {Ádám property} if the isomorphism \(\langle S\rangle_n\simeq \langle T\rangle_n\) implies the proportionality \(S\sim T\). A more general form of the Ádám property is investigated in this paper. The spectrum \(\text{ Spec}\;G\) of a graph is the set of eigenvalues with multiplicities of its adjacency matrix. A set \(S\subseteq Z_n\) has the {spectral Ádám property} if the isospectrality \(\text{ Spec}\;\langle S\rangle_n=\text{ Spec}\;\langle T\rangle_n\) implies the proportionality \(S\sim T\). The authors show that any set \(S=\{\pm a,\pm b\}\subseteq Z_n\) with \(\gcd(a,b,n)=1\) satisfies the spectral Ádám property. It is also shown that for any fixed \(m\) the probability that a random \(m\)-element set \(S\subseteq Z_n\) does not have the spectral Ádám property is \(O(n^{-1})\).