*Click on * Show Abstract *beside each title to toggle display of the abstract.*

In the arXiv since August 30, 2017 **Show Abstract****Hide Abstract**

**Abstract:**
We show that the patterns in the Abelian sandpile are stable. The proof combines the structure theory for the patterns with the regularity machinery for non-divergence form elliptic equations. The stability results allows one to improve weak-* convergence of the Abelian sandpile to pattern convergence for certain classes of solutions.

to appear in *Annals of Mathematics* (preprint available. In the arXiv, updated July 17, 2017) **Extra:** Code to generate tiles.**Show Abstract****Hide Abstract**

**Abstract:**
We prove that the set of quadratic growths attainable by integer-valued superharmonic functions on the lattice ℤ^{2} has the structure of an Apollonian circle packing. This completely characterizes the PDE which determines the continuum scaling limit of the Abelian sandpile on the lattice ℤ^{2}.

*GAFA* **26** (2016) 306-336 (preprint available. In the arXiv, updated May 22, 2014) **Extra:** images of Γ on various lattices.**Show Abstract****Hide Abstract**

**Abstract:**
The *Abelian sandpile* process 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. Using a characterization of the quadratic growths attainable by integer-superharmonic functions, we prove that the *sandpile PDE* recently shown to characterize the scaling limit of the sandpile admits certain fractal solutions, giving a precise mathematical perspective on the fractal nature of the sandpile.

*Duke Math J.* **162** (2013) 627-642. (preprint available. In the arXiv, updated March 7, 2012)**Show Abstract****Hide 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*→ ∞.

in graphs with random edge weights

Submitted. In the arxiv, updated July 2017.
**Show Abstract****Hide Abstract**

**Abstract:**
We determine, asymptotically in n, the distribution and mean of the weight of a minimum-weight *k*-clique (or any strictly balanced graph *H*) in a complete graph *K _{n}* whose edge weights are independent random values drawn from the uniform distribution or other continuous distributions. For the clique, we also provide explicit (non-asymptotic) bounds on the distribution's CDF in a form obtained directly from the Stein-Chen method, and in a looser but simpler form. The direct form extends to other subgraphs and other edge-weight distributions. We illustrate the clique results for various values of

Submitted. In the arxiv since May 2017.
**Show Abstract****Hide Abstract**

**Abstract:**
Let Ω_{q} denote the set of proper *q*-colorings of the random graph *G _{n,m}, m=dn*/2 and let

Submitted. In the arxiv since May 2017.
**Show Abstract****Hide Abstract**

**Abstract:**
In the Diffusion Limited Aggregation (DLA) process on on ℤ^{2}, or more generally ℤ^{d}, particles aggregate to an initially occupied origin by arrivals on a random walk. The scaling limit of the result, empirically, is a fractal with dimension strictly less than *d*. Very little has been shown rigorously about the process, however.
We study an analogous process on the Boolean lattice {0,1}^{n}, in which particles take random decreasing walks from (1,…,1), and stick at the last vertex before they encounter an occupied site for the first time; the vertex (0,…,0) is initially occupied. In this model, we can rigorously prove that lower levels of the lattice become full, and that the process ends by producing an isolated path of unbounded length reaching (1,…,1).

In the *Proceedings of the National Academy of Sciences*, available online. (preprint also available.) **Extra:** Code for redistricting chain.
**Show Abstract****Hide Abstract**

**Abstract:**
We present a new statistical test to detect that a presented state of a reversible Markov chain was not chosen from a stationary distribution. In particular, given a value function for the states of the Markov chain, we would like to demonstrate rigorously that the presented state is an outlier with respect to the values, by establishing a *p*-value under the null hypothesis that it was chosen from a stationary distribution of the chain.

A simple heuristic used in practice is to sample ranks of states from long random trajectories on the Markov chain, and compare these to the rank of the presented state; if the presented state is a 0.1%-outlier compared to the sampled ranks (its rank is in the bottom $0.1\%$ of sampled ranks) then this should correspond to a *p*-value of 0.001. This is not rigorous, however, without good bounds on the mixing time of the Markov chain.

Our test is the following: given the presented state in the Markov chain, take a random walk \emph{from the presented state} for any number of steps. We prove that observing that the presented state is an ε-outlier on the walk is significant at *p=√2ε*, under the null hypothesis that the state was chosen from a stationary distribution. We assume nothing about the Markov chain beyond reversibility, and show that significance at *p≈√ε* is essentially best possible in general.
We illustrate the use of our test with a potential application to the rigorous detection of gerrymandering in Congressional districtings.

Submitted. In the arXiv since December 7, 2016.
**Show Abstract****Hide Abstract**

**Abstract:**
Let *A=A _{n,m,k}* be a random

To appear in *Random Structures & Algorithms*. In the arXiv since November 24, 2014.
**Show Abstract****Hide Abstract**

**Abstract:**
We consider the problem of traveling among random points in Euclidean space, when only a random fraction of the pairs are joined by traversable connections. In particular, we show a threshold for a pair of points to be connected by a geodesic of length arbitrarily close to their Euclidean distance, and analyze the minimum length Traveling Salesperson Tour, extending the Beardwood-Halton-Hammersley theorem to this setting.

*Annals of Applied Probability* **27** (2017) 582-630. Also in the arXiv, last updated May 2016. (A preprint is also available.)
**Show Abstract****Hide Abstract**

