last updated: 9/16

Projects

Banded states and limit shapes in the Ising model, in progress
Integrability for resistor networks, in progress
Phase transitions in the laplacian determinant, in progress
Greens function on the branched cover of Z^2, with D. Wilson, in progress
Dimers and the Beauville system, with A. Goncharov, in progress

Publications

The six-vertex model and Schramm-Loewner evolution with J. Miller, S. Sheffield, D. Wilson

Bipolar orientations on planar maps and SLE(12) with J. Miller, S. Sheffield, D. Wilson

Bipodal structure in oversaturated random graphs with C. Radin, K. Ren. L. Sadun

Permutations with fixed pattern densities with C. Radin, D. Kral, P. Winkler

Fixed-energy harmonic functions with A. Abrams

Right-angled hexagon tilings of the hyperbolic plane

On the space of circular planar networks with D. Wilson

On the asymptotics of constrained exponential random graphs with M. Yin.

Multipodal structure and phase transitions in large constrained graphs with C. Radin, K. Ren, L. Sadun. Given a large graph with fixed number of edges and fixed subgraph density of k-stars, we show that the graph is with high probability multipodal, that is, has the structure of a random block model.

On the asymptotics of dimers on tori with N. Sun, D. Wilson Computing the asymptotics of the partition function for the dimer model on a large torus graph.

Random curves on surfaces induced from the Laplacian determinant with A. Kassel. How does one define a spanning tree on a graph embedded on a curved surface?

Random two-component spanning forests with A. Kassel and W. Wu. Ann. Inst. Henri Poincaré Probab. Stat. 51 (2015), no. 4, 1457–1464 What are the sizes of the components?

Principal minors and rhombus tilings with Robin Pemantle. J. Phys. A 47 (2014), no. 47, 474010, 17 pp. Minimal parametrizing sets for the principal minors of a matrix and their cluster structure.

Double-dimers, the Ising model and the hexagon recurrence with Robin Pemantle. J. Combin. Theory Ser. A 137 (2016) A study of a recurrence relation arising from and generalizing the Ising model Yang-Baxter relation.

Conformal invariance of loops in the double-dimer model CMP 2 (2014). We show that the loops in a superposition of two random dimer coverings are conformally invariant.

Spanning trees of graphs on surfaces and the intensity of loop-erased random walk on Z^2 with D. Wilson. How to compute the probability that the loop-erased random walk in Z^2 goes through a specified edge. J. Amer. Math. Soc. 28 (2015).

Dimers and cluster integrable systems with A. Goncharov. Associated to a bipartite dimer model on a torus is an algebraic integrable Hamiltonian system. Ann Sci. ENS. 46 (2013)

Double-dimer pairings and skew Young diagrams, with D. Wilson The number of tilings of skew Young diagrams with ribbon tiles satisfying certain constraints. These arise in the combinatorics of double-dimer pairing probabilities. EJP, 18 (2011), #P130

Hausdorff dimension of the multiplicative golden mean shift , with Y. Peres and B. Solomyak, CRAS 349, 11–12, 2011, Pages 625–628

Hausdorff dimension for fractals invariant under the multiplicative integers , with Y. Peres and B. Solomyak. What is the dimension of the set of binary sequences for which x_k x_{2k}=0? And similar constructions. ETDS 32 (2012), pp 1567-1584

Spanning forests and the vector bundle laplacian The matrix-tree theorem is extended to the laplacian for a rank-1 or rank-2 connection on a graph. Ann. Prob. Volume 39, Number 5 (2011), 1621-2041

Combinatorics of Tripartite boundary connections for trees and dimers with D. Wilson. How to reconstruct a graph from its boundary resistances. Elec. J. Comb, 16, paper 112 (2009)

Les Houches lectures on the dimer model Exact Methods in Low-dimensional Statistical Physics and Quantum Computing, J. Jacobsen and S. Ouvry, eds., Oxford Univ. Press 2010.

Monotone loop models and rational resonance, with Alan Hammond, We study the orbit structure of a random dynamical system on the square grid on a torus obtained by choosing at each vertex a random up- or right-neighbor. PTRF 2011, Volume 150, pp 613-633.

