From finite topologies and lattices to the automorphism groups of rational Schur rings
by
Mikhail Klin
Ben-Gurion University of the Negev, Beer Sheva, Israel
Coauthors: Istvan Kovacs

A Cayley graph G over cyclic group Z_n of order n is called a circulant graph. Graph G is called rational if the spectrum of its adjacency matrix consists only of rational (in fact integer) numbers. The main motivation of this presentation stems from our interest to establish efficient procedure to determine automorphism group of a rational circulant graph.

We employ methodology of Schur rings (briefly, S-rings), see [3].

Problem of classification of rational S-rings (S-rings of traces in original Schur-Wielandt's terminology) goes back to the seminal paper of Schur (1933). Various particular cases were considered a few decades ago by Ya. Yu. Gol'fand, Klin and R. Pöschel. In particular, for the case when n is a product of k distinct primes, Gol'fand (1985) established a bijection between rational S-rings over Z_n and finite topologies on the set of cardinality k.

An elegant description of all rational S-rings over Z_n was provided by Muzychuk [2] in terms of sublattices of the lattice of all natural divisors of n.

Another origin of our approach stems to the operation of crested product of association schemes [1]. Note that similar concepts for the particular case of S-rings over cyclic groups were suggested by K. H. Leung and S. C. Ma, S. Evdokimov and I. N. Ponomarenko. A more general operation of wedge product of association schemes is treated by Muzychuk.

Merging ideas of our predecessors, we consider simple reduction rules which allow for a given rational S-ring S over Z_n to describe its automorphism group Aut(G). Special attention is paid to those particular cases when Aut(G) appears via iterative use of wreath products and direct products of symmetric groups. For a rational circulant graph G we determine such S-ring S that Aut(G)=Aut(S).

Note that it follows from our results that all rational S-rings over Z_n are Schurian.

This expository talk is based on the cooperation of the authors with O.H. Kegel and M. Muzychuk.

References

[1] Bailey, R. A.; Cameron, Peter J. Crested products of association schemes. J. London Math. Soc. (2) 72 (2005), no. 1, 1-24. [2] Muzychuk, Mikhail E. The structure of rational Schur rings over cyclic groups. European J. Combin. 14 (1993), no. 5, 479-490. [3] Muzychuk, Mikhail; Klin, Mikhail; Pöschel, Reinhard. The isomorphism problem for circulant graphs via Schur ring theory. Codes and association schemes (Piscataway, NJ, 1999), 241-264, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 56, Amer. Math. Soc., Providence, RI, 2001.

PDF

Date received: June 10, 2008