= Equitable partition
An <equitable partition> of a finite <graph> groups vertices so that any two vertices in one cell have the same number of neighbours in each cell. For a <simple graph> with cells $C_1,\ldots,C_k$, this means that numbers
$$
b_{ij}=|N(v)\cap C_j|\qquad(v\in C_i)
$$
do not depend on which $v$ in $C_i$ is selected. Here $N(v)$ denotes the set of neighbours of $v$. These counts form the <equitable quotient matrix> $B=(b_{ij})$. An <equitable partition> need not be a <proper vertex colouring> and need not have cells of equal sizes.<Practical graph isomorphism, II by Brendan D. McKay and Adolfo Piperno>[Section3.1 and footnote1, equitable-partition terminology]{ref}
An original five-vertex <path graph> $1-2-3-4-5$ has an <equitable partition>
$$
C_1=\{1,5\},\qquad C_2=\{2,4\},\qquad C_3=\{3\},\qquad
B=\begin{pmatrix}0&1&0\\1&0&1\\0&2&0\end{pmatrix}.
$$
Each endpoint has one neighbour in $C_2$; each member of $C_2$ has one neighbour in $C_1$ and one in $C_3$; the middle vertex has two neighbours in $C_2$. Although the graph is undirected, $B$ is not <symmetric matrix>, because its entries count neighbours per vertex rather than total edges between cells. Counting those edges from both ends gives $|C_i|b_{ij}=|C_j|b_{ji}$.
The counts also compress an exact part of the <adjacency matrix>. Let $A$ be that <matrix> and let $S$ have one column per cell, with $S_{vi}=1$ for $v\in C_i$ and zero otherwise. Then
$$
AS=SB.
$$
Indeed, $(AS)_{vj}$ counts neighbours of $v$ in $C_j$, which is exactly $(SB)_{vj}$. Hence $Bz=\lambda z$ implies $A(Sz)=\lambda(Sz)$. Since nonempty disjoint cells make the columns of $S$ <linearly independent>, $z\ne0$ gives $Sz\ne0$: every <eigenvalue> of $B$ is an <eigenvalue> of $A$. For the displayed example, these include $0$ and $\pm\sqrt3$.
An <equitable partition> preserves neighbour counts, not all adjacency information. The <disjoint union of graphs> of a triangle and a four-vertex cycle has an equitable one-cell partition, since every vertex has two neighbours. Nevertheless, no <graph automorphism> can send a triangle vertex to a four-cycle vertex: their <connected components of a graph> are not isomorphic. This distinguishes equitable cells from symmetry orbits and explains why <colour refinement> may leave ambiguity.
Back to article page
