Diagonal structures and beyond

The Hamming graph $H(n,m)$ has vertex set $A^n$, where $A$ is a set of size $m$; two vertices are joined if they differ in exactly one coordinate.
In the case $m=2$, we get another interesting graph, the folded cube, by adding to the Hamming graph (the cube) the edges which join antipodal vertices, those differing in all coordinates. For $n=4$, this gives the Clebsch graph.
I will give a generalization of the folded cube for the case $m>2$.
$A^n$ has a natural Cartesian decomposition, with a corresponding lattice of partitions corresponding to the equivalence relations $\equiv_J$, for $J\subseteq\{1,\ldots,n\}$, where $v\equiv_Jw$ if $v$ and $w$ agree in all coordinates outside $J$. So then $v$ and $w$ are adjacent in $H(n,m)$ if and only if $v\equiv_{\{j\}}w$ for some index $j$. In joint work with Cameron, Praeger and Schneider [3], we showed that, for $n\geqslant 2$, if a set of $n+1$ partitions of a set $\Omega$ has the property that any $n$ of them are the minimal elements in an $n$-dimensional Cartesian lattice, then either

\itemsep0pt
• (a) $n=2$, and the partitions are the rows, columns and letters of a Latin square; or
• (b) there is a group $G$ of order $m$, unique up to isomorphism, such that $\Omega=G^n$, and the partitions are the coset partitions of the $n$ coordinate subgroups $G_1,\ldots,G_m$ and the diagonal subgroup $\delta(G)$.

In case (b), the automorphism groups of the structures generalize the diagonal groups occurring in the O'Nan–Scott Theorem.
In subsequent work, Cameron and I [1] considered a graph on $G^m$, called the diagonal graph, which generalises the folded cube. Two vertices are joined whenever they are in the same part of one of the minimal partitions. (In the case $n=2$, this is the Latin square graph associated with the Latin square.) To find the spectrum of this graph, we use the partial order on the join-semilattice generated by the partitions, and in particular its Möbius function.
Also, with Cameron, Kinyon and Praeger [2], I have begun investigating the situation when there are $n+r$ partitions, any $n$ of which are the minimal elements of an $n$-dimensional Cartesian lattice, with $r>1$.

Список литературы

1. R. A. Bailey and P. J. Cameron, The diagonal graph, arXiv: 2101.02451
2. P. J. Cameron, M.l Kinyon, C. E. Praeger, Diagonal groups and arcs over groups, arXiv: 2010.16338
3. P. J. Cameron, C. E. Praeger, C. Schneider, The geometry of diagonal groups, arXiv: 2007.10726