Click on Show Abstract beside each title to toggle display of the abstract.
In the arXiv since August 30, 2017 Show AbstractHide 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 AbstractHide 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 AbstractHide 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 AbstractHide 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→ ∞.
Submitted. In the arxiv, updated July 2017. Show AbstractHide 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 Kn 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 k and n. The results may be applied to evaluate whether an observed minimum-weight copy of a graph H in a network provides statistical evidence that the network's edge weights are not independently distributed but have some structure.
Submitted. In the arxiv since May 2017. Show AbstractHide Abstract
Abstract: Let Ωq denote the set of proper q-colorings of the random graph Gn,m, m=dn/2 and let Hq be the graph with vertex set Ωq and an edge {σ,τ} where σ,τ are mappings [n]→[q] iff h(σ,τ)=1. Here h(σ,τ) is the Hamming distance |{v∈[n]:σ(v)≠τ(v)}|. We show that w.h.p. Hq contains a single giant component containing almost all colorings in Ωq if d is sufficiently large and q≥cd log d for a constant c>3/2.
Submitted. In the arxiv since May 2017. Show AbstractHide 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 AbstractHide 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 AbstractHide Abstract
Abstract: Let A=An,m,k be a random n×m matrix over GF2 where each column consists of k randomly chosen ones. Let M be an arbirary fixed binary matroid. We show that if m/n and k are sufficiently large then as n→∞ the binary matroid induced by A contains M as a minor.
To appear in Random Structures & Algorithms. In the arXiv since November 24, 2014. Show AbstractHide 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 AbstractHide Abstract
Abstract: Given an instance of the preferential attachment graph Gn=([n],En), we would like to find vertex 1, using only `local' information about the graph. Borgs et. al gave a O(log 4n) time algorithm, which is local in the sense that it grows a connected set of vertices which will contain vertex 1 while still of size O(log 4n). We give a O(ωlog 7/2n) algorithm to find vertex 1 (where ω→∞ is arbitrary), which is local in the strong sense that it traverses the graph vertex-by-vertex, and operates only on the neighborhood of its current vertex.
Electronic Journal of Combinatorics
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 AbstractHide Abstract
Abstract:
Suppose there is a collection x1,x2,...,xN of independent uniform [0,1] random variables, and a hypergraph F of target structures on the vertex set {1,...,N}. We would like to buy a target structure at small cost, but we do not know all the costs xi ahead of time. Instead, we inspect the random variables xi one at a time, and after each inspection, choose to either keep the vertex i at cost xi, or reject vertex i forever.
In the present paper, we consider the case where {1,...,N} is the edge-set of some graph, and the target structures are the spanning trees of a graph, spanning arborescences of a digraph, the paths between a fixed pair of vertices, perfect matchings, Hamilton cycles or the cliques of some fixed size.
Submitted. In the arXiv since April 15, 2016. Show AbstractHide 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 AbstractHide 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 AbstractHide 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 AbstractHide 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 AbstractHide 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 AbstractHide Abstract
Abstract: We construct dense, triangle-free, chromatic-critical graphs of chromatic number k for all k ≥ 4. For k ≥ 6 our constructions have >(¼ - ε)n2 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 > (¼ - ε)n2 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 AbstractHide 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 AbstractHide 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 AbstractHide 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 AbstractHide 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 AbstractHide 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 H1/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 AbstractHide 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.