Distinguishing partitions of complete multipartite graphs - Goff, Michael (Ars mathematica contemporanea, 2016)
Razlikovalna 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 razredov.
Keywords: combinatorial species; complete multipartite graph; distinguishing partition; kombinatorične vrste; polni multipartitni graf; preštevanje dreves; razlikovalna particija; tree enumeration