Boundary partitions in trees and dimers , with David Wilson. Take a random spanning forest on a planar graph in which every component touches the outer boundary. We compute the connection probabilities of boundary vertices, in terms of electrical properties of the graph. A similar calculation works for the ``double-dimer'' model.

Lectures on dimers Statistical mechanics, 191--230, IAS/Park City Math. Ser., 16, Amer. Math. Soc., Providence, RI, 2009. Lecture notes for a course on the dimer model.

On the characterization of expansion maps for self-affine tilings , with B. Solomyak. Which linear maps can be the expansion map for a self-affine tiling of R^n? We give a necessary condition (conjecturally sufficient) in the case of diagonalizable maps. Discrete & Computational Geometry (2010), 43, pp 577-593

Branched polymers , with Peter Winkler. A branched polymer is a connected collection of $n$ disks with disjoint interiors. We compute the volume of the configuration space of branched polymers in $2$ and $3$ dimensions, as well as providing an algorithm for exact simulation. Amer. Math. Monthly,

Height fluctuations in the honeycomb dimer model Height fluctuations in the scaling limit of the dimer model (lozenge tiling model) for fairly general boundary conditions are shown to be given by a Gaussian free field, or more precisely, the image of a Gaussian free field under a certain diffeomorphism. CMP, 2008


Limit shapes and the complex Burgers equation , with Andrei Okounkov. Limit shape surfaces arising in the dimer model give a neat family of surfaces in R^3 described by an exactly solvable PDE. Algebraicity and facet formation. Acta Math.


Andrei Okounkov's work on the dimer model , A brief survey of Andrei Okounkov's work on the dimer model and random surfaces. Appeared in the PIMS newsletter volume 10, issue 2 (Winter 2007).


Dimers and Amoebae , with Scott Sheffield and Andrei Okounkov, Ann. Math. 163 (2006), no. 3, 1019--1056. Associated to each periodic bipartite planar graph is a plane curve P(z,w)=0. The "amoeba" of this plane curve describes the phase space of ergodic Gibbs measures on dimer configurations. Measures are gaseous, liquid or frozen depending on whether you are inside a bounded component of the complement, inside the amoeba itself, or outside the amoeba.


Planar dimers and Harnack curves with Andrei Okounkov, Duke Math. J. 131 (2006), no. 3, 499--524. We use dimer technology to classify the set of "Harnack curves". These classical curves are in some sense the "nicest" family of real plane curves. They can be thought of as two-variable analogues of one variable real polynomials with only real, negative roots. The simplest definition is that they are curves with the property that the area of their amoeba is maximal for their given degree (pi^2 times the degree).


Dimer problems an introduction to dimers written for the Encyclopedia of mathematical physics.


Topological mixing for substitutions on two letters , with Boris Solomyak and Lorenzo Sadun. ETDS, 25 (2005) 1919-1934. We give necessary and sufficient conditions for a substitution on two letters to be topologically mixing.


What is....a dimer? Notices of the AMS 52 (2005), 342-343.


Rhombic embeddings of planar graphs, with Jean-Marc Schlenker. TAMS 357 (2005), 3443-3458. Given a planar graph, all of whose faces are of degree 4, is there an embedding in R^2 in which every edge has length 1? We provide a complete answer, as well as a description of the set of all such embeddings.


Dimers, tilings and trees with Scott Sheffield. JCTB 92 (2004), 295-317. Generalizing the Smith diagram for an electrical network, we show how to associate to a "discrete analytic" function on a bipartite planar graph a tiling of a region with convex polygons. This also generalizes the results of the paper "Tilings and discrete Dirichlet functions", below.


Critical resonance in the non-intersecting lattice paths model , with David Wilson, PTRF 130 (2004) 289-318. We study the phase transition in the honeycomb dimer model (equivalently, monotone non-intersecting lattice path model). At the critical point the system has a strong long-range dependence; in particular, periodic boundary conditions give rise to a ``resonance'' phenomenon, where the partition function and other properties of the system depend sensitively on the shape of the domain.


