BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Distinguishing partitions and asymmetric uniform hypergraphs Ellingham, Mark


In 2011 Ellingham and Schroeder introduced the idea of a "distinguishing partition" for an action of a group $\Gamma$ on a set $X$, namely a partition of $X$ that is preserved by no nontrivial element of $\Gamma$. As a special case, a distinguishing partition of a graph is a partition of the vertex set that is preserved by no nontrivial automorphism. Distinguishing partitions are weaker at breaking symmetry than distinguishing colourings, and not every graph has a distinguishing partition. We discuss our work with Schroeder which linked distinguishing partitions of complete equipartite graphs with asymmetric uniform hypergraphs. We find a function $f(n)$ such that a distinguishing partition for $K_{m(n)}=K_{n,n,\ldots,n}$, or equivalently for the wreath product action $S_n \wr S_m$, exists if and only if $m\geq f(n)$. We also discuss some other work on distinguishing partitions of complete multipartite graphs by Michael Goff.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International