Odnośnie do metod Pfaffa w liczeniu i kombinatoryce

Ostatnio zastanawiałem się nad wprowadzeniem do algorytmów holograficznych. Natknąłem się na obiekty kombinatoryczne zwane Pfaffians. W tej chwili tak naprawdę niewiele o nich wiem i natknąłem się na zaskakujące zastosowania, które można zastosować.

Na przykład dowiedziałem się, że można ich używać do skutecznego liczenia liczby idealnych dopasowań na wykresach płaskich. Można ich również użyć do zliczenia liczby możliwych przechyleń szachownicy za pomocą płytek 2 * 1. Połączenie kafelkowe wydawało mi się bardzo ciekawe i próbowałem szukać bardziej odpowiednich materiałów w Internecie, ale w większości miejsc znalazłem tylko jedno lub dwa oświadczenia o połączeniu i nic więcej.

Chciałem tylko zapytać, czy ktoś mógłby zasugerować jakieś odniesienie do odpowiedniej literatury, ponieważ byłoby to naprawdę świetne i nie mogę się doczekać, aby przestudiować pokrewne materiały.

(To interesujące pytanie dla mnie, ponieważ czytam również o Pfaffianie.)

Proponuję następujące odniesienia:

• Rozdział 8 niesamowitej książki Loving and Plummer pt. Matching Theory .
• Artykuł Algorytmy bez podziału na determinanty i Pfa ffi an: algebraiczne i kombinatoryjne podejścia Rote'a . Ten artykuł wiąże Pfaffian z obiektem kombinatorycznym zwanym naprzemienną sekwencją zamkniętego marszu ( zwaną także naprzemienną sekwencją clow), co daje nam dynamiczny (bez dzielenia) algorytm obliczania Pfaffian.
• W artykule Ścieżki nie przecinające się, pfaffi i płaskie partycje autorstwa Stembridge, który pokazuje, jak używać Pfaffian do wyliczania konfiguracji w kombinatorykach. W artykule podano również kombinatoryjne dowody podstawowych tożsamości, np.

  $A$$\mathsf{pf}(A)^2 = \mathsf{det}(A)$

Ten artykuł na temat obwodów Pfaffa może być dla Ciebie interesujący; Miałem na myśli, że będzie to samodzielne wprowadzenie do algorytmów holograficznych, a także odkrywanie, co można zrobić z Pfaffianami.

To naprawdę powinien być komentarz, ale z powodu braku miejsca zamieszczam to jako odpowiedź.

Dziękujemy za odpowiedzi i komentarze dla wszystkich. Ostatnio natknąłem się na inną ankietę Robina Thomasa. Można go znaleźć tutaj http://people.math.gatech.edu/~thomas/PAP/pfafsurv.pdf .

Poza tym dodam także jedno zdanie na temat połączenia kafelkowego (na co zwróciła mi uwagę Dana Randall). Jeśli weźmiesz podwójną sieć, płytki domino 2x1 są tylko krawędziami. Dlatego idealne kafelkowanie jest właśnie idealnym dopasowaniem w podwójnym. Następnie teorię Pfaffianów można wykorzystać do zliczenia idealnych dopasowań w grafach płaskich.

Oznacza to, że możesz skupić się przede wszystkim na liczeniu idealnych dopasowań na wykresie - reszta po prostu trywialnie.

Są też prace wykonane przez Charlesa Little, Fischera, McCuaiga, Robertsona, Seymour'a i Thomasa, Loebl, Galluccio, Teslera, Mirandy, Lucchesi, de Carvalho i Murty (tych, które przychodzą mi teraz na myśl.)