Constructing rational maps from subdivision rules, with J. W. Cannon, W. J. Floyd, W. R. Parry. Conf. Geom. Dyn. 7 (2003), 76--102. A subdivision rule is a finite set S of disks and a combinatorial rule for subdividing each of them into copies of disks in S. Can such a subdivision rule (which is determined by a finite amount of combinatorial information) be realized by a conformal dynamical system? Under certain restrictive hypotheses, it can even be realized by a rational mapping.


Pavages, arbres, et labyrinths al\'eatoires, with W. Werner, Images des Maths, 2003.


The Laplacian and Dirac operators on critical planar graphs , Inventiones 150 (2002),409-439. On a periodic planar graph whose edge weights satisfy a certain simple geometric condition, the discrete Laplacian and Dirac operators have the amazing property that their determinants and inverses only depend on the local geometry of the graph. We relate the logarithm of the determinants to the volume plus mean curvature of an associated hyperbolic ideal polyhedron.


An introduction to the dimer model , lecture notes for a short course at the ICTP, May, 2002.


The low-temperature expansion of the Wulff crystal in the 3D Ising model , with Raphael Cerf, Comm. Math. Phys 222 (2001), 147-179. We compute the asymptotic shape of a plane partition of n, as n->infinity. We also compute the Wulff shape to order epsilon in the 3D Ising model at temperature epsilon, as epsilon->0.


Dominos and the Gaussian free field , Ann. Prob. 29, no. 3 (2001), 1128-1137. We show that the height function (see below) on a random domino tiling of a simply connected region has a scaling limit (when the lattice spacing tends to zero) which is the ``massless free field," a conformally invariant Gaussian process whose coefficients in the eigenbasis of the Dirichlet Laplacian are independent Gaussians. This paper uses the main result of the paper, "Conformal invariance of domino tiling", below.


The asymptotic determinant of the discrete Laplacian Acta Math 185 (2000) no. 2, 239-286. We compute the asymptotic form of the determinant of the Laplacian on a sequence of subgraphs of (1/n)Z^2 converging to a rectilinear region U. This formula, and the connection between the Laplacian determinant and the uniform spanning tree process, is used to show that the expected length of the loop-erased random walk (the branch of the uniform spanning tree) of diameter n is n^(5/4), a result predicted by physicists in 1992.


Conformal invariance of domino tiling Ann. Prob. 28 (2000) no. 2, 759-795. A domino tiling of the plane can be thought of as a map h from Z^2 to Z with the property that around each lattice square the four values are four consecutive integers n,n+1,n+2,n+3: the dominos cross exactly those edges whose height difference is three. We show that this ``height function'' h on a random domino tiling of (1/n)Z^2 has a distribution which is conformally invariant in the scaling limit n->infinity.


The planar dimer model with boundary: a survey Directions in mathematical quasicrystals, 307-328, CRM Monogr. Ser., 13, Amer. Math. Soc., Providence, RI, 2000. A survey of recent mathematical work on the planar dimer model.


Long-range properties of spanning trees in Z^2 , J. Math. Phys. 41 (2000) 1338-1363. We prove a number of conformal invariance properties of spanning trees in Z^2. In particular we show that the meeting point of the tree branches issued from three boundary points has a distribution which is conformally invariant in the scaling limit. We also compute asymptotic crossing probabilities for rectangles and annuli and show that they are also conformally invariant.


Trees and Matchings (with J. Propp, D. Wilson), Elec. J. Comb. 7 (2000), Research Paper 25. For the spanning tree model on any directed, weighted, planar graph we construct a bijection with the dimer model on a related graph. This bijection, which generalizes that of Temperley, can be used to compute local statistics in the spanning tree model as well as ``winding numbers" of the tree branches. Conversely, a dimer model which arises from a spanning tree model can be sampled quickly, a nontrivial problem for general dimer models.


Dimères et arbres couvrants , Mathématique et physique, 1--14, SMF Journ. Annu., 1999, Soc. Math. France, Paris, 1999. An introduction to the planar dimer model and its relation to spanning trees.


Sur la dynamique, la combinatoire et la statistique des pavages , mémoire d'habilitation. A resume of many of the more important papers below.


