2022/05/04 by Costa, Simone
#05B20 #05C10 #05C15 #05C30 #05C60 #05D40 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2205.02066
Archdeacon, in his seminal paper [1], defined the concept of Heffter array in order to provide explicit constructions of ℤv-regular biembeddings of complete graphs Kv into orientable surfaces. In this paper, we first introduce the quasi-Heffter arrays as a generalization of the concept of Heffer array and we show that, in this context, we can define a 2-colorable embedding of Archdeacon type of the complete multipartite graph K(v)/(t)× t into an orientable surface. Then, our main goal is to study the full automorphism groups of these embeddings: here we are able to prove, using a probabilistic approach, that, almost always, this group is exactly ℤv. As an application of this result, given a positive integer t\not≡ 0\pmod4, we prove that there are, for infinitely many pairs of v and k, at least (1-o(1)) (((v-t)/(2))!)/(ϕ(v)) non-isomorphic biembeddings of K(v)/(t)× t whose face lengths are multiples of k. Here ϕ(⋅) denotes the Euler's totient function. Moreover, in case t=1 and v is a prime, almost all these embeddings define faces that are all of the same length kv, i.e. we have a more than exponential number of non-isomorphic kv-gonal biembeddings of Kv.