A Fast Algorithm for Finding Quasi-Geodesic \(\sigma\)-positive Braids
speaker: Luis Paris (Université de Bourgogne)abstract: Joint work with J. Fromentin.
Let \(n \in \mathbb{N}\), \(n \ge 2\), and \(i \in \{1, \dots, n-1\}\). We say that a braid \(\beta \in B_n\) is \({\it \sigma_i-positive}\) (resp. \({\it \sigma_i-negative}\)) if it can be written in the form
\begin{equation}
\beta = \beta0 \sigmai \beta1 \cdots \sigmai \betak \quad (\text{resp.}\ \beta0 \sigmai{-1} \beta1 \cdots \sigmai{-1} \betak)\,,
\end{equation}
with \(k \ge 1\) and \(\beta_0,\beta_1, \dots, \beta_k \in B_i\). A celebrated theorem of P. Dehornoy says that, for every braid \(\beta \in B_n \setminus \{1\}\), there is a unique \(i \in \{1, \dots, n-1\}\) such that \(\beta\) is either \(\sigma_i\)-positive, or \(\sigma_i\)-negative, but not both. There are several proofs of this result, most of them effective, but all with algorithms of exponential (or more) complexity, and that determine either a \(\sigma_i\)-positive expression, or \(\sigma_i\)-negative expression, whose length is exponential with respect to the word length of \(\beta\). Recall that the length of the expression in (1) is
\[
k+1 + \sum_{j=0}^k \
\beta_j\
\,,
\]
where \(\
\beta_j\
\) denotes the word length of \(\beta_j\) with respect to the canonical generating set.
In this lecture we present a new algorithm of quadratic complexity which, given a braid \(\beta \in B_n \setminus \{1\}\), determines either a \(\sigma_i\)-positive expression, or a \(\sigma_i\)-negative expression, whose length is linear with respect to the word length of \(\beta\).
timetable:
Wed 22 Jun, 10:00 - 11:00, Aula Dini
<< Go back