Zu den Pfaffian-Methoden in der Zählung und Kombinatorik

Vor kurzem habe ich eine Einführung in holographische Algorithmen durchgesehen. Ich bin auf einige kombinatorische Objekte gestoßen, die Pfaffianer genannt werden. Ich weiß im Moment nicht viel darüber und bin auf einige überraschende Anwendungen gestoßen, für die sie eingesetzt werden können.

Ich habe zum Beispiel erfahren, dass sie verwendet werden können, um die Anzahl perfekter Übereinstimmungen in ebenen Diagrammen effizient zu zählen. Sie können auch verwendet werden, um die Anzahl möglicher Kacheln eines Schachbretts unter Verwendung von 2 * 1-Kacheln zu zählen. Die Kachelverbindung schien mir sehr neugierig und ich habe versucht, im Internet nach relevanteren Materialien zu suchen, aber an den meisten Stellen habe ich nur ein oder zwei Aussagen über die Verbindung und sonst nichts gefunden.

Ich wollte nur fragen, ob jemand einen Verweis auf relevante Literatur vorschlagen könnte, da dies wirklich großartig wäre, und ich freue mich darauf, einige verwandte Materialien zu studieren.

(Dies ist eine interessante Frage für mich, da ich auch über den Pfaffian lese.)

Ich schlage folgende Referenzen vor:

• Kapitel 8 des großartigen Buches Matching Theory von Lovasz und Plummer.
• Die Arbeit Division-Free Algorithms for the Determinant and the Pfa'an: Algebraic and Combinatorial Approaches von Rote. In diesem Artikel wird der Pfaffian mit dem kombinatorischen Objekt " Alternating Closed Walk Sequence" (auch als alternierende Clow-Sequenz bezeichnet) in Beziehung gesetzt, das uns einen dynamischen (teilungsfreien) Algorithmus zur Berechnung des Pfaffian liefert.
• Der Artikel Nicht schneidende Pfade, Pfänder und ebene Partitionen von Stembridge zeigt, wie mit dem Pfaffian Konfigurationen in der Kombinatorik aufgezählt werden können. Die Arbeit liefert auch kombinatorische Beweise für grundlegende Identitäten, z.

  Wenn eine schrägsymmetrische Matrix ist, dann ist p f ( A ) 2 = d e t ( A ) .$A$$\mathsf{pf}(A)^2 = \mathsf{det}(A)$

Möglicherweise finden Sie dieses Papier über Pfaffian-Schaltungen und die darin enthaltenen Referenzen interessant. Ich habe es als eigenständige Einführung in holografische Algorithmen sowie als Erläuterung der Möglichkeiten von Pfaffians verstanden.

Das hätte eigentlich ein Kommentar sein sollen, aber aus Platzgründen poste ich dies als Antwort.

Danke für die Antworten und Kommentare an alle. Kürzlich bin ich auf eine andere Umfrage von Robin Thomas gestoßen. Sie finden es hier http://people.math.gatech.edu/~thomas/PAP/pfafsurv.pdf .

Davon abgesehen möchte ich noch eine Aussage zur Kachelverbindung hinzufügen (auf die mich Prof. Dana Randall hingewiesen hat). Wenn Sie das Doppelgitter nehmen, sind 2x1 Dominosteine ​​nur Kanten. Daher ist eine perfekte Kachelung genau das Richtige für Sie. Dann kann die Theorie der Pfaffianer verwendet werden, um perfekte Übereinstimmungen in ebenen Graphen zu zählen.

Dies bedeutet, dass Sie sich in erster Linie darauf konzentrieren können, perfekte Übereinstimmungen in der Grafik zu zählen - der Rest folgt nur trivial.

Es gibt auch Arbeiten von Charles Little, Fischer, McCuaig, Robertson, Seymour und Thomas, Loebl, Galluccio, Tesler, Miranda, Lucchesi, de Carvalho und Murty (die mir gerade einfallen).