Computação do grafo das classes de comutação para a maior permutação com sinal

Abstract

Usando a apresentação de Coxeter padrão para o grupo das simetrias com sinal em n+1 letras, duas expressões reduzidas de uma permutação com sinal estão na mesma classe de comutação se uma se poder obter da outra aplicando uma sequência finita de comutações. As classes de comutação de uma dada permutação com sinal podem ser vistas como os vértices de um grafo, chamado grafo das classes de comutação, onde duas classes estão ligadas por uma aresta se existem elementos nessas classes que diferem por uma relação longa. O foco desta tese será o grafo das classes de comutação para a maior permutação com sinal onde vão ser exploradas diversas propriedades, mais especificamente, será calculado o seu diâmetro e raio através da construção de uma função que irá dividir este grafo em várias camadas. Vamos também mostrar que este grafo não é planar para n>2, usando o famoso Teorema de Wagner, e vamos identificar todas as classes de comutação que possuem apenas um elemento. Estes grafos são estruturas que possuem grandes dimensões, o que torna a sua construção manual inexequível. Deste modo, foi desenvolvida uma aplicação que permitiu visualizar o grafo para alguns valores de n, bem como explorar algumas das suas propriedades. Para tal foi necessário construir um algoritmo que permitisse gerar todas as classes de comutação para alguns valor de n. Na parte final deste trabalho serão descritos todos os algoritmos usados para gerar todas as classes de comutação, algo que foi de extrema importância na obtenção dos resultados teóricos.

Using the standard Coxeter presentation for the signed symmetric group on n+1 letters, two reduced expressions for a given signed permutation are in the same commutation class if one expression can be obtained from the other one by applying a finite sequence of commutations. The commutation classes of a given signed permutation can be seen as the vertices of a graph, called the commutation graph, where two classes are connected by an edge if there are elements in those classes that differ by a long braid relation. The commutation graph for the longest signed permutation is going to be the focus of this thesis where we are going to explore some properties of this graph. More specifically, we compute its diameter and radius using a ranking function that will divide the graph in several layers. We will also show that the graph is not planar for n>2, using Wagner's Theorem, and compute all commutation classes that have only one element. This kind of graphs have large dimensions, which makes its construction very difficult if we try to do it by hand. For that reason, we developed an application in which we could visualize the graph for some values of $n$ and explore some of its properties. For this, we constructed an algorithm capable of generating all commutation classes for some values of n. In the final part of this work we describe all algorithms that were used to generate all commutation classes, which were extremely important in obtaining the theoretical results of this thesis.