Max Planck Institute for Dynamics and Self-Organization -- Department for Nonlinear Dynamics and Network Dynamics Group
Personal tools
Log in

Complex Disordered Systems: Statistical Physics and Symbolic Computation

Anti-ferromagnetically interacting multi-state spins

In systems of statistical physics, a few macroscopic quantities specify thermodynamic states (macrostates) which are realized by an ensemble of microscopic states (microstates), defined by the values of all degrees of freedom of all particles. Whereas some specific microstates are essentially irrelevant because they are extremely rare in number and thus highly improbable, a huge number of microstates are typical in the sense that it individually represents the macrostate in a faithful way. For simple systems the relevance of microscopic states is well understood. For instance, in an ideal gas in a finite box, by the assumption of the thermodynamics of microcanonical ensembles, each microscopic state is equally probable such that the probability of the gas being in a small part of the box is much smaller than it being distributed over the entire box. In this sense a microstate of the gas that is distributed over the available volume may be a faithful representation of macroscopic variables whereas the microstate of a the gas localized in a part of the box is essentially not relevant for the macrostate.

For many-particle systems with more complicated interactions than those assumed for the ideal gas, however, it is not well understood how microstates contribute to complex macroscopic ground states and other equilibria. Furthermore, for many systems of physical relevance the partition function or its equivalent, even for the ground state, cannot be computed such that these systems are poorly understood [1]. In the current project we study two different paradigmatic systems where we develop the theory and computation of complex macrostates. First, we consider the dynamics and equilibria of reorganization processes of particle aggregates on surfaces. Here we theoretically unified and explained several previous model-specific works and used the new theoretical insights to develop alternative, efficient algorithms to study properties of the equilibria. Second, we consider the anti-ferromagnetic Potts model, a paradigmatic system to study phase transitions in statistical physics; here we use an equivalence between the partition function of Potts models and representation-invariant polynomials in graph theory to compute these polynomials and thus all main observables. In particular, these results contribute towards understanding systems exhibiting ground state entropy, an exception to the third law of thermodynamics.

 

Statistical Physics of Reorganization. Self-organizing many-particle systems - ranging from interacting atoms in clusters to co-acting individuals in flocks of birds - constitute fundamental cornerstones for understanding universal features of complex systems. The physics of particle reorganization on surfaces [2] exhibits dominantly stochastic dynamics where the macroscopic equilibrium, if it exists, consists of many different coexisting microscopic states but is typically characterized by statistical mean field measures (e.g., average thickness, average height fluctuations, fractal dimension, total spatial extent). For instance, a mono-layered connected aggregate of a fixed number of particles is continuously rearranging and assuming a huge number of different aggregates of complicated structure, often of self-similar geometry. The equilibrium of such systems is characterized by 'typical' microscopic aggregates that already individually satisfy mean field theory and rearrange into each other. For instance, whereas a straight line of single particles constitute one particular connected aggregate that is a possible microscopic realization, aggregates of this maximal length occur extremely rarely and are thus atypical. Many previous works in detail studied several models of specific reorganization mechanisms (e.g., ordinary diffusion, Levy flights or surface diffusion) but it was not well understood how their results depended on the model details. In particular, it was unclear in all of these specific models what a 'typical' aggregate was. This lead to the core question for such reorganizing systems: Which typical microscopic states characterize the macroscopic observables?

 

In a work together with Stefan Großkinsky (now Warwick Mathematics Institute, UK) and Björn Naundorf we studied a general class of reversible aggregate-reorganization processes [3]. Using the broad mathematical perspective of general Markov processes rather than focusing on specific models for the reorganization mechanism, we found that these processes exhibit globally attracting equilibrium distributions that are universal, i.e. identical for large classes of models. As the equilibrium distribution was obtained analytically, it also became clear which microscopic states significantly contribute to the macroscopic one and are thus 'typical'. As a particular application, our results explain and unify several previous works (e.g., from [4] to [5]) and predict the fractal dimension of the aggregates.

 

The unified analysis furthermore suggests a new computational approach for studying reorganization phenomena: To obtain equilibrium properties of any such process, computationally expensive reorganization dynamics such as random walks, surface diffusion or Levy flights can be replaced by more efficient yet simpler methods.

 

 

Efficient Computation of Partition Functions and Graph-Invariant Polynomials. The Tutte polynomial (TP) of a graph, being closely related to different kinds of enumeration problems, arises independently in statistical physics and graph theory. In physics, it equals the partition function of the Potts model, a paradigmatic lattice spin model, and is as such crucial to a theoretical understanding of phase transitions. In graph theory, the TP is a universal chromatic invariant of a graph and yields many other invariants directly relevant to important graph features such as its communication capabilities, which in turn are of interest, e.g., in computer science. How to efficiently compute the TP (and other related functions of graphs) thus is an important issue in graph theory, of practical relevance to computer science, and an outstanding problem in theoretical statistical physics [6]. However, finding the TP is a computationally hard problem: the time to find it generally increases exponentially with the number of edges in a graph. Conventionally, algorithms for its computation were developed with the aim to cover every possible graph, thus including worst case instances. As a result, their actual performance can often be low on specific types of graphs of interest such that solutions to specific problems become restricted to small graph examples [7] or even practically impossible.

 

