Counting over non-planar graphs

Riccardo Zecchina

Physica A: Statistical Mechanics and its Applications, 2001, vol. 302, issue 1, 100-109

Abstract: In a framework at the interface between statistical physics and computational complexity, we discuss the extension of the Pfaffian formalism for the evaluation of the Ising partition function or of the weighted matching polynomial over planar lattices to the general case of non-planar graphs. The combinatorial features of the method acquire a simple topological character independent of the local details of the lattices. As a by product, we also give a simple formula for the evaluation of the permanent of 0–1 matrices in terms of determinants.

Date: 2001
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437101004459
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:302:y:2001:i:1:p:100-109

DOI: 10.1016/S0378-4371(01)00445-9

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().