Publications

Papers

Click on the word Abstract below each title to toggle display of the abstract.

Abelian Sandpile

Apollonian structure in the Abelian Sandpile (with Lionel Levine, Charles K. Smart)

(preprint available. In the arXiv since August 23, 2012.) Extra: images of Γ on various lattices.

Abstract Abstract: We state a conjecture relating integer-valued superharmonic functions on ℤ² to an Apollonian circle packing of ℝ². The conjecture is motivated by the Abelian sandpile process, which evolves configurations of chips on the integer lattice by toppling any vertex with at least 4 chips, distributing one of its chips to each of its 4 neighbors. When begun from a large stack of chips, the terminal state of the sandpile has a curious fractal structure which has remained unexplained. Our conjecture implies that the Sandpile PDE recently shown to characterize the continuum limit of the sandpile is equivalent to the Apollonian PDE, and we use the special geometric structure of the latter to prove that it admits certain fractal solutions. Boundary condition evidence from finite sandpiles suggest that these solutions exactly correspond to regions of the limiting sandpile, leading to precise geometric conjectures on the Abelian sandpile's fractal behavior.
Note: The above mentioned conjecture is now essentially proved—the write-up is in progress.

Convergence of the Abelian Sandpile (with Charles K. Smart)

To appear in Duke. (preprint available. In the arXiv since April 30, 2011.)

Abstract Abstract: The Abelian sandpile growth model is a diffusion process for configurations of chips placed on vertices of the integer lattice ℤ^d , in which sites with at least 2d chips topple, distributing 1 chip to each of their neighbors in the lattice, until no more topplings are possible. From an initial configuration consisting of n chips placed at a single vertex, the rescaled stable configuration seems to converge to a particular fractal pattern as n→ ∞. However, little has been proved about the appearance of the stable configurations. We use PDE techniques to prove that the rescaled stable configurations do indeed converge to a unique limit a n→ ∞.

Local Lemma

The Lefthanded Local Lemma characterizes chordal dependency graphs

To appear in Random Structures & Algorithms (preprint available, last updated March 30, 2012)

Abstract Abstract: Shearer gave a general theorem characterizing the family L of dependency graphs labeled with probabilities p_v which have the property that for any family of events with a dependency graph from L (whose vertex-labels are upper bounds on the probabilities of the events), there is a positive probability that none of the events from the family occur.
We show that, unlike the standard Lovász Local Lemma—which is less powerful than Shearer's condition on every nonempty graph—a recently proved `Lefthanded' version of the Local Lemma is equivalent to Shearer's condition for all chordal graphs. This also gives a simple and efficient algorithm to check whether a given labeled chordal graph is in L.

An extension of the Moser-Tardos algorithmic local lemma

To appear in SIAM J. Discrete Math. (preprint available, last updated March 1, 2011)

Abstract Abstract: A recent theorem of Bissacot, et al. proved using results about the cluster expansion in statistical mechanics extends the Lovász Local Lemma by weakening the conditions under which its conclusions holds. In this note, we prove an algorithmic analog of this result, extending Moser and Tardos's recent algorithmic Local Lemma, and providing an alternative proof of the theorem of Bissacot, et al. applicable in the Moser-Tardos algorithmic framework.

Highly nonrepetitive sequences: winning strategies from the Local Lemma

Random Structures & Algorithms 38 pp 140-161 (preprint also available, last updated October 24, 2010)

(Presented at the Special Session on Probabilistic and Extremal Combinatorics at the AMS meeting at UIUC, March 2009, and at the Random Structures and Algorithms conference in Poznań, Poland)

Abstract Abstract: We prove game-theoretic versions of several classical results on nonrepetitive sequences, showing the existence of winning strategies using an extension of the Local Lemma which can dramatically reduce the number of edges needed in a dependency graph when there is an ordering underlying the significant dependencies of events. This appears to represent the first successful application of a Local Lemma to games.

Combinatorial Games

(see also above)

The Hales-Jewett number is exponential: game-theoretic consequences (with J. Beck and S. Vijay)

Analytic Number Theory: Essays in Honour of Klaus Roth
(Editors: William Chen, Tim Gowers, Heini Halberstam, Wolfgang Schmidt and Bob Vaughan)

Abstract Abstract: We prove an exponential lower bound on the Hales Jewett number H(n), improving on the previously known bound H(n)≥n. We also prove a lower bound on the Halving Hales Jewett number concerning balanced colorings of hypercubes, demonstrating H_1/2(n)≥H(n-2). Taken together, these two results imply that there are infinitely many Tic-Tac-Toe games which are delicate win games or delicate draw games (roughly speaking: these classes contain the games where the optimium play outcome occurs for nontrivial reasons). Individually, neither of these classes are known to have cardinality >1.

A finite goal set in the plane which is not a winner

Discrete Mathematics 308 (24) (2008) 6546-6551 (pdf also available)

Abstract Abstract: J. Beck has shown that if two players alternately select previously unchosen points from the plane, Player 1 can always build a congruent copy of any given finite goal set G, in spite of Player 2’s efforts to stop him. We give a finite goal set G (it has 5 points) which Player 1 cannot construct before Player 2 in this achievement game played in the plane.

Geometry

Sets resilient to erosion

Advances in Geometry 11 (2011) pp. 201-224. (preprint available)

Abstract Abstract: The erosion of a set in Euclidean space by a radius r > 0 is the subset of X consisting of points at distance ≥ r from the complement of X. A set is resilient to erosion if it is similar to its erosion by some positive radius. We give a somewhat surprising characterization of resilient sets, consisting in one part of simple geometric constraints on convex resilient sets, and, in another, a correspondence between nonconvex resilient sets and scale-invariant (e.g., `exact fractal') sets.

Graph Theory

Critical graphs without triangles: an optimum density construction

To appear in Combinatorica. (preprint available)

(Presented at the Rènyi Institute Workshop on Extremal Combinatorics in Budapest, June 2007, and the Princeton Discrete Math Seminar, December 2007)

Abstract Abstract: We construct dense, triangle-free, chromatic-critical graphs of chromatic number k for all k ≥ 4. For k ≥ 6 our constructions have >(¼ - ε)n² edges, which is asymptotically best possible by Turán's theorem. We also demonstrate (nonconstructively) the existence of dense k-critical graphs avoiding all odd cycles ≤ ℓ for any ℓ and any any k ≥ 4, again with a best possible density of > (¼ - ε)n² edges for k ≥ 6. The families of graphs without triangles or of given odd-girth are thus rare examples where we know the correct maximal density of k-critical members (k ≥ 6). We also construct dense 4-critical graphs of any odd-girth.

Distance Sequences in Locally Infinite Vertex-Transitive Digraphs

Combinatorica 26 (5) (2006) 577-585 (pdf also available)

Abstract Abstract: We prove that the out-distance sequence {f⁺(k)} of a vertex-transitive digraph of finite or infinite degree satisfies f⁺(k + 1) ≤ f⁺(k)² for k ≥ 1, where f⁺(k) denotes the number of vertices at directed distance k from a given vertex. As a corollary, we prove that for a connected vertex-transitive undirected graph of infinite degree d, we have f(k) = d for all k, 1 ≤ k < diam(G). This answers a question by L. Babai.