A variational principle for domino tilings (with Henry Cohn and James Propp) J. Amer. Math. Soc. 14 (2001), no. 2, 297-346 If P_n is a sequence of polyominos in (1/n)Z^2 (each tileable with dominos: 1/n by 2/n and 2/n by 1/n rectangles) which converge to a fixed domain U, in such a way that the rescaled height function on the boundary of P_n converges to a function b on the boundary of U, we give an explicit PDE for the asymptotic form of the height function on a random domino tiling of P_n as n->infinity. This is closely related to the Wulff shape of the Ising model in Z^3 at zero temperature.


Geometry of self-affine tiles II with Jie Lie, R. Strichartz, Y. Wang, Indiana Univ. Math. J. 48 (1999), 25-42. We study the boundary of the convex hull of a self-affine tile in the plane, and show that the extreme points of the convex hull are a Cantor set of dimension zero.


Billiards on rational triangles (with J. Smillie) , Comment. Math. Helv. 75 (2000), 65--108. We construct an algebraic invariant of a rational-angled polygon and use it to find those acute rational triangles which have the "Veech property" (their associated Riemann surface has a large group of affine diffeomorphisms). This has a strong consequence for the billiard flow on these triangles: in every direction the billiard flow is either periodic or uniquely ergodic.


Hyperbolic geometry (with J. Cannon, W. Floyd, W. Parry), Flavors of Geometry, S. Levy, ed., MSRI pubs. number 31, Cambridge Univ. Press. An introduction to hyperbolic geometry, discussing a certain amount of history of hyperbolic space, followed by a discussion of the 6 different models of hyperbolic space and relations between them.


Arithmetic construction of sofic partitions of hyperbolic toral automorphisms (with A. Vershik), Erg. Thy. and Dyn. Syst., 18(1998),357-372. We construct Markov partitions for hyperbolic toral automorphisms using purely algebraic means. This has the advantage over traditional proofs of existence since it is completely concrete.


Local statistics of lattice dimers , Ann. Inst. H. Poincar\'e, Probabilit\'es, 33 (1997)591-618. We show how to compute local statistics for the uniform measure on dimer configurations on a planar graph, using the inverse of Kasteleyn's matrix. We use this to show that the height fluctuations for two points at distance n in a random lozenge tiling of the plane have variance 9*Log(n)/Pi^2. This paper won the Gauthier-Villars prize for the best paper published in this journal in 1997.


Tiling with squares and square-tileable surfaces Most of this paper is subsumed in the following paper:


Tilings and discrete Dirichlet problems , Isr. J. Math 105(1998),61-84. We give a relation between harmonic functions on planar Markov chains and tilings of polygons with trapezoids. This generalizes the classical relation between planar electrical networks and square tilings. Using these methods we classify those Euclidean tori which can be square-tiled.


Tilings of convex polygons, Ann. Inst. Fourier, 47, 3(1997),929-944. Call a polygon rational if the ratio of any two side lengths is rational. If a convex polygon R is tiled with rational polygons then R is itself rational. This extends a result of Dehn which says that a rectangle is square-tileable if and only if its aspect ratio is rational. As an application of this result, we classify the convex polygons which are tileable with triangles whose angles are multiples of Pi/n.


Projecting the one-dimensional Sierpinski gasket , Isr. J. math, 97 (1997),221-238. We study the one-dimensional Lebesgue measure of linear projections of the Cantor set in the plane in base 3 with digits {0,1,i}. We show that the projection in a direction of irrational slope has measure 0. In rational directions p/q the projection has measure 0 unless pq = -1 mod 3, in which case the measure is 1/q.


Tiling a rectangle with the fewest squares, J. Combin. Thy A, 76(1996)272-291. An aXb rectangle is tileable with squares if and only if a/b is rational. Given a rational number p/q in lowest terms, with 1/10 < p/q < 10, we show that C_1 Log(q) tiles are necessary and C_2 Log(q) tiles are sufficient to tile, for universal constants C_1,C_2.


