Leírás
In this "mixed salad" talk, I will introduce graph-theoretical, algorithmic, and algebraic concepts arising in the study of permutations, as developed by geneticists and bioinformaticians. After a brief historical overview of how discrete algorithmic problems were formulated by geneticists before the development of the theory of computation and the construction of the first electronic computers, I will focus on two sorting problems: sorting signed permutations by reversals and sorting permutations by block interchanges. For both problems, there are two notable classes of permutations that may exhibit limiting structures: dead-end permutations in Cayley graphs defined by the sorting operations as generators, and permutations arising from the so-called infinite-site model.
Signed permutations form the hyperoctahedral group, which is isomorphic to the wreath product of $\mathbb{Z}_2$ and $S_n$. A reversal acts on a signed permutation by reversing a consecutive segment and flipping the signs of all elements within that segment. A dead end in a Cayley graph is a vertex $v$ that has no neighbor farther from the identity than $v$. While every finite Cayley graph trivially has at least one dead end (namely, a vertex at maximal distance from the identity), the Cayley graph generated by reversals contains dead ends at distance $(2/3 - \varepsilon)$ times the diameter. These permutations admit a natural description via certain graphs called adjacency graphs.
It remains an open question whether these dead ends possess a limiting structure that can be described in a graph-theoretical framework, similarly to how Brownian separable permutons can be described via Galton–Watson trees. Another open problem is to determine the smallest constant $c$ such that, in a given class of finite Cayley graphs, there exist dead ends at distance $c$ times the diameter from the identity. A further question concerns the maximal possible proportion of dead ends in such graph classes.
In the infinite-site model, the length of the permutation tends to infinity, and the rate of mutations (i.e., the allowed sorting operations) also tends to infinity, while the expected number of mutations in a fixed time interval remains constant. In this regime, with high probability, no position in the permutation is affected more than once. These permutations admit both a graph-theoretical description and an elegant linear-algebraic formulation over the finite field $\mathbb{F}_2$.