Livro para auto-estudo de algoritmos na teoria de grupos

12

Eu sou um estudante de matemática interessado em TCS.

Eu quero estudar os algoritmos e a complexidade deles para resolver os problemas teóricos do grupo, como encontrar ordem dos elementos, enumeração de coset, encontrar gerador, testar se um determinado subconjunto gera o grupo.

Que livro devo ler?

ricardorr
fonte
4
Você pode ser mais específico sobre o que você entende por "problemas fundamentais da teoria de grupos"? Dependendo de seus interesses, diferentes fontes podem ser mais ou menos adequada ...
Joshua Grochow
Coisas como encontrar cosets, geradores de descobrir, testar se um subconjunto de um grupo é um gerador, encontrar ordem dos elementos, encontrar subgrupos
ricardorr
@ricardorr talvez você possa editar sua pergunta para torná-la mais precisa? Como Joshua diz, existem várias classes diferentes de problemas relacionados à teoria dos grupos.
András Salamon

Respostas:

6

Se você estiver interessado na teoria de grupos relevante para o isomorfismo do gráfico, além do livro de Seress mencionado por David Eppstein, eu recomendo

Grupos de Permutação de Dixon e Mortimer

O texto acima é um livro sobre a teoria dos grupos "justos", mas dos livros sobre a teoria dos grupos puros, é provavelmente o mais relevante para o isomorfismo de grafos.

Um livro que é mais diretamente sobre algoritmos para isomorfismo de gráfico, que coloca os algoritmos da teoria de grupos no centro do palco, é:

Christoph Hoffman. Algoritmos teóricos de grupo e isomorfismo gráfico . Notas da Aula de Springer em Ciência da Computação 136.

O último (juntamente com a tese de Paolo Codenotti) é atualmente um dos poucos lugares amplamente acessíveis onde você pode realmente encontrar um relato completo de alguns dos algoritmos mais teóricos de grupo para o isomorfismo de grafos.

Joshua Grochow
fonte
16

Realmente faz diferença qual é a entrada para o algoritmo: como você especifica um grupo?

Se você deseja grupos dados por geradores e reladores, sugiro a Teoria Combinatória de Grupos , de Magnus, Karrass e Solitar (mas os algoritmos são escassos, porque muitos dos problemas importantes são indecidíveis).

Se você deseja grupos automáticos (grupos cujos elementos são cadeias de símbolos e cujas operações de grupo são executadas por autômatos finitos, com aplicativos em topologia de baixa dimensão), sugiro Processamento de texto em grupos por Epstein (não eu!), Cannon, Holt , Levy, Paterson e Thurston.

Se você deseja grupos de permutação (o tipo de algoritmo teórico de grupo que é mais relevante, por exemplo, para isomorfismo de gráfico), o Seress tem um livro Algoritmos de Grupo de Permutação, mas eu não tenho uma cópia, então não posso lhe dizer se é bom.

Deve haver um quarto parágrafo aqui sobre algoritmos de grupos de matrizes, mas não conheço um livro sobre esse tópico. Há uma pequena cobertura no livro de Seress.

David Eppstein
fonte
6

A referência mais moderna e abrangente é provavelmente "Handbook of Computational Group Theory", de Holt, Eick e O'Brien (link)

Uma referência clássica é "Computação em grupos apresentados finitamente", de Charles Simms.

NietzscheanAI
fonte
2

Se você está preocupado apenas com grupos de permutação finitos, achei o livro "Algoritmos fundamentais para grupos de permutação", de Gregory Butler, muito legível. É apenas para grupos de permutação finita, mas foi um dos únicos livros que forneceu pseudo-código e descrições algorítmicas que eu pude entender (para Schreirer-Sims, grupos geradores fortes, etc.). O livro de Seress recomendado por outros é decente, mas por alguma razão ele tem aversão ao pseudo código, por isso foi muito difícil para mim entender. Pessoalmente, usei o livro de Butler para uma compreensão concreta dos algoritmos e o livro de Seress como auxílio na compreensão de provas de correção.

O livro de Butler já é bastante antigo, mas ainda não encontrei uma introdução melhor aos algoritmos de grupos de permutações finitas.

user834
fonte
1

Cortei os dentes na Pesquisa de Enumeração Combinatória de Algoritmos, http://www.math.mtu.edu/~kreher/cages.html .

Eu recomendo. Você aprende algoritmos de grupo de codificação muito mais rápidos, pois os exemplos manuais são detalhados rapidamente. Também pegue um sistema como o Sage ou o Magma para jogar como calculadora de bancada.

Chad Brewbaker
fonte
Apenas uma observação de que o capítulo deste livro sobre grupos parece ser principalmente sobre grupos de permutação.
David Eppstein