Teoria Combinatória de Grupos e Semigrupos

Código:

M502

Sigla:

M502

Áreas Científicas
Classificação	Área Científica
OFICIAL	Matemática

Ocorrência: 2011/2012 - 2S

Ativa?	Sim
Unidade Responsável:	Departamento de Matemática
Curso/CE Responsável:	Programa Doutoral em Matemática - Interuniversitário

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
IUD-M	2	PE do Prog Inter-Univ Dout Mat	1	-	9	60	243

Língua de trabalho

Inglês

Objetivos

Getting acquaintance with the recent trends of combinatorial and geometric (semi)group theory.

Programa

1. Words and free monoids.

Words are the primordial object in both combinatorial group theory and combinatorial semigroup theory. We introduce their basic combinatorial properties and explore free monoids.

2. Languages and automata.

Languages are sets of words and they can be used to encode virtually everything, playing therefore a major role in theoretical computer science. Rational languages and finite automata are central.

3. Turing machines and computability.

If finite automata are often involved in the positive successes of the theories, we need to dive into the darkest waters of uncomputability to understand the limits of algorithmics in groups and semigroups.

4. Free groups.

Free groups play a major role in this course. We explore several important themes: Stallings' automata for finitely generated subgroups, the automorphism group, rational subsets, the boundary of the completion for the prefix metric. Finite automata are ubiquitous.

5. Free inverse monoids.

Inverse monoids correspond to partial injective transformations the way groups correspond to permutations. Free inverse monoids, in the beautiful Munn construction, are built from finite trees (finite automata, actually), and constitute undoubtedly one of the most aesthetic algebraic objects in Mathematics.

6. Presentations.

This is the moment when we leave the safe coast of free objects for the open sea of (finite) presentations, where we subject free objects to a few defining relations and obtain therefore various types of quotients. We start our study of Cayley graphs and Schutzenberger graphs, obtaining also the first major undecidability results.

7. Free products and graph products.

We study free products and their generalization to the partial commutativity case: graph products. We start by the basic models of trace monoids and graph groups.

8. Van Kampen diagrams and pictures.

Van Kampen diagrams and pictures constitute the classical geometric tools to study group presentations, and have been successfully applied to study many types of presentations, such as in the case of small cancellation.

9. HNN extensions and free products with amalgamation.

These two constructions constitute two of the biggest successes in terms of construction of normal forms and applications, and are deeply interconnected. Some of the most unlikely embedding theorems could be proved using these tools.

10. Beyond the word problem.

So far, the decidability problem we have usually considered is the word problem. Now we solve other problems for particular cases such as the conjugacy problem or the isomorphism problem.

11. Inverse monoid presentations and Stephen's sequence.

Stephen's sequence emerges in the late eighties as a powerful tool to study various finite inverse monoid presentations from a geometric viewpoint. We introduce the construction and explore some of its nicest applications.

12. Hyperbolic groups.

Gromov introduces hyperbolic groups in 1987 with a revolutionary idea: to use the geometry of the Cayley graph to solve algorithmic problems. We study the properties and applications of the theory, including the central concept of quasi-isometry.

13. Automatic groups.

This concept can be defined through purely automata-theoretic features or blending it in alternative with a geometric property of the Cayley graph. We present some of its successes.

14. Self-similar groups.

Grigorchuk boosted in the last decade the study of self-similar groups, also known as automata groups. These are groups of sequential permutations built from a certain type of finite automata, and are deeply related to wreath products and actions in uniform trees of finite degree.

Observações Bibliográficas

Detailed bibliography can be provided upon request to the email pvsilva@fc.up.pt.

Métodos de ensino e atividades de aprendizagem

Exposition on blackboard. Discussion of exercises.

Tipo de avaliação

Avaliação distribuída com exame final

Componentes de Avaliação

Descrição	Tipo	Tempo (Horas)	Peso (%)	Data Conclusão
Participação presencial (estimativa)	Participação presencial	56,00
	Total:	-	0,00

Fórmula de cálculo da classificação final

50% of the classification is obtained by the written resolution of 14 exercises. The other 50% are determined by the final exam, where the students are free to use notes to help them. A minimum marking of 9 is required in the final exam.