Distinguishing partitions of complete multipartite graphs
Michael Goff · Ars Mathematica Contemporanea · 2015
A distinguishing partition of a set X with automorphism group aut(X) is a partition of X that is fixed by no nontrivial element of aut(X). In the event that X is a complete multipartite graph with its automorphism group, the existence of a distinguishing partition is equivalent to the existence of an asymmetric hypergraph with prescribed edge sizes. An asymptotic result is proven on the existence of a distinguishing partition when X is a complete multipartite graph with m1 parts of size n1 and m2 parts of size n2 for small n1, m2 and large m1, n2. A key tool in making the estimate is counting the number of trees of particular classes.