BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Volker Gebhardt

Volker Gebhardt appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.GRmath.CODiscrete Mathematicsmath.GTPopulations and EvolutionQuantitative Methods

Catalog footprint

What is connected

11works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

11 published item(s)

preprint2020arXiv

A path-deformation framework for determining weighted genome rearrangement distance

Measuring the distance between two bacterial genomes under the inversion process is usually done by assuming all inversions to occur with equal probability. Recently, an approach to calculating inversion distance using group theory was introduced, and is effective for the model in which only very short inversions occur. In this paper, we show how to use the group-theoretic framework to establish minimal distance for any weighting on the set of inversions, generalizing previous approaches. To do this we use the theory of rewriting systems for groups, and exploit the Knuth--Bendix algorithm, the first time this theory has been introduced into genome rearrangement problems. The central idea of the approach is to use existing group theoretic methods to find an initial path between two genomes in genome space (for instance using only short inversions), and then to deform this path to optimality using a confluent system of rewriting rules generated by the Knuth--Bendix algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Bacterial phylogeny in the Cayley graph

Many models of genome rearrangement involve operations (e.g. inversions and translocations) that are self-inverse, and hence generate a group acting on the space of genomes. This gives a correspondence between genome arrangements and the elements of a group, and consequently, between evolutionary paths and walks on the Cayley graph. Many common methods for phylogeny reconstruction rely on calculating the minimal distance between two genomes; this omits much of the other information available from the Cayley graph. In this paper we begin an exploration of some of this additional information, in particular describing the phylogeny as a Steiner tree within the Cayley graph, and exploring the "interval" between two genomes. While motivated by problems in systematic biology, many of these ideas are of independent group-theoretic interest.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the penetration distance in Garside monoids

We prove that the exponential growth rate of the regular language of penetration sequences is smaller than the growth rate of the regular language of normal form words, if the acceptor of the regular language of normal form words is strongly connected. Moreover, we show that the latter property is satisfied for all irreducible Artin monoids of spherical type, extending a result by Caruso. Our results establish that the expected value of the penetration distance $pd(x,y)$ in an irreducible Artin monoid of spherical type is bounded independently of the length of $x$, if $x$ is chosen uniformly among all elements of given canonical length and $y$ is chosen uniformly among all atoms; the latter in particular explains observations made by Thurston in the context of the braid group, and it shows that all irreducible Artin monoids of spherical type exhibit an analogous behaviour. Our results also give an affirmative answer to a question posed by Dehornoy.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Zappa-Szép products of Garside monoids

A monoid $K$ is the internal Zappa-Szép product of two submonoids, if every element of $K$ admits a unique factorisation as the product of one element of each of the submonoids in a given order. This definition yields actions of the submonoids on each other, which we show to be structure preserving. We prove that $K$ is a Garside monoid if and only if both of the submonoids are Garside monoids. In this case, these factors are parabolic submonoids of $K$ and the Garside structure of $K$ can be described in terms of the Garside structures of the factors. We give explicit isomorphisms between the lattice structures of $K$ and the product of the lattice structures on the factors that respect the Garside normal forms. In particular, we obtain explicit natural bijections between the normal form language of $K$ and the product of the normal form languages of its factors.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Group-theoretic models of the inversion process in bacterial genomes

The variation in genome arrangements among bacterial taxa is largely due to the process of inversion. Recent studies indicate that not all inversions are equally probable, suggesting, for instance, that shorter inversions are more frequent than longer, and those that move the terminus of replication are less probable than those that do not. Current methods for establishing the inversion distance between two bacterial genomes are unable to incorporate such information. In this paper we suggest a group-theoretic framework that in principle can take these constraints into account. In particular, we show that by lifting the problem from circular permutations to the affine symmetric group, the inversion distance can be found in polynomial time for a model in which inversions are restricted to acting on two regions. This requires the proof of new results in group theory, and suggests a vein of new combinatorial problems concerning permutation groups on which group theorists will be needed to collaborate with biologists. We apply the new method to inferring distances and phylogenies for published Yersinia pestis data.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Algorithms for Garside calculus

Garside calculus is the common mechanism that underlies a certain type of normal form for the elements of a monoid, a group, or a category. Originating from Garside's approach to Artin's braid groups, it has been extended to more and more general contexts, the latest one being that of categories and what are called Garside families. One of the benefits of this theory is to lead to algorithms solving effectively the naturally occurring problems, typically the Word Problem. The aim of this paper is to present and solve these algorithmic questions in the new extended framework.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Normal forms of random braids

Analysing statistical properties of the normal forms of random braids, we observe that, except for an initial and a final region whose lengths are uniformly bounded (that is, the bound is independent of the length of the braid), the distributions of the factors of the normal form of sufficiently long random braids depend neither on the position in the normal form nor on the lengths of the random braids. Moreover, when multiplying a braid on the right, the expected number of factors in its normal form that are modified, called the "expected penetration distance", is uniformly bounded. We explain these observations by analysing the growth rates of two regular languages associated to normal forms of elements of Garside groups, respectively to the modification of a normal form by right multiplication. A universal bound on the expected penetration distance in a Garside group yields in particular an algorithm for computing normal forms that has linear expected running time.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Computing growth functions of braid monoids and counting vertex-labelled bipartite graphs

We derive a recurrence relation for the number of simple vertex-labelled bipartite graphs with given degrees of the vertices and use this result to obtain a new method for computing the growth function of the Artin monoid of type $A_{n-1}$ with respect to the simple elements (permutation braids) as generators. Instead of matrices of size $2^{n-1}\times 2^{n-1}$, we use matrices of size $p(n)\times p(n)$, where $p(n)$ is the number of partitions of $n$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Generating random braids

We present an algorithm to generate positive braids of a given length as words in Artin generators with a uniform probability. The complexity of this algorithm is polynomial in the number of strands and in the length of the generated braids. As a byproduct, we describe a finite state automaton accepting the language of lexicographically minimal representatives of positive braids that has the minimal possible number of states, and we prove that its number of states is exponential in the number of strands.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Finite index subgroups of mapping class groups

Let $g\geq3$ and $n\geq0$, and let ${\mathcal{M}}_{g,n}$ be the mapping class group of a surface of genus $g$ with $n$ boundary components. We prove that ${\mathcal{M}}_{g,n}$ contains a unique subgroup of index $2^{g-1}(2^{g}-1)$ up to conjugation, a unique subgroup of index $2^{g-1}(2^{g}+1)$ up to conjugation, and the other proper subgroups of ${\mathcal{M}}_{g,n}$ are of index greater than $2^{g-1}(2^{g}+1)$. In particular, the minimum index for a proper subgroup of ${\mathcal{M}}_{g,n}$ is $2^{g-1}(2^{g}-1)$.

0 citations0 reviewsNo code linkedOpen access