Recentemente, eu estava revisando uma introdução aos algoritmos holográficos. Me deparei com alguns objetos combinatórios chamados Pfaffians. Eu realmente não sei muito sobre isso no momento e me deparei com alguns usos surpreendentes que eles podem usar.
Por exemplo, soube que eles podem ser usados para contar com eficiência o número de combinações perfeitas em gráficos planares. Além disso, eles podem ser usados para contar o número de possíveis inclinações de um tabuleiro de xadrez usando peças 2 * 1. A conexão lado a lado parecia muito curiosa para mim e tentei procurar materiais mais relevantes na Web, mas na maioria dos lugares encontrei apenas uma ou duas afirmações sobre a conexão e nada mais.
Eu só queria perguntar se alguém poderia sugerir alguma referência à literatura relevante, pois isso seria realmente ótimo e estou ansioso para estudar alguns materiais relacionados.
fonte
Respostas:
(Esta é uma pergunta interessante para mim, porque também estou lendo sobre o Pfaffian.)
Sugiro as seguintes referências:
fonte
Você pode achar interessante este artigo sobre circuitos pfaffianos e as referências nele contidas; Eu pretendi que fosse uma introdução independente aos algoritmos holográficos, além de explorar o que pode ser feito com os Pfaffians.
fonte
Isso realmente deveria ter sido um comentário, mas, pela falta de espaço, estou postando isso como resposta.
Obrigado pelas respostas e comentários a todos. Recentemente, me deparei com outra pesquisa de Robin Thomas. Você pode encontrá-lo aqui http://people.math.gatech.edu/~thomas/PAP/pfafsurv.pdf .
Fora isso, eu também acrescentaria uma declaração sobre a conexão lado a lado (que foi apontada pela Prof Dana Randall). Se você usar a treliça dupla, as peças de dominó 2x1 serão apenas bordas. Portanto, um ladrilho perfeito é precisamente uma combinação perfeita no dual. Então, a teoria de Pfaffians pode ser usada para contar combinações perfeitas em gráficos planares.
Isso significa que você pode se concentrar principalmente na contagem de combinações perfeitas no gráfico - o resto segue apenas trivialmente.
fonte
Também há trabalhos de Charles Little, Fischer, McCuaig, Robertson, Seymour e Thomas, Loebl, Galluccio, Tesler, Miranda, Lucchesi, de Carvalho e Murty (os que me vêm à cabeça agora).
fonte