In this project we are developing a new class of computational methods to find the TP and solve related enumeration problems on classes of graphs [8] that are of immediate practical interest in applications. We take this physics perspective [9-11], developing methods that efficiently exploit the specific properties of large classes of graphs but would loose their advantages if applied to 'worst-case' instances. The new idea is based on the above-mentioned link of the TP of graph theory to partition functions in physics that are termed as simple summations. We interpret the summations as symbolic operators and the expressions occurring during evaluation as elements of an abstract ring that satisfies the ring axioms along with further identification rules. Very recently, we worked out the link between the ring representation and conventional summation over variables that occurs in the partition function using methods from mathematical algebra [12].

 

Using these results from abstract algebra and the physics perspective mentioned above, we are developing graph theoretical algorithms that are based on symbolic summations. The methods are designed such that a resulting algorithm first analyzes and exploits the specific structure of the graph and accordingly represent it in a (close-to) optimal way before performing the actual calculation of the TP.

 

As a first study on chromatic polynomials (special cases of TPs) suggests, such new methods may drastically outperform existing ones on many graphs of practical interest. For instance, although the Potts model has originally been invented in the 1960s to describe phenomena in physically relevant , three-dimensional lattices, three-dimensions could not be accessed so far, neither analytically nor computationally. Using our new method, we now computed antiferromagnetic Potts ground state partition functions of lattices in three dimensions and of disordered versions thereof. Generalization of our current results to full TPs may also have immediate applications to other systems. For instance, one could compute exact partition functions of various ordered and disordered lattices of relevance in physics and possibly access the communication capabilities of complex real world networks via applied graph theory. In summary, taking into account the structure of the specific graphs of interest, usually ignored by conventional methods, and using a symbolic method of computation based on abstract algebra, yields promising results on moderate and large scale enumeration problems, that in part could not be accessed until today.

 

 

[1] A.K. Hartmann and M. Weigt, Phase Transitions in Combinatorial Optimization Problems,
Wiley-VCH (Berlin, 2005).

[2] P. Meakin, Fractals, Scaling and Growth Far from Equilibrium, Cambridge University Press (Cambridge, UK, 1998).

[3] S. Großkinsky, M. Timme, and B. Naundorf, Phys. Rev. Lett. 88 (2002) 245501.

[4] R. Botet and R. Jullien, Phys. Rev. Lett. 55 (1985) 1943.

[5] M. Filoche and B. Sapoval, Phys. Rev. Lett. 85 (2000) 5118.

[6] A. Sokal, The multivariate Tutte polynomial (alias Potts model) for graphs and matroids, in: “Surveys in Combinatorics 2005”, Cambrige University Press (Cambridge, UK, 2005).

[7] P.H. Lundow and K. Markstrom, Research Report 3, Dept. Mathematics, Umea University, Sweden (2002).

[8] A. Andrzejak, Discr. Math.190 (1998) 39; D. Noble, Combin. Prob. Comput. 7 (1998) 307.

[9] M. Mezard et al., Science 297 (2002) 812.

[10] M. Weigt and A. Hartmann, Phys. Rev. Lett. 84 (2000) 6118.

 

[11] M. Mezard, T. Mora, and R. Zecchina, Phys. Rev. Lett. 94 (2005) 197205.

[12] D. Kozen and M. Timme, Technical Report, Cornell University, http://hdl.handle.net/1813/8352 (2007).


Contact:  Marc Timme 

Members working within this Project:

 Nora Molkenthin 
 Denny Fliegner 
 Marc Timme 

Former Members:

 Anna Levina 
 Frank van Bussel 
 Jan Nagler 

Selected Publications:

F. Wolf, R. Engelken, M. Puelma Touzel, J.D. Flórez Weidinger, and A. Neef (2014).
Dynamical models of cortical circuits
Current Opinion in Neurobiology 25:228-236.

J. Nagler, A. Levina, and M. Timme (2011).
Impact of single links in competitive percolation
Nature Physics 7:265. download file

F. van Bussel, C. Ehrlich, D. Fliegner, S. Stolzenberg, and M. Timme (2010).
Chromatic polynomials of random graphs
J. Phys. A: Math. Theor. 43:175002. download file

D. Battaglia (2009).
Neuron-less Neural-like Networks with Exponential Association Capacity at Tabula Rasa
In: Methods and Models in Artificial and Natural Computation, vol. 1 (IWINAC 2009), edited by J. Mira, J.M Ferrandez, J. R. Alvarez et al.. Springer-Verlag, Berlin-Heidelberg, pages 184-194. download file

M. Timme, F. van Bussel, D. Fliegner, and S. Stolzenberg (2009).
Counting Complex Disordered States by Efficient Pattern Matching: Chromatic Polynomials and Potts Partition Functions
New J. Phys. 11:023001. download file

D. Kozen, and M. Timme (2008).
Indefinite Summation and the Kronecker Delta
Technical Report, Cornell University.

S. Großkinsky, M. Timme, and B. Naundorf (2002).
Universal Attractors of Reversible Aggregate-Reorganization Processes
Phys. Rev. Lett. 88(24):245501.