Acerca de los métodos de Pfaffian en conteo y combinatoria

Recientemente, estaba revisando una introducción a los algoritmos holográficos. Encontré algunos objetos combinatorios llamados Pfaffians. No sé mucho sobre eso en este momento y encontré algunos usos sorprendentes a los que se les puede dar.

Por ejemplo, llegué a saber que se pueden usar para contar eficientemente la cantidad de coincidencias perfectas en gráficos planos. Además, se pueden usar para contar el número de posibles inclinaciones de un tablero de ajedrez usando fichas de 2 * 1. La conexión en mosaico me pareció muy curiosa y traté de buscar materiales más relevantes en la web, pero en la mayoría de los lugares simplemente encontré una o dos afirmaciones sobre la conexión y nada más.

Solo quería preguntar si alguien podría sugerir alguna referencia a la literatura relevante, ya que eso sería realmente genial y espero estudiar algunos materiales relacionados.

(Esta es una pregunta interesante para mí porque también estoy leyendo sobre el Pfaffian).

Sugiero las siguientes referencias:

• Capítulo 8 del impresionante libro Matching Theory de Lovasz y Plummer.
• El documento Algoritmos libres de división para el determinante y el Pfa ffi an: enfoques algebraicos y combinatorios de Rote. Este artículo relaciona el Pfaffian con el objeto combinatorio llamado secuencia de caminata cerrada alterna (también conocida como secuencia de payaso alterna), que nos da un algoritmo dinámico (sin división) para calcular el Pfaffian.
• El documento Rutas de no intersección, pfa ffi ans y particiones planas de Stembridge, que muestra cómo usar el Pfaffian para enumerar configuraciones en combinatoria. El documento también proporciona pruebas combinatorias de identidades básicas, por ejemplo,

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

Puedes encontrar este artículo sobre los circuitos de Pfaffian y las referencias allí interesantes; He querido que sea una introducción autónoma a los algoritmos holográficos, así como explorar lo que se puede hacer con Pfaffians.

Esto realmente debería haber sido un comentario, pero por la falta de espacio, estoy publicando esto como respuesta.

Gracias por las respuestas y comentarios a todos. Recientemente, me encontré con otra encuesta realizada por Robin Thomas. Puede encontrarlo aquí http://people.math.gatech.edu/~thomas/PAP/pfafsurv.pdf .

Aparte de esto, también agregaría una declaración sobre la conexión de mosaico (que me señaló la profesora Dana Randall). Si toma la retícula dual, las fichas de dominó 2x1 son solo bordes. Por lo tanto, un mosaico perfecto es precisamente una combinación perfecta en el dual. Entonces, la teoría de Pfaffians se puede usar para contar emparejamientos perfectos en gráficos planos.

Esto significa que puede centrarse principalmente en contar las coincidencias perfectas en el gráfico; el resto solo sigue trivialmente.

También hay trabajos realizados por Charles Little, Fischer, McCuaig, Robertson, Seymour y Thomas, Loebl, Galluccio, Tesler, Miranda, Lucchesi, de Carvalho y Murty (los que me vienen a la mente en este momento).