416 KB62 KB200820252016Goff, Michaelštevilka:1letnik:10str. 45-66COBISSID:17732953ISSN:1855-3966URN:URN:NBN:SI:doc-BC8FDUQAenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneacombinatorial speciescomplete multipartite graphdistinguishing partitionkombinatorične vrstepolni multipartitni grafpreštevanje drevesrazlikovalna particijatree enumerationDistinguishing partitions of complete multipartite graphs|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 classesRazlikovalna particija množice ?$X$? z grupo avtomorfizmov ?$\text{aut}(X)$? je particija množice ?$X$?, ki je ne ohranja noben netrivialen element ?$\text{aut}(X)$?. V primeru, ko je ?$X$? polni multipartitni graf, ?$\text{aut}(X)$? pa grupa vseh njegovih avtomorfizmov, je obstoj razlikovalne particije ekvivalenten obstoju asimetričnega hipergrafa s predpisanimi velikostmi povezav. Dokažemo asimptotski rezultat o obstoju razlikovalne particije, ko je ?$X$? polni multipartitni graf z ?$m_1$? deli velikosti ?$n_1$? in ?$m_2$? deli velikosti ?$n_2$? za majhne ?$n_1$?, ?$m_2$? in velike ?$m_1$?, ?$n_2$?. Ključno orodje pri ocenjevanju je preštevanje dreves določenih razredovTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije