Open Collections

Distinguishing partitions and asymmetric uniform hypergraphs

Banff International Research Station for Mathematical Innovation and Discovery

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.

Mathematics; Combinatorics; Group theory and generalizations; Discrete mathematics

video/mp4

Author affiliation: Vanderbilt University

2019-03-20

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/68957

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/