Distinguishing partitions and asymmetric uniform hypergraphs

english

2011

volume 4, issue 1

asymmetric uniform hypergraph   complete equipartite graph   distinguishing number   distinguishing partition   graph theory

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

A distinguishing partition for an action of a group ?$\Gamma$? on a set ?$X$? is 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. In this paper we provide a link between distinguishing partitions of complete equipartite graphs and asymmetric uniform hypergraphs. Suppose that ?$m \geq 1$? and ?$n \geq 2$?. We show that an asymmetric ?$n$?-uniform hypergraph with ?$m$? edges exists if and only if ?$m \geq f(n)$?, where ?$f(2) = f(14) = 6, f(6) = 5$?, and ?$f(n) = \lfloor \log_2 (n + 1) + 2 \rfloor$? otherwise. It follows that a distinguishing partition of ?$K_{m(n)} = K_{n,n, \dots ,n}$?, or equivalently for the wreath product action ?$S_n$? Wr ?$S_m$?, exists if and only if ?$m \geq f(n)$?.

16.12.2021