Mengenai Metode Pfaffian dalam Menghitung dan Kombinasi

13

Baru-baru ini, saya akan membahas pengantar Holographic Algorithms. Saya menemukan beberapa objek kombinatorial yang disebut Pfaffians. Saya tidak benar-benar tahu banyak tentang itu saat ini dan menemukan beberapa kegunaan mengejutkan yang bisa mereka lakukan.

Sebagai contoh, saya jadi tahu bahwa mereka dapat digunakan untuk menghitung secara efisien jumlah pencocokan sempurna dalam grafik planar. Juga, mereka dapat digunakan untuk menghitung jumlah kemungkinan papan catur menggunakan 2 * 1 ubin. Koneksi ubin sepertinya sangat ingin tahu bagi saya dan saya mencoba mencari materi yang lebih relevan di web tetapi di sebagian besar tempat saya hanya menemukan satu atau dua pernyataan tentang koneksi dan tidak ada yang lain.

Saya hanya ingin bertanya apakah seseorang dapat menyarankan beberapa referensi ke literatur yang relevan karena itu akan sangat bagus dan saya berharap untuk mempelajari beberapa materi terkait.

reference-request co.combinatorics counting-complexity Akash Kumar
sumber
3
Ini dikenal sebagai "masalah dimer." Gambaran umum ada di bagian 7.14 dari "Model yang Dipecahkan dengan Tepat" Baxter dan juga dalam math.brown.edu/~rkenyon/papers/de2.pdf Jumlah dimer dapat diekspresikan sebagai fungsi partisi model Ising, contoh yang dikerjakan dari fungsi partisi Ising melalui Pfaffian diberikan di cs.cmu.edu/~jch1/research/presentation/globersonjaakkola.ppt
Yaroslav Bulatov
terima kasih atas komentarnya yaroslav. contoh cmu terlihat membantu
Akash Kumar
Anda mungkin tertarik dengan sejarah singkat pfaffian dari combinatorics.org/Volume_3/PDF/v3i2r5.pdf
Radu GRIGore
Terima kasih atas komentarnya Radu. Saya menemukan survei lain oleh Robin Thomas. Anda dapat menemukannya di sini people.math.gatech.edu/~thomas/PAP/pfafsurv.pdf
Akash Kumar

Jawaban:

17

(Ini adalah pertanyaan yang menarik bagi saya karena saya juga membaca tentang Pfaffian.)

Saya menyarankan referensi berikut:

Dai Le
sumber
2
Sungguh, terima kasih banyak Dai. Itu referensi yang sangat bagus. Saya akan pergi melalui mereka segera. Terima kasih lagi. Dan ya, nikmati Natal ini dan selamat tahun baru!
Akash Kumar
@arnab dan @Akash Saya senang saran saya membantu! Selamat Natal dan selamat tahun baru untuk kalian berdua!
Dai Le
@Dai, ini terlihat sangat menarik. Manakah dari tiga referensi ini yang menyebutkan algoritma Berkowitz (versi Pfaffian)?
Michael Soltys
12

Anda mungkin menemukan makalah ini di sirkuit Pfaffian dan referensi di dalamnya menarik; Saya bermaksud menjadikannya pengantar mandiri untuk algoritma holografik serta mengeksplorasi apa yang bisa dilakukan dengan Pfaffians.

Jason Morton
sumber
Itu luar biasa! Terima kasih dan selamat tahun baru!
Dai Le
Wah ... bagus sekali! Benar-benar selaras dengan apa yang saya inginkan. Terima kasih banyak (dan ya tahun baru yang bahagia)
Akash Kumar
6

Ini seharusnya benar-benar komentar, tetapi karena kurangnya ruang saya memposting ini sebagai jawaban.

Terima kasih atas jawaban dan komentar semua orang. Baru-baru ini, saya menemukan survei lain oleh Robin Thomas. Anda dapat menemukannya di sini http://people.math.gatech.edu/~thomas/PAP/pfafsurv.pdf .

Selain ini, saya juga akan menambahkan satu pernyataan tentang koneksi ubin (yang ditunjukkan kepada saya oleh Prof Dana Randall). Jika Anda mengambil kisi ganda, maka ubin domino 2x1 hanyalah pinggiran. Oleh karena itu, ubin yang sempurna adalah pencocokan sempurna di dual. Kemudian, teori Pfaffians dapat digunakan untuk menghitung kecocokan sempurna dalam grafik planar.

Ini berarti bahwa Anda hanya bisa fokus pada penghitungan kecocokan sempurna dalam grafik - sisanya hanya mengikuti sepele.

Akash Kumar
sumber
3

Ada juga pekerjaan yang dilakukan oleh Charles Little, Fischer, McCuaig, Robertson, Seymour dan Thomas, Loebl, Galluccio, Tesler, Miranda, Lucchesi, de Carvalho, dan Murty (yang muncul di benak saya saat ini.)


sumber