School of Mathematical Sciences

Equitable partitions of Latin square graphs menu

Equitable partitions of Latin square graphs

Speaker: 
Peter Cameron (St Andrews)
Date/Time: 
Fri, 12/01/2018 - 16:00
Room: 
W316, Queen's Building
Seminar series: 

A partition of a graph $G$ is equitable if, for any two parts $P_i$ and $P_j$ (possibly equal) and $x\in P_i$, the number $p_{ij}$ of neighbours of $x$ in $P_j$ depends only on $i$ and $j$ and not on $x$. It is easy to show that the spectrum of the matrix $(p_{ij})$ is contained in the spectrum of the graph.

Given a Latin square $L$ of order $n$, the corresponding Latin square graph has as vertex set the set of cells of the square, with two vertices joined if they lie in the same row or column or contain the same letter. Its eigenvalues are $3(n-1)$, $n-3$ and $-3$. We conjecture, and have nearly proved, that in an equitable partition of a Latin square graph whose matrix does not have $-3$ as an eigenvalue, each part is a union of rows, or of columns, or of letters, or of subsquares of order $n/2$. I will also discuss some variants and generalisations.

This is joint work with Rosemary Bailey (QMUL/St Andrews) and Sergey Goryainov (Shanghai Jiao Tong University).