Variation of the local topological structure of graph embeddings

The $2$-cell embeddings of graphs on closed surfaces have been widely studied. It is well known that ($2$-cell) embedding a given graph $G$ on a closed orientable surface is equivalent to cyclically ordering the edges incident to each vertex of $G$. In this paper, we study the following problem: given a genus $g$ embedding $mathbb{E}$ of the graph $G$, if we randomly rearrange the edges around a vertex, i.e., re-embedding, what is the probability of the resulting embedding $mathbb{E}$ having genus $g+Delta g$? We give a formula to compute this probability. Meanwhile, some other known and unknown results are also obtained. For example, we show that the probability of preserving the genus is at least $frac{2}{deg(v)+2}$ for re-embedding any vertex $v$ of degree $deg(v)$ in a one-face embedding; and we obtain a necessary condition for a given embedding of $G$ to be an embedding with the minimum genus.

A simple framework on sorting permutations

In this paper we present a simple framework to study various distance problems of permutations, including the transposition and block-interchange distance of permutations as well as the reversal distance of signed permutations. These problems are very important in the study of the evolution of genomes. We give a general formulation for lower bounds of the transposition and block-interchange distance from which the existing lower bounds obtained by Bafna and Pevzner, and Christie can be easily derived. As to the reversal distance of signed permutations, we translate it into a block-interchange distance problem of permutations so that we obtain a new lower bound. Furthermore, studying distance problems via our framework motivates several interesting combinatorial problems related to product of permutations, some of which are studied in this paper as well.

Plane permutations and applications to a result of Zagier-Stanley and distances of permutations

In this paper, we introduce plane permutations, i.e. pairs $mathfrak{p}=(s,pi)$ where $s$ is an $n$-cycle and $pi$ is an arbitrary permutation, represented as a two-row array. Accordingly a plane permutation gives rise to three distinct permutations: the permutation induced by the upper horizontal ($s$), the vertical $pi$) and the diagonal ($D_{mathfrak{p}}$) of the array. The latter can also be viewed as the three permutations of a hypermap. In particular, a map corresponds to a plane permutation, in which the diagonal is a fixed point-free involution. We study the transposition action on plane permutations obtained by permuting their diagonal-blocks. We establish basic properties of plane permutations and study transpositions and exceedances and derive various enumerative results. In particular, we prove a recurrence for the number of plane permutations having a fixed diagonal and $k$ cycles in the vertical, generalizing Chapuys recursion for maps filtered by the genus. As applications of this framework, we present a combinatorial proof of a result of Zagier and Stanley, on the number of $n$-cycles $omega$, for which the product $omega(1~2~cdots ~n)$ has exactly $k$ cycles. Furthermore, we integrate studies on the transposition and block-interchange distance of permutations as well as the reversal distance of signed permutations. Plane permutations allow us to generalize and recover various lower bounds for transposition and block-interchange distances and to connect reversals with block-interchanges.

On plane permutations

In this paper we generalize permutations to plane permutations. We employ this framework to derive a combinatorial proof of a result of Zagier and Stanley, that enumerates the number of $n$-cycles $omega$, for which $omega(12cdots n)$ has exactly $k$ cycles. This quantity is $0$, if $n-k$ is odd and $frac{2C(n+1,k)}{n(n+1)}$, otherwise, where $C(n,k)$ is the unsigned Stirling number of the first kind. The proof is facilitated by a natural transposition action on plane permutations which gives rise to various recurrences. Furthermore we study several distance problems of permutations. It turns out that plane permutations allow to study transposition and block-interchange distance of permutations as well as the reversal distance of signed permutations. Novel connections between these different distance problems are established via plane permutations.