The construction of self-similar tilings , Geom. and Func. Analysis 6,(1996):417-488. Thurston showed that the expansion constant of a self-similar tiling of the plane must be a complex Perron number (algebraic integer strictly larger in modulus than its Galois conjugates except for its complex conjugate). Here we prove that, conversely, for every complex Perron number there exists a self-similar tiling. We also classify the expansion constants for self-similar tilings which have a rotational symmetry of order n.


A group of paths in the plane Trans. AMS 348,(1996):3155-3172. We define a natural product structure on the set of parametrized ``nonbacktracking'' paths in the plane. The product of two paths is simply their concatenation: the second is translated to the end of the first, after which we remove any backtracks. The set of paths thus forms a group, and we classify the finitely generated subgroups of this group. They are free products of free abelian groups and surface groups. The proof uses Rips' classification of groups acting freely on R-trees.


A note on tiling with integer-sided rectangles , J. Combin. Thy A 74, No. 2 (1996):321-332. We give an algorithm for tiling a simple polygon with rectangles, each of which has at least one integer side. This extends the old result of de Bruijn which states that a rectangle R can be tiled with rectangles, each of which has an integer side, if and only if R has an integer side. The algorithm uses nice group, the free product of the circle with itself.


Measures of Full dimension on Affine-Invariant Sets (with Yuval Peres), Erg. Thy. and Dyn. Syst. 16 (1996), 307-323.


Hausdorff dimensions of sofic affine-invariant sets (with Yuval Peres), Isr. J. Math 94(1996):157-178.


Inflationary tilings with a similarity structure. Comment. Math. Helv. 69 (1994):169-198. These are self-similar tilings with a finite number of tile types up to complex affine maps (translations and rotations and homotheties), rather than just translations. If one assumes that the tiling has a finite number of local configurations (up to complex affine maps) then the tiling must be algebraic: the expansion constant is an algebraic number and the complex affine maps between tiles are algebraic as well (after a linear coordinate change). The proof uses the differentiability almost everywhere of a quasiconformal mapping.


Tiling a Polygon with Parallelograms, Algorithmica 9 (1993): 382-397. We present an algorithm for tiling a polygon with parallelograms or determining that one does not exist.


Rigidity of planar tilings, Invent. Math.107 (1992):637-651. A tile is a set which is the closure of its interior. If translates of a finite set of tiles in the plane can tile a neighborhood of the unit disk in an infinite number of distinct ways, then in one of those ways the tile boundaries contain a line segment running completely through the disk (a chord). This proves that a tiling of the plane with translated copies of a finite set of tiles either has only a finite number of local configurations or else contains arbitrarily long line segments in the boundaries of the tiles.


Self-Replicating Tilings, in Symbolic dynamics and its applications, AMS Contemp. Math. Series 135, P. Walters, ed., (1992). A self-replicating tile is a set (with interior) which can be tiled by a finite number of translates of a shrunken linear copy of itself. This paper provides a beginning of a classification of such sets as well as the tilings they generate. The principal result is that under mild hypothesis the inverse of the contracting linear mapping must be similar to an integer matrix, and the translates must respect the corresponding lattice.


How to Take Short Cuts, (with Claire Kenyon), Disc. Comput. Geom. 8 (1992):251-264. Given a simple polygon of perimeter 1, can you add line segments of total length less than 10, so that any two points of the resulting set are connected by a path of length at most 3 times their Euclidean distance? We supply an elementary construction (not with these constants), answering a question of Peter Jones (who gave a less elementary construction).


Tiling a polygon with rectangles , (with Claire Kenyon), Proc. of 33rd Fundamentals of Computer Science (FOCS), (1992):610-619. We give an algorithm which tiles a simple polygon with 1Xn and mX1 bars, or decides that one does not exist. A consequence is that the space of tilings is connected by simple local transformations. The proof uses an analysis of the "Conway tiling group".


Intersecting Random Translates of Invariant Cantor Sets, (with Yuval Peres), Invent. Math. 104 (1991):601-629. Let C_1 and C_2 be two Cantor sets in base b with deleted digits. The intersection (C_1+t)\cap C_2, when non-empty, has a dimension as a function of t which is almost surely constant. We compute this dimension in terms of the Lyapunov exponant of a random matrix product.


Richard Kenyon