TY - ELEC
AU - Ellingham, Mark
PY - 2018
TI - Distinguishing partitions and asymmetric uniform hypergraphs
LA - eng
M3 - Moving Image
AB - 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.
N2 - 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.
UR - https://open.library.ubc.ca/collections/48630/items/1.0377187
ER - End of Reference