Square-free non-Cayley numbers. On vertex-transitive non-Cayley graphs of square-free order. (Q1766111)

A (finite) graph \(\Gamma\) is vertex-transitive if its automorphism group \(\Aut(\Gamma)\) acts transitively on the vertex set \(V(\Gamma)\); it is a Cayley graph if \(\Aut(\Gamma)\) contains a regular subgroup. The smallest vertex-transitive graph which is not a Cayley graph is the Petersen graph with \(10\) vertices. An integer \(n\) is called a non-Cayley number if there is a vertex-transitive graph which is not Cayley (written \(n\in\mathcal{NC}\)). This class of integers was first studied by \textit{D. Marušič} [Ars Comb. 16-B, 297-302 (1983; Zbl 0535.05034)] and since then a considerable amount has been learned of these numbers. For example, each integer in \(\mathcal{NC}\) is either square-free, equal to \(12\), or has the form \(p^2\) or \(p^3\) (\(p\) prime) [see \textit{B. McKay} and \textit{C. E. Praeger}, J. Graph Theory 22, No. 4, 321-334 (1996; Zbl 0864.05041)]. A series of authors have determined the integers in \(\mathcal{NC}\) which are a product of at most three distinct primes [see \textit{Á. Seress}, Discrete Math. 182, No. 1-3, 279-292 (1998; Zbl 0908.05050)]. In the present paper the authors determine the square-free integers \(n\in\mathcal{NC}\) for which there is a graph \(\Gamma\) with \(n\) vertices such that \(\Aut(\Gamma)\) is `primitive' on \(V(\Gamma)\) but \(\Gamma\) is not Cayley. These integers fall into seven (presumably) infinite classes and 16 exceptional degrees. The proof is based on the authors' earlier classification of primitive permutation groups of square-free degree [\textit{C. H. Li} and \textit{Á. Seress}, Bull. Lond. Math. Soc. 35, No. 5, 635-644 (2003; Zbl 1043.20001)] together with a description (in the present paper) of the primitive permutation groups of square-free degree which contain a regular subgroup. The main theorems imply the following corollaries: (1) all vertex-primitive Cayley graphs of square-free order are known; and (2) a group \(R\) of composite square-free order is not a \(B\)-group (Burnside group) if and only if \(R\cong\mathbb{Z}_{29}.\mathbb{Z}_7\), \(\mathbb{Z}_{31}.\mathbb{Z}_5\) or \(\mathbb{Z}_p.\mathbb{Z}_{(p-1)/2}\) for some prime \(p\equiv 3\bmod 4\).