Livro para auto-estudo de algoritmos na teoria de grupos

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?

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.

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.

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.

Não é um livro, mas talvez as notas de A. Hulpke sobre a teoria dos grupos computacionais sejam de interesse?

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.

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.