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

Accepted to *Annales Henri Poincaré*. In the arXiv, updated January 2020 **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.

*Annals of Mathematics* ** 186** (2017) 1-67. In the arXiv, updated July 17, 2017) **Extra:** Code to generate tiles. **Workshop Video:** ICERM workshop.
**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*→ ∞.

Submitted. In the arXiv since July, 2019.
**Show Abstract****Hide Abstract**

**Abstract:**
In this work, we study the problem of online optimization of piecewise Lipschitz functions with semi-bandit feedback. This challenging class of non-convex optimization problems often arises in algorithm selection problems for combinatorial settings, where the goal is to find the best algorithm from a large algorithm family for a specific application domain. In these settings, each evaluation of the loss functions in the optimization problem can be computationally expensive, often requiring the learner to run a combinatorial algorithm to measure its performance. Combined with the fact that small differences between similar algorithms in the family can lead to cascading changes in algorithm behavior, efficient online optimization in these settings is a challenging problem. However, we show that in many applications, evaluating the loss function for one algorithm choice can sometimes reveal the loss for a range of similar algorithms, essentially for free. We develop online optimization algorithms capable of using this kind of extra information by working in the semi-bandit feedback setting. Our algorithms achieve regret bounds that are essentially as good as algorithms under full-information feedback and are significantly more computationally efficient. We apply our semi-bandit optimization results to obtain online algorithm selection procedures for two rich families of combinatorial algorithms. We provide the first provable guarantees for online algorithm selection for clustering problems using a family of clustering algorithms containing classic linkage procedures. We also show how to select algorithms from a family of greedy knapsack algorithms with simultaneously lower computational complexity and stronger regret bounds than the best algorithm selection procedures from prior work.

Submitted. In the arXiv since October 24, 2017.
**Show Abstract****Hide Abstract**

**Abstract:**
We design and analyze a protocol for dividing a state into districts, where parties take turns proposing a division, and freezing a district from the other party's proposed division. We show that our protocol has predictable and provable guarantees for both the number of districts in which each party has a majority of supporters, and the extent to which either party has the power to pack a specific population into a single district.

Submitted. In the arXiv since January 2018.
**Show Abstract****Hide Abstract**

**Abstract:**
We show any matrix of rank $r$ over $\mathbb{F}_q$ can have $\leq \binom{r}{k}(q-1)^k$ distinct columns of weight $k$ if $k \leq O(\sqrt{\log r})$ (up to divisibility issues), and $\leq \binom{r}{k}(q-1)^{r-k}$ distinct columns of co-weight $k$ if $k \leq O_q(r^{2/3})$. This shows the natural examples consisting of only $r$ rows are optimal for both, and the proofs will recover some form of uniqueness of these examples in all cases.

Manuscript. preprint available. In the arXiv since April 2020. **Extra:** Simulation code.
**Show Abstract****Hide Abstract**

**Abstract:**
We discuss the failure of monotonicity properties for even simple compartmental epidemic models, for the case where transmission rates are non-constant. We also identify a special case in which monotonicity holds.

*PLOS ONE* **15** (2020). **Extra:** Simulation code, updated April 19. **Seminar Video:** PIMS/UBC Math-Bio Seminar.
**Show Abstract****Hide Abstract**

**Abstract:**
We use a simple SIR-like epidemic model which integrates known age-contact patterns for the United States to model the effect of age-targeted mitigation strategies for a COVID-19-like epidemic. We find that, among strategies which end with population immunity, strict age-targeted mitigation strategies have the potential to greatly reduce mortalities and ICU utilization for natural parameter choices.

online preprint.
**Show Abstract****Hide Abstract**

**Abstract:**
Minimizing infections and deaths from COVID-19 are not the same thing. While society has some control on the final number of infected individuals through intervention and mitigation strategies, we have much greater control over the age-profile of the final cohort of infected individuals. By ignoring this distinction, strategies which focus on minimizing transmission rates to every extent possible in the entire population could increase deaths among all age groups.
We argue for what we call the *heterogeneous transmission thesis*: in the response to a highly transmittable infectious disease with highly age-variable mortality rates, death rates (for all age groups) may be minimized by mitigation strategies which selectively reduce transmission rates in at-risk populations, while maintaining closer-to-normal transmission rates in low-risk populations.

*Discrete Analysis* (2020). Also in the arXiv.
**Show Abstract****Hide Abstract**

**Abstract:**
Suppose we choose *N* points uniformly randomly from a convex body in *d* dimensions. How large must *N* be, asymptotically with respect to *d*, so that the convex hull of the points is nearly as large as the convex body itself? It was shown by Dyer-Füredi-McDiarmid that exponentially many samples suffice when the convex body is the hypercube, and by Pivovarov that the Euclidean ball demands roughly *d*^{ d/2} samples. We show that when the convex body is the simplex, exponentially many samples suffice; this then implies the same result for any convex simplicial polytope with at most exponentially many faces.

*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.

(Submitted). In the arXiv since December 2020
**Show Abstract****Hide Abstract**

**Abstract:**
We prove that even in average case, the Euclidean Traveling Salesman Problem exhibits an integrality gap of (1+ϵ) for ϵ>0 when the Held-Karp Linear Programming relaxation is augmented by all comb inequalities of bounded size. This implies that large classes of branch-and-cut algorithms take exponential time for the Euclidean TSP, even on random inputs.

(Submitted). In the arXiv, updated February 2020.
**Show Abstract****Hide Abstract**

