Journal of the Ramanujan Mathematical Society
Volume 36, Issue 4, December 2021 pp. 353–361.
The diagonal graph
Authors:
R. A. Bailey and Peter J. Cameron
Author institution:School of Mathematics and Statistics,
University of St Andrews, North Haugh, St Andrews, Fife, KY16 9SS, U.K.
Summary:
According to the O'Nan--Scott Theorem, a finite primitive
permutation group either preserves a structure of one of three
types (affine space, Cartesian lattice, or diagonal semilattice),
or is almost simple. However, diagonal groups are a much larger
class than those occurring in this theorem. For any positive
integer m and group G (finite or infinite), there is a
diagonal semilattice, a sub-semilattice of the lattice of
partitions of a set Ω, whose automorphism group is the
corresponding diagonal group. Moreover, there is a graph (the
diagonal graph), bearing much the same relation to the diagonal
semilattice and group as the Hamming graph does to the Cartesian
lattice and the wreath product of symmetric groups.
Our purpose here, after a brief introduction to this semilattice
and graph, is to establish some properties of this graph.
The~diagonal graph Γ{D(G,m)} is a Cayley graph for the
group~G{m}, and so is vertex-transitive. We establish its clique
number in general and its chromatic number in most cases, with a
conjecture about the chromatic number in the remaining cases. We
compute the spectrum of the adjacency matrix of the graph, using a
calculation of the Möbius function of the diagonal semilattice.
We also compute some other graph parameters and symmetry
properties of the graph.
We believe that this family of graphs will play a significant role in
algebraic graph theory.
Contents
Full-Text PDF