Quanto aos métodos Pfaffianos em contagem e combinatória

13

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.

Akash Kumar
fonte
3
Isso é conhecido como "problema do dímero". Uma visão geral está na seção 7.14 dos "Modelos exatamente resolvidos" da Baxter e também em math.brown.edu/~rkenyon/papers/de2.pdf O número de dímeros pode ser expresso como função de partição do modelo Ising, um exemplo elaborado da função de partição Ising através do Pfaffian é dado em cs.cmu.edu/~jch1/research/presentation/globersonjaakkola.ppt
Yaroslav Bulatov
obrigado pelo comentário yaroslav. o exemplo CMU parece útil
Akash Kumar
Você pode estar interessado na breve história dos pfaffians de combinatorics.org/Volume_3/PDF/v3i2r5.pdf
Radu GRIGore
Obrigado pelo comentário Radu. Me deparei com outra pesquisa feita por Robin Thomas. Você pode encontrá-lo aqui people.math.gatech.edu/~thomas/PAP/pfafsurv.pdf
Akash Kumar

Respostas:

17

(Esta é uma pergunta interessante para mim, porque também estou lendo sobre o Pfaffian.)

Sugiro as seguintes referências:

Dai Le
fonte
2
Realmente, muito obrigado Dai. Essas são realmente boas referências. Vou passar por eles muito em breve. Obrigado novamente. E sim, aproveite este Natal e tenha um feliz ano novo!
Akash Kumar
@arnab e @Akash Estou feliz que minha sugestão ajude! Feliz Natal e feliz ano novo para vocês dois!
Dai Le
@ Dai, isso parece muito interessante. Qual dessas três referências menciona o algoritmo de Berkowitz (versão Pfaffian)?
22719 Michael Soltys
12

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.

Jason Morton
fonte
Fantástico! Obrigado e feliz ano novo!
Dai Le
Whoo ... isso é ótimo! Totalmente em sintonia com o que eu queria. Muitos graças (e sim um feliz ano novo)
Akash Kumar
6

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.

Akash Kumar
fonte
3

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