Distinguishing partitions of complete multipartite graphs - Goff, Michael (Ars mathematica contemporanea, 2016)
A distinguishing partition of a set ?$X$? with automorphism group ?$\text{aut}(X)$? is a partition of ?$X$? that is fixed by no nontrivial element of ?$\text{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 ?$m_1$? parts of size ?$n_1$? and ?$m_2$? parts of size ?$n_2$? for small ?$n_1$?, ?$m_2$? and large ?$m_1$?, ?$n_2$?. A key tool in making the estimate is counting the number of trees of particular classes.
Keywords: combinatorial species; complete multipartite graph; distinguishing partition; kombinatorične vrste; polni multipartitni graf; preštevanje dreves; razlikovalna particija; tree enumeration