**Abstract:**
Given an instance of the preferential attachment graph *G _{n}*=([

*Electronic Journal of Combinatorics* **Extra:** bound.cpp.
**Show Abstract****Hide Abstract**

**Abstract:**
We consider the question of the existence of homomorphisms between $G_{n,p}$ and odd cycles when $p=c/n,\,1 < c\leq 4$. We show that for any positive integer $\ell$, there exists $\varepsilon=\varepsilon(\ell)$ such that if $c=1+\varepsilon$ then w.h.p. $G_{n,p}$ has a homomorphism from $G_{n,p}$ to $C_{2\ell+1}$ so long as its odd-girth is at least $2\ell+1$. On the other hand, we show that if $c=4$ then w.h.p. there is no homomorphism from $G_{n,p}$ to $C_5$. Note that in our range of interest, $\chi(G_{n,p})=3$ w.h.p., implying that there is a homomorphism from $G_{n,p}$ to $C_3$.

*Random Structures*. In the arXiv since May 19, 2016.
**Show Abstract****Hide Abstract**

**Abstract:**
Suppose there is a collection *x _{1},x_{2},...,x_{N}* of independent uniform [0,1] random variables, and a hypergraph F of

In the present paper, we consider the case where {1,...,

Submitted. In the arXiv since April 15, 2016.
**Show Abstract****Hide Abstract**

**Abstract:**
We show that if P≠NP, then a wide class of TSP heuristics fail to approximate the length of the TSP to asymptotic optimality, even for random Euclidean instances. As an application, we show that when using a heuristic from this class, a natural class of branch-and-bound algorithms takes exponential time to find an optimal tour (again, even on a random point-set), regardless of the particular branching strategy or lower-bound algorithm used.

Accepted to *STOC 2016*. To appear in *Random Structures & Algorithms*. In the arXiv since January 8, 2015.
**Show Abstract****Hide Abstract**

**Abstract:**
The classical Beardwood-Halton-Hammersly theorem (1959) asserts the existence of an asymptotic formula of the form *β√n* for the minimum length of a Traveling Salesperson Tour throuh $n$ random points in the unit square, and in the decades since it was proved, the existence of such formulas has been shown for other such *Euclidean functionals* on random points in the unit square as well. Despite more than 50 years of attention, however, it remained unknown whether the minimum length TSP through *n* random points in [0,1]^{2} was asymptotically distinct from its natural lower bounds, such as the minimum length spanning tree, the minimum length 2-factor, or, as raised by Goemans and Bertsimas, from its linear programming relaxation.
We prove that the TSP on random points in Euclidean space is indeed asymptotically distinct from these and other natural lower bounds, and show that this separation implies that branch-and-bound algorithms based on these natural lower bounds must take nearly exponential (*e*^{Ω(n)}) time to solve the TSP to optimality, even in average case. This is the first average-case superpolynomial lower bound for these branch-and-bound algorithms; a lower bound as strong as *e*^{Ω(n)} was not even known in worst-case analysis.

Conference version in RANDOM 2017. In the arXiv since November 24, 2014. **Extra:** Code for Figure 1.
**Show Abstract****Hide Abstract**

**Abstract:**
We consider the problem of traveling among random points in Euclidean space, when only a random fraction of the pairs are joined by traversable connections. In particular, we show a threshold for a pair of points to be connected by a geodesic of length arbitrarily close to their Euclidean distance, and analyze the minimum length Traveling Salesperson Tour, extending the Beardwood-Halton-Hammersley theorem to this setting.

*SIAM J. Discrete Math* **28** 911-917 (2014). (preprint available, last updated January 26, 2013)
**Show Abstract****Hide 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.

*Random Structures & Algorithms* **38** pp 140-161 (preprint also available, last updated October 24, 2010)
**Show Abstract****Hide 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.

*Combinatorica* **33** (4) (2013) 495-513
(preprint also available)
**Show Abstract****Hide 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^{2} 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^{2} 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.

*Combinatorica* **26** (5) (2006) 577-585 (pdf is also available)
**Show Abstract****Hide 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)^{2} 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.

*Advances in Geometry* **11** (2011) pp. 201-224. (preprint is available)
**Show Abstract****Hide 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.

(see also the RSA **38** paper, above)

SIAM J. Discrete Math. **29** (2015). In the arXiv since January 22, 2014. (A preprint is also available.)
**Show Abstract****Hide Abstract**

**Abstract:**
We introduce and analyze the Walker-Breaker game, a variant of Maker-Breaker games
where Maker is constrained to choose edges of a walk or path in a given graph G, with the
goal of visiting as many vertices of the underlying graph as possible.

*The Electronic Journal of Combinatorics* **21** #P2.26, In the arXiv since December 3, 2013. (A preprint is also available.)
**Show Abstract****Hide Abstract**

**Abstract:**
We consider a simple game, the *k*-regular graph game, in which players take turns adding edges to an initially empty graph subject to the constraint that the degrees of vertices cannot exceed *k*. We show a sharp topological threshold for this game: for the case *k*=3 a player can ensure the resulting graph is planar, while for the case *k*=4, a player can force the appearance of arbitrarily large clique minors.

Analytic Number Theory: Essays in Honour of Klaus Roth

(Editors: William Chen, Tim Gowers, Heini Halberstam, Wolfgang Schmidt and Bob Vaughan) (A preprint is also available.)
**Show Abstract****Hide 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.

*Discrete Mathematics* **308** (24) (2008) 6546-6551 (pdf also available)
**Show Abstract****Hide 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.