О методах Пфаффа в подсчете и комбинаторике

13

Недавно я изучал введение в голографические алгоритмы. Я столкнулся с некоторыми комбинаторными объектами, которые называются пфаффианцами. Я не очень много знаю о них на данный момент и натолкнулся на некоторые неожиданные способы их использования.

Например, я узнал, что их можно использовать для эффективного подсчета количества идеальных совпадений на плоских графиках. Кроме того, их можно использовать для подсчета количества возможных выпадений на шахматной доске, используя плитки 2 * 1. Связь с плиткой показалась мне очень любопытной, и я попытался найти более релевантные материалы в Интернете, но в большинстве мест я нашел только одно или два заявления о связи и ничего больше.

Я просто хотел спросить, может ли кто-нибудь предложить какую-нибудь ссылку на соответствующую литературу, поскольку это было бы действительно здорово, и я с нетерпением жду изучения некоторых связанных материалов.

reference-request co.combinatorics counting-complexity Акаш Кумар
источник
3
Это известно как «проблема димера». Обзор находится в разделе 7.14 «Точно решаемых моделей» Бакстера, а также в math.brown.edu/~rkenyon/papers/de2.pdf. Число димеров может быть выражено как функция разбиения модели Изинга, разработанный пример функции разбиения Изинга. через Пфаффиана в cs.cmu.edu/~jch1/research/presentation/globersonjaakkola.ppt
Ярослав Булатов
спасибо за комментарий ярослав. Пример cmu выглядит полезным
Акаш Кумар
Возможно, вас заинтересует краткая история пфаффианцев на сайте combinatorics.org/Volume_3/PDF/v3i2r5.pdf
Radu GRIGore
Спасибо за комментарий Раду. Я столкнулся с другим опросом Робина Томаса. Вы можете найти его здесь people.math.gatech.edu/~thomas/PAP/pfafsurv.pdf
Акаш Кумар

Ответы:

17

(Это интересный вопрос для меня, потому что я также читаю о Пфаффиане.)

Я предлагаю следующие ссылки:

Дай Ле
источник
2
Действительно, большое спасибо, Дай. Это действительно хорошие ссылки. Я скоро их пройду. Еще раз спасибо. И да, наслаждайтесь этим Рождеством и очень счастливого нового года!
Акаш Кумар
@arnab и @Akash Я рад, что мое предложение помогает! Счастливого Рождества и счастливого нового года вам двоим!
Дай Ле
@Dai, это выглядит очень интересно. В какой из этих трех ссылок упоминается алгоритм Берковица (версия Пфаффа)?
Майкл Солтыс
12

Вы можете найти эту статью о цепях Пфаффа и ссылки в ней интересными; Я имел в виду, что это будет самостоятельное введение в голографические алгоритмы, а также исследование того, что можно сделать с помощью пфаффианцев.

Джейсон Мортон
источник
Это потрясающе! Спасибо и с новым годом!
Дай Ле
Ого ... это здорово! Совершенно в гармонии с тем, что я хотел. Большое спасибо (и да, с новым годом)
Акаш Кумар
6

Это действительно должен был быть комментарий, но из-за недостатка места я отправляю это как ответ.

Спасибо за ответы и комментарии всем. Недавно я наткнулся на очередной опрос Робина Томаса. Вы можете найти его здесь http://people.math.gatech.edu/~thomas/PAP/pfafsurv.pdf .

Помимо этого, я бы также добавил одно утверждение о связи с плиткой (на которое мне указал профессор Дана Рэндалл). Если взять двойную решетку, то плитки домино 2х1 - это просто ребра. Следовательно, идеальная черепица - это как раз идеальное совпадение в двойном. Затем теория Пфаффиана может быть использована для подсчета идеальных совпадений в плоских графах.

Это означает, что вы можете в первую очередь сосредоточиться на подсчете идеальных совпадений на графике - остальное просто следует тривиально.

Акаш Кумар
источник
3

Есть также работа, проделанная Чарльзом Литтлом, Фишером, Маккуэйгом, Робертсоном, Сеймуром и Томасом, Лоэблом, Галлуччо, Теслером, Мирандой, Луккези, де Карвалью и Мурти (те, которые приходят мне в голову прямо сейчас).


источник