The falling raindrop, revisited (2009)
I reconsider the problem of a raindrop falling through mist, collecting mass, and generalize it to allow an arbitrary power-law form for the accretion rate. I show that the coupled differential...
When is a Riesz distribution a complex measure? (2009)
Let R_\alpha be the Riesz distribution on a simple Euclidean Jordan algebra, parametrized by the complex number \alpha. I give an elementary proof of the necessary and sufficient condition for...
New critical exponents for percolation and the random-cluster model (2009)
Deng, Youjin, Zhang, Wei, Garoni, Timothy M., Sokal, Alan D., Sportiello, Andrea
We introduce several infinite families of new critical exponents for the random-cluster model, and give heuristic scaling arguments determining all but one of these exponents as a function of q in...
Real-variables characterization of generalized Stieltjes functions (2009)
We give a simple proof for a characterization of Stieltjes functions, first obtained by Widder in 1938, in terms of inequalities for their derivatives on (0,\infty). By the same method, we also...
A ridiculously simple and explicit implicit function theorem (2009)
I show that the general implicit-function problem (or parametrized fixed-point problem) in one complex variable has an explicit series solution given by a trivial generalization of the Lagrange...
Caracciolo, Sergio, Masbaum, Gregor, Sokal, Alan D., Sportiello, Andrea
Consider the problem of determining whether there exists a spanning hypertree in a given k-uniform hypergraph. This problem is trivially in P for k=2, and is NP-complete for k>= 4, whereas for k=3,...
Jackson, Bill, Procacci, Aldo, Sokal, Alan D.
We find zero-free regions in the complex plane at large |q| for the multivariate Tutte polynomial (also known in statistical mechanics as the Potts-model partition function) Z_G(q,w) of a graph G...
Caracciolo, Sergio, Sportiello, Andrea, Sokal, Alan D.
We prove, by simple manipulation of commutators, two noncommutative generalizations of the Cauchy-Binet formula for the determinant of a product. As special cases we obtain elementary proofs of the...
The chromatic polynomial P_G(q) of a loopless graph G is known to be nonzero (with explicitly known sign) on the intervals (-\infty,0), (0,1) and (1,32/27]. Analogous theorems hold for the flow...
Scott, Alexander D., Sokal, Alan D.
We prove some variants of the exponential formula and apply them to the multivariate Tutte polynomials (also known as Potts-model partition functions) of graphs. We also prove some further identities...
Phase transition in the 3-state Potts antiferromagnet on the diced lattice (2008)
Kotecky, Roman, Salas, Jesus, Sokal, Alan D.
We prove that, contrary to theoretical expectations, the 3-state Potts antiferromagnet on the diced lattice (dual of the Kagome lattice) has a phase transition at nonzero temperature. We then present...
Some Comments on Multigrid Methods for Computing Propagators (2007)
I make three conceptual points regarding multigrid methods for computing propagators in lattice gauge theory: 1) The class of operators handled by the algorithm must be stable under coarsening. 2)...
We derive some new structural results for the transfer matrix of square-lattice Potts models with free and cylindrical boundary conditions. In particular, we obtain explicit closed-form expressions...
Grassmann Integral Representation for Spanning Hyperforests (2007)
Caracciolo, Sergio, Sokal, Alan D., Sportiello, Andrea
Given a hypergraph G, we introduce a Grassmann algebra over the vertex set, and show that a class of Grassmann integrals permits an expansion in terms of spanning hyperforests. Special cases provide...
Dynamic critical behavior of the Chayes-Machta-Swendsen-Wang algorithm (2007)
Deng, Youjin, Garoni, Timothy M., Machta, Jonathan, Ossola, Giovanni, Polin, Marco, Sokal, Alan D.
We study the dynamic critical behavior of the Chayes-Machta dynamics for the Fortuin-Kasteleyn random-cluster model, which generalizes the Swendsen-Wang dynamics for the q-state Potts model to...
De La Rue, Thierry, Fernandez, Roberto, Sokal, Alan D.
Motivated by the Dobrushin uniqueness theorem in statistical mechanics, we consider the following situation: Let \alpha be a nonnegative matrix over a finite or countably infinite index set X, and...
Dynamic critical behavior of the worm algorithm for the Ising model (2007)
Deng, Youjin, Garoni, Timothy M., Sokal, Alan D.
We study the dynamic critical behavior of the worm algorithm for the two- and three-dimensional Ising models, by Monte Carlo simulation. The autocorrelation functions exhibit an unusual...
Maxmaxflow and counting subgraphs (2007)
We introduce a new graph invariant \Lambda(G) that we call maxmaxflow, and put it in the context of some other well-known graph invariants, notably maximum degree and its relatives. We prove the...
Critical speeding-up in a local dynamics for the random-cluster model (2007)
Deng, Youjin, Garoni, Timothy M., Sokal, Alan D.
We study the dynamic critical behavior of the local bond-update (Sweeny) dynamics for the Fortuin-Kasteleyn random-cluster model in dimensions d=2,3, by Monte Carlo simulation. We show that, for a...
Deng, Youjin, Garoni, Timothy M., Sokal, Alan D.
We present Monte Carlo simulations of the spanning-forest model (q \to 0 limit of the ferromagnetic Potts model) in spatial dimensions d=3,4,5. We show that, in contrast to the two-dimensional case,...
Cluster simulations of loop models on two-dimensional lattices (2006)
Deng, Youjin, Garoni, Timothy M., Guo, Wenan, Blote, Henk W. J., Sokal, Alan D.
We develop cluster algorithms for a broad class of loop models on two-dimensional lattices, including several standard O(n) loop models at n \ge 1. We show that our algorithm has little or no...
Spanning forests and the q-state Potts model in the limit q \\to 0 (2005)
Jacobsen, Jesper Lykke, Salas, Jesus, Sokal, Alan D.
We study the q-state Potts model with nearest-neighbor coupling v=e^{\\beta J}-1 in the limit q,v \\to 0 with the ratio w = v/q held fixed. Combinatorially, this limit gives rise to the generating...
The multivariate Tutte polynomial (alias Potts model) for graphs and matroids (2005)
The multivariate Tutte polynomial (known to physicists as the Potts-model partition function) can be defined on an arbitrary finite graph G, or more generally on an arbitrary matroid M, and encodes...
Spanning forests and the q-state Potts model in the limit q \\to 0 (2005)
Jacobsen, Jesper Lykke, Salas, Jesus, Sokal, Alan D.
We study the q-state Potts model with nearest-neighbor coupling v=e^{\\beta J}-1 in the limit q,v \\to 0 with the ratio w = v/q held fixed. Combinatorially, this limit gives rise to the generating...
Spanning forests and the q-state Potts model in the limit q \\to 0 (2005)
Jacobsen, Jesper Lykke, Salas, Jesus, Sokal, Alan D.
We study the q-state Potts model with nearest-neighbor coupling v=e^{\\beta J}-1 in the limit q,v \\to 0 with the ratio w = v/q held fixed. Combinatorially, this limit gives rise to the generating...
Correction-to-scaling exponents for two-dimensional self-avoiding walks (2004)
Caracciolo, Sergio, Guttmann, Anthony J., Jensen, Iwan, Pelissetto, Andrea, Rogers, Andrew N., Sokal, Alan D.
We study the correction-to-scaling exponents for the two-dimensional self-avoiding walk, using a combination of series-extrapolation and Monte Carlo methods. We enumerate all self-avoiding walks up...
Fermionic field theory for trees and forests (2004)
Caracciolo, Sergio, Jacobsen, Jesper Lykke, Saleur, Hubert, Sokal, Alan D., Sportiello, Andrea
We prove a generalization of Kirchhoff's matrix-tree theorem in which a large class of combinatorial objects are represented by non-Gaussian Grassmann integrals. As a special case, we show that...
Ossola, Giovanni, Sokal, Alan D.
We show that linear congruential pseudo-random-number generators can cause systematic errors in Monte Carlo simulations using the Swendsen-Wang algorithm, if the lattice size is a multiple of a very...
Ossola, Giovanni, Sokal, Alan D.
We have performed a high-precision Monte Carlo study of the dynamic critical behavior of the Swendsen-Wang algorithm for the three-dimensional Ising model at the critical point. For the dynamic...
Spanning forests and the q-state Potts model in the limit q \to 0 (2004)
Jacobsen, Jesper Lykke, Salas, Jesus, Sokal, Alan D.
We study the q-state Potts model with nearest-neighbor coupling v=e^{\beta J}-1 in the limit q,v \to 0 with the ratio w = v/q held fixed. Combinatorially, this limit gives rise to the generating...
Homogeneous multivariate polynomials with the half-plane property (2004)
Young-bin Choe, James G. Oxley, Alan D. Sokal, David G. Wagner
A polynomial P in n complex variables is said to have the “half-plane property” (or Hurwitz property) if it is nonvanishing whenever all the variables lie in the open right half-plane. Such...
Alan D. Sokal, Edited Garrett Fagan
The human understanding is not composed of dry light, but is subject to influence from the will and the emotions, a fact that creates fanciful knowledge; man prefers to believe what he wants to be...
The repulsive lattice gas, the independent-set polynomial, and the Lov\'asz local lemma (2003)
Scott, Alexander D., Sokal, Alan D.
We elucidate the close connection between the repulsive lattice gas in equilibrium statistical mechanics and the Lovasz local lemma in probabilistic combinatorics. We show that the conclusion of the...
The Brown-Colbourn conjecture on zeros of reliability polynomials is false (2003)
We give counterexamples to the Brown-Colbourn conjecture on reliability polynomials, in both its univariate and multivariate forms. The multivariate Brown-Colbourn conjecture is false already for the...
Numerical Computation of \prod_{n=1}^\infty (1 - tx^n) (2002)
I present and analyze a quadratically convergent algorithm for computing the infinite product \prod_{n=1}^\infty (1 - tx^n) for arbitrary complex t and x satisfying |x| < 1, based on the identity...
Jacobsen, Jesper Lykke, Salas, Jesús, Sokal, Alan D.
We study the chromatic polynomial P_G(q) for m \times n triangular-lattice strips of widths m
Homogeneous multivariate polynomials with the half-plane property (2002)
Choe, Young-Bin, Oxley, James G., Sokal, Alan D., Wagner, David G.
A polynomial P in n complex variables is said to have the "half-plane property" (or Hurwitz property) if it is nonvanishing whenever all the variables lie in the open right half-plane. Such...
Homogeneous with the Multivariate Polynomials Half-Plane Property (2002)
Young-bin Choe, James G. Oxley, Alan D. Sokal, David G. Wagner
A polynomial P in n complex variables is said to have the "half-plane property " (or Hurwitz property) if it is nonvanishing whenever all the variables lie in the open right half-plane....
Unusual corrections to scaling in the 3-state Potts antiferromagnet on a square lattice (2001)
Cardy, John, Jacobsen, Jesper Lykke, Sokal, Alan D.
At zero temperature, the 3-state antiferromagnetic Potts model on a square lattice maps exactly onto a point of the 6-vertex model whose long-distance behavior is equivalent to that of a free scalar...
On the Chromatic Roots of Generalized Theta Graphs (2001)
Jason Brown, Carl Hickman, Alan D. Sokal, David G. Wagner
The generalized theta graph \Theta s 1;:::;s k consists of a pair of endvertices joined by k internally disjoint paths of lengths s 1; : : : ; s k 1. We prove that the roots of the chromatic...
Chromatic roots are dense in the whole complex plane (2000)
I show that the zeros of the chromatic polynomials P_G(q) for the generalized theta graphs \Theta^{(s,p)} are, taken together, dense in the whole complex plane with the possible exception of the disc...
On the chromatic roots of generalized theta graphs (2000)
Brown, Jason, Hickman, Carl, Sokal, Alan D., Wagner, David G.
The generalized theta graph \Theta_{s_1,...,s_k} consists of a pair of endvertices joined by k internally disjoint paths of lengths s_1,...,s_k \ge 1. We prove that the roots of the chromatic...
Sokal, Alan D., Starinets, Andrei O.
We compute the phase diagram in the N\to\infty limit for lattice RP^{N-1}, CP^{N-1} and QP^{N-1} sigma-models with the quartic action, and more generally for mixed isovector/isotensor models. We show...
We study the chromatic polynomials (= zero-temperature antiferromagnetic Potts-model partition functions) P_G(q) for m \times n rectangular subsets of the square lattice, with m \le 8 (free or...
I review recent results and unsolved problems concerning the hard-core lattice gas and the q-coloring model (antiferromagnetic Potts model at zero temperature). For each model, I consider its...
Chromatic Polynomials, Potts Models and All That (1999)
The q-state Potts model can be defined on an arbitrary finite graph, and its partition function encodes much important information about that graph, including its chromatic polynomial, flow...
Bounds on the Complex Zeros of (Di)Chromatic Polynomials and Potts-Model Partition Functions (1999)
I show that there exist universal constants $C(r) < \infty$ such that, for all loopless graphs $G$ of maximum degree $\le r$, the zeros (real or complex) of the chromatic polynomial $P_G(q)$ lie in...
Universal Amplitude Ratios in the Critical Two-Dimensional Ising Model on a Torus (1999)
Using results from conformal field theory, we compute several universal amplitude ratios for the two-dimensional Ising model at criticality on a symmetric torus. These include the correlation-length...
Antiferromagnetic Potts Models on the Square Lattice: A High-Precision Monte Carlo Study (1998)
Ferreira, Sabino José, Sokal, Alan D.
We study the antiferromagnetic q-state Potts model on the square lattice for q=3 and q=4, using the Wang-Swendsen-Kotecky (WSK) Monte Carlo algorithm and a powerful finite-size-scaling extrapolation...
We prove that the q-state Potts antiferromagnet on a lattice of maximum coordination number r exhibits exponential decay of correlations uniformly at all temperatures (including zero temperature)...
Multi-Grid Monte Carlo via $XY$ Embedding. II. Two-Dimensional $SU(3)$ Principal Chiral Model (1996)
Mana, Gustavo, Pelissetto, Andrea, Sokal, Alan D.
We carry out a high-precision simulation of the two-dimensional $SU(3)$ principal chiral model at correlation lengths $\xi$ up to $\sim 4 \times 10^5$, using a multi-grid Monte Carlo (MGMC) algorithm...
Logarithmic Corrections and Finite-Size Scaling in the Two-Dimensional 4-State Potts Model (1996)
We analyze the scaling and finite-size-scaling behavior of the two-dimensional 4-state Potts model. We find new multiplicative logarithmic corrections for the susceptibility, in addition to the...
We have performed a high-precision Monte Carlo study of the dynamic critical behavior of the Swendsen-Wang algorithm for the two-dimensional 3-state Potts model. We find that the Li-Sokal bound...
Mendes, Tereza, Pelissetto, Andrea, Sokal, Alan D.
We introduce a variant of the multi-grid Monte Carlo (MGMC) method, based on the embedding of an $XY$ model into the target model, and we study its mathematical properties for a variety of nonlinear...
We prove that the $q$-state Potts antiferromagnet on a lattice of maximum coordination number $r$ exhibits exponential decay of correlations uniformly at all temperatures (including zero temperature)...
Mana, Gustavo, Pelissetto, Andrea, Sokal, Alan D.
We carry out a high-precision simulation of the two-dimensional $SU(3)$ principal chiral model at correlation lengths $\xi$ up to $\approx\! 4 \times 10^5$, using a multi-grid Monte Carlo (MGMC)...
Caracciolo, Sergio, Edwards, Robert G., Pelissetto, Andrea, Sokal, Alan D.
We reply to criticism by Patrascioiu and Seiler [hep-lat/9502019] of our results [Phys. Rev. Lett. 75, 1891 (1995), hep-lat/9411009] on asymptotic scaling in the two-dimensional $O(3)$...
Monte Carlo Methods in Statistical Mechanics: Foundations and New Algorithms (1996)
Introduction The goal of these lectures is to give an introduction to current research on Monte Carlo methods in statistical mechanics and quantum field theory, with an emphasis on: 1) the conceptual...
Mana, Gustavo, Mendes, Tereza, Pelissetto, Andrea, Sokal, Alan D.
We introduce a new and very convenient approach to multi-grid Monte Carlo (MGMC) algorithms for general nonlinear $\sigma$-models: it is based on embedding an $XY$ model into the given...
Dynamic Critical Behavio(u)r of a Cluster Algorithm for the Ashkin--Teller Model (1995)
We study the dynamic critical behavior of a Swendsen--Wang--type algorithm for the Ashkin--Teller model. We find that the Li--Sokal bound on the autocorrelation time ($\tau_{{\rm int},{\cal E}} \ge...
Monte Carlo Methods for the Self-Avoiding Walk (1995)
This article is a pedagogical review of Monte Carlo methods for the self-avoiding walk, with emphasis on the extraordinarily efficient algorithms developed over the past decade. Many more details can...
Caracciolo, Sergio, Edwards, Robert G., Mendes, Tereza, Pelissetto, Andrea, Sokal, Alan D.
We have computed the four-loop contribution to the beta-function and to the anomalous dimension of the field for the two-dimensional lattice $N$-vector model. This allows the determination of the...
Campostrini, Massimo, Cucchieri, Attilio, Mendes, Tereza, Pelissetto, Andrea, Rossi, Paolo, Sokal, Alan D., ...
In this talk we present the exact solution of the most general one-dimensional $O(N)$-invariant spin model taking values in the sphere $S^{N-1}$, with nearest-neighbour interactions, and we discuss...
Cucchieri, Attilio, Mendes, Tereza, Pelissetto, Andrea, Sokal, Alan D.
We solve exactly the general one-dimensional $O(N)$-invariant spin model taking values in the sphere $S^{N-1}$, with nearest-neighbor interactions, in finite volume with periodic boundary conditions,...
Multi-Grid Monte Carlo. IV. One-Dimensional $O(4)$-Symmetric Nonlinear $\sigma$-Model (1995)
Mendes, Tereza, Sokal, Alan D.
We study the dynamic critical behavior of the multi-grid Monte Carlo (MGMC) algorithm with piecewise-constant interpolation and a W-cycle, applied to the one-dimensional $O(4)$-symmetric nonlinear...
New Method for the Extrapolation of Finite-Size Data to Infinite Volume (1994)
Caracciolo, Sergio, Edwards, Robert G., Ferreira, Sabino J., Pelissetto, Andrea, Sokal, Alan D.
We present a simple and powerful method for extrapolating finite-volume Monte Carlo data to infinite volume, based on finite-size-scaling theory. We discuss carefully its systematic and statistical...
Two-Dimensional $O(3)$ $\sigma$-Model up to Correlation Length $10^5$ (1994)
Caracciolo, Sergio, Edwards, Robert G., Pelissetto, Andrea, Sokal, Alan D.
We carry out a high-precision Monte Carlo simulation of the two-dimensional $O(3)$-invariant $\sigma$-model at correlation lengths $\xi$ up to $\sim 10^5$. Our work employs a new and powerful method...
Asymptotic Scaling in the Two-Dimensional $O(3)$ $\sigma$-Model at Correlation Length $10^5$ (1994)
Caracciolo, Sergio, Edwards, Robert G., Pelissetto, Andrea, Sokal, Alan D.
We carry out a high-precision Monte Carlo simulation of the two-dimensional $O(3)$-invariant $\sigma$-model at correlation lengths $\xi$ up to $\sim 10^5$. Our work employs a new and powerful method...
Li, Bin, Madras, Neal, Sokal, Alan D.
We make a high-precision Monte Carlo study of two- and three-dimensional self-avoiding walks (SAWs) of length up to 80000 steps, using the pivot algorithm and the Karp-Luby algorithm. We study the...
Finite-Size Scaling at $\xi/L \gg 1$ (1994)
Caracciolo, Sergio, Edwards, Robert G., Ferreira, Sabino José, Pelissetto, Andrea, Sokal, Alan D.
We present a simple and powerful method for extrapolating finite-volume Monte Carlo data to infinite volume, based on finite-size-scaling theory. We discuss carefully its systematic and statistical...
Antiferromagnetic Potts Models on the Square Lattice (1994)
Ferreira, Sabino José, Sokal, Alan D.
We study the antiferromagnetic $q$-state Potts model on the square lattice for $q=3$ and $q=4$, using the Wang-Swendsen-Koteck\'y Monte Carlo algorithm and a new finite-size-scaling extrapolation...
Monte Carlo Methods for the Self-Avoiding Walk (1994)
This article is a pedagogical review of Monte Carlo methods for the self-avoiding walk, with emphasis on the extraordinarily efficient algorithms developed over the past decade.
New Universality Classes for Two-Dimensional $\sigma$-Models (1993)
Caracciolo, Sergio, Edwards, Robert G., Pelissetto, Andrea, Sokal, Alan D.
We argue that the two-dimensional $O(N)$-invariant lattice $\sigma$-model with mixed isovector/isotensor action has a one-parameter family of nontrivial continuum limits, only one of which is the...
A General Limitation on Monte Carlo Algorithms of Metropolis Type (1993)
Caracciolo, Sergio, Pelissetto, Andrea, Sokal, Alan D.
We prove that for any Monte Carlo algorithm of Metropolis type, the autocorrelation time of a suitable ``energy''-like observable is bounded below by a multiple of the corresponding ``specific...
Some Comments on Multigrid Methods for Computing Propagators (1993)
I make three conceptual points regarding multigrid methods for computing propagators in lattice gauge theory: 1) The class of operators handled by the algorithm must be stable under coarsening. 2)...
Static Scaling Behavior of High-Molecular-Weight Polymers in Dilute Solution: A Reexamination (1993)
Previous theories of dilute polymer solutions have failed to distinguish clearly between two very different ways of taking the long-chain limit: (I) $N \to\infty$ at fixed temperature $T$, and (II)...
Comment on ``Antiferromagnetic Potts Models'' (1993)
We show that the Wang-Swendsen-Koteck\'y algorithm for antiferromagnetic $q$-state Potts models is nonergodic at zero temperature for $q=3$ on periodic $3m \times 3n$ lattices where $m,n$ are...
New Lower Bounds on the Self-Avoiding-Walk Connective Constant (1993)
Hara, Takashi, Slade, Gordon, Sokal, Alan D.
We give an elementary new method for obtaining rigorous lower bounds on the connective constant for self-avoiding walks on the hypercubic lattice $Z^d$. The method is based on loop erasure and...
New Lower Bounds on the Self-Avoiding-Walk Connective Constant (1993)
Takashi Hara, Gordon Slade, Alan D. Sokal
We give an elementary new method for obtaining rigorous lower bounds on the connective constant for self-avoiding walks on the hypercubic lattice Z d . The method is based on loop erasure and...
Static Scaling Behavior of High-Molecular-Weight Polymers in Dilute Solution: A Reexamination (1993)
A Reexamination, Alan D. Sokal
Previous theories of dilute polymer solutions have failed to distinguish clearly between two very different ways of taking the long-chain limit: (I) N ! 1 at fixed temperature T , and (II) N ! 1, T !...
Wolff-Type Embedding Algorithms for General Nonlinear $\sigma$-Models (1992)
Caracciolo, Sergio, Edwards, Robert G., Pelissetto, Andrea, Sokal, Alan D.
We study a class of Monte Carlo algorithms for the nonlinear $\sigma$-model, based on a Wolff-type embedding of Ising spins into the target manifold $M$. We argue heuristically that, at least for an...
Multi-Grid Monte Carlo III. Two-Dimensional O(4)-Symmetric Nonlinear $\sigma$-Model (1992)
Edwards, Robert G., Ferreira, Sabino José, Goodman, Jonathan, Sokal, Alan D.
We study the dynamic critical behavior of the multi-grid Monte Carlo (MGMC) algorithm with piecewise-constant interpolation applied to the two-dimensional O(4)-symmetric nonlinear $\sigma$-model [=...