Towards understanding complexity of Ising partition function

by · Jul 23, 2016 · 199 views ·

Ising partition function is usually defined on a graph G embedded in a 2-dimensional surface. It is equivalent to the generating function of the edge-cuts of G, and also to the generating function of the even sets of edges of G. A standard way to calculate the Ising partition function is to compute a linear combination of 4g Pfaffians, where g is the genus of the surface. This is known as the Arf-invariant formula. Solving a conjecture of Sergei Norine for even sets, we proved some years ago with Gregor Masbaum that 4g is optimal in a very restricted but natural computational model. In the talk I will further address the complexity of computing the maximum weight of an edge-cut for embedded graphs. Close to enumeration of the even sets is the enumeration of the perfect matchings. I will discuss some questions about perfect matchings enumeration on grids suggested by physicists. Finally, I will discuss product formulas for the Ising partition functions.

Watch SlidesLive on mobile devices

© SlidesLive Inc.