**Abstract:**
Recall that Janson showed that if the edges of the complete graph Kn are assigned exponentially distributed independent random weights, then the expected length of a shortest path between a fixed pair of vertices is asymptotically equal to (log n)/n. We consider analogous problems where edges have not only a random length but also a random cost, and we are interested in the length of the minimum-length structure whose total cost is less than some cost budget. For several classes of structures, we determine the correct minimum length structure as a function of the cost-budget, up to constant factors. Moreover, we achieve this even in the more general setting where the distribution of weights and costs are arbitrary, so long as the density f(x) as x→0 behaves like cxγ for some γ≥0; previously, this case was not understood even in the absence of cost constraints. We also handle the case where each edge has several independent costs associated to it, and we must simultaneously satisfy budgets on each cost. In this case, we show that the minimum-length structure obtainable is essentially controlled by the product of the cost thresholds.

(Submitted). In the arXiv, submitted September 2019
**Show Abstract****Hide Abstract**

**Abstract:**
We give qualitative and quantitative improvements to theorems which enable significance testing in Markov Chains, with a particular eye toward the goal of enabling strong, interpretable, and statistically rigorous claims of political gerrymandering. Our results can be used to demonstrate at a desired significance level that a given Markov Chain state (e.g., a districting) is extremely unusual (rather than just atypical) with respect to the fragility of its characteristics in the chain. We also provide theorems specialized to leverage quantitative improvements when there is a product structure in the underlying probability space, as can occur due to geographical constraints on districtings.

Submitted. In the arXiv, updated August 2019.
**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.

(Submitted). In the arXiv, submitted August 2018
**Show Abstract****Hide Abstract**

**Abstract:**
Let *p*=(1+*ε*)/*n*. It is known that if *N*=*ε*^{3}*n*→∞ then w.h.p. *G _{n,p}* has a unique giant largest component. We show that if in addition,

(Submitted). In the arXiv, submitted January 2019
**Show Abstract****Hide Abstract**

**Abstract:**
We study random multidimensional assignment problems where the costs decompose into the sum of independent random variables. In particular, in three dimensions, we assume that the costs *W _{i,j,k}* satisfy

*SIAM J. Discrete Math* **33** 1374-1389 (2019). Also in the arXiv.
**Show Abstract****Hide Abstract**

**Abstract:**
We consider arbitrary graphs *G* with *n* vertices and minimum degree at least *δn* where *δ*>0 is constant. If the conductance of *G* is sufficiently large then we obtain an asymptotic expression for the cover time *C _{G}* of

*SODA* 2019. Also in the arXiv.
**Show Abstract****Hide Abstract**

**Abstract:**
We study the rank of the random n×m 0/1 matrix **A**_{n,m;k} where each column is chosen independently from the set Ω_{n,k} of 0/1 vectors with exactly *k* 1's. Here 0/1 are the elements of the field GF_{2}. We obtain an asymptotically correct estimate for the rank in terms of *c,n,k*, assuming that *m*=*cn*. In addition, we assign i.i.d. U[0,1] weights X_{c},**c**∈Ω_{n,k} and let the weight of a set of columns *C* be *X*(*C*)=∑_{c∈C}X_{c}. Let a basis be a set of *n*−**1**_{k even} linearly independent columns. We obtain an asymptotically correct estimate for the minimum weight of a basis. This generalises the well-known result for *k*=2 viz. that the expected length of a minimum weight spanning tree tends to ζ(3).

*Annals of Applied Probability* **28** (2018). In the arXiv, updated December 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).

*Random Structures & Algorithms* (2018). Also in the arXiv since November 2017.
**Show Abstract****Hide Abstract**

**Abstract:**
We consider a synchronous dispersion process introduced in Cooper et. al. and we show that on the infinite line the final set of occupied sites takes up *O*(*n*) space, where *n* is the number of particles involved.

*Discrete Applied Mathematics* **254** (2019) 107-112. Also in the arXiv since December 2017.
**Show Abstract****Hide Abstract**

**Abstract:**
We study the localization game on dense random graphs. In this game, a *cop* *x* tries to locate a *robber* *y* by asking for the graph distance of *y* from every vertex in a sequence of sets *W*_{1},*W*_{2},…,*W*_{l}. We prove high probability upper and lower bounds for the minimum size of each *W*_{i} that will guarantee that *x* will be able to locate *y*.

in graphs with random edge weights

*SIAM J. Discrete Math* **32** 2115-2133 (2018). Also in the arXiv.
**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

*Electronic Journal of Combinatorics* **25** #P1.72. Also in the arXiv.
**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

*PNAS* **114** (2017) 2860-2864 (also: arXiv) **Extra:** Code for redistricting chain. **Extra:** Brief amici curiae in SCOTUS Gill v. Whitford gerrymandering case
**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.

*Random Structures & Algorithms* (2019). Also in the arXiv.
**Show Abstract****Hide Abstract**

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

*Random Structures & Algorithms* (2018). Also in the arXiv.
**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.
**Show Abstract****Hide Abstract**

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

*STOC 2016*. Journal version in *Random Structures & Algorithms* **51** (2017) 375-403. 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.

RANDOM 2017. Journal version in *Random Structures & Algorithms* (2018). Also in the arXiv. **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.

*Electronic Journal of Combinatorics* **22** #P1.34. In the arXiv since April 19, 2014. **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$.

*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* **41** (2012) 546-556. In the arXiv since April 2012.
**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,...,

*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.

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

(Submitted). In the arXiv since March 2020
**Show Abstract****Hide Abstract**

**Abstract:**
We study two biassed Maker-Breaker games played on the complete digraph K⃗ n. In the strong connectivity game, Maker wants to build a strongly connected subgraph. We determine the asymptotic optimal bias for this game viz. n/log(n). In the Hamiltonian game, Maker wants to build a Hamiltonian subgraph. We determine the asymptotic optimal bias for this game up to a constant factor.

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.