Low-dimensional affine synchronizing groups

Tese de mestrado em Matemática, apresentada à Universidade de Lisboa, através da Faculdade de Ciências, 2012The synchronization property emerged from finite state automata and transformation semigroup theory. Synchronizing permutation groups were introduced by Arnold and Steinberg to study the Cerný Conjecture. In this thesis we study the synchronization property in affine permutation groups of low-dimensions. J.E. Pin proved that one-dimensional affine groups are synchronizing. Hence our main results concern affine groups in dimension 2. We used the characterization given by Neumann of synchronization using graph theory, which relies on the study of the equality between the clique number and the chromatic number of certain graphs invariant under the actions of a group, called the suitability property. It turned out that some of such graphs for two-dimensional affine groups have an interesting geometry and are part of a widely studied class of graphs, the generalized Paley graphs. Further, we used the properties of the theta-function defined by Lovász connected to eigenvalues of a graph to obtain a necessary condition for the suitability in edge-transitive and vertex-transitive graphs. In this thesis we stated a criterion to decide if a generalized Paley graph is suitable. Then we used the tools referred to above and we presented conditions for twodimensional affine groups to be synchronizing.A propriedade de sincronização surgiu no contexto da teoria de autómatos e semigrupos de transformaçãoo. Arnold and Steinberg definiram os grupos de permutação sincronizantes com o objectivo de estudar a Conjectura de Cerný por outra perspectiva. Nesta tese estudamos a propriedade de sincronização em grupos afins de pequenas dimensões. Dado que J.E. Pin provou que os grupos afins de dimensão 1 são sempre sincronizantes, os resultados principais desta tese aplicam-se a grupos afins bidimensionais. Peter Neumann estudou os grupos sincronizantes usando teoria de grafos. Esta caracterização consiste no estudo de grafos invariantes sobre a acção de um grupo e em determinar se os seus números cromático e de clique coincidem. Descobrimos que alguns grafos invariantes sobre a acção de grupos afinns bidimensionais tinham uma geometria simétrica e que faziam parte de uma classe amplamente estudada de grafos, conhecidos como grafos de Paley generalizados. Como ferramenta extra, estudámos a função-teta, um número invariante num grafo, que foi definida por Lovász. Esta função possui uma caracterização que utiliza os valores próprios da matriz de adjacência do grafo e que nos permitiu concluir uma condição suficiente para a igualdade no número cromático e de clique em grafos cujo grupo de automorfismos é transitivo nas arestas e nos vértices. Nesta tese estabelecemos um critério para a igualdade no número cromático e de clique nos grafos de Paley generalizados e usámos esse resultado, bem como as ferramentas anteriormente referidas, para obter uma caracterização dos grupos afins bidimensionais sincronizantes