Publications

Papers

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

Abelian Sandpile

Stability of patterns in the Abelian sandpile (with Charles K. Smart)

Annales Henri Poincaré (2020). Also in the arXiv. 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.

The Apollonian structure of integer superharmonic matrices (with Lionel Levine, Charles K. Smart)

Annals of Mathematics (2017). In the arXiv, updated July 17, 2017) Extra: Code to generate tiles. Workshop Video: ICERM workshop. Show AbstractHide Abstract

Abstract: We prove that the set of quadratic growths attainable by integer-valued superharmonic functions on the lattice ℤ² 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 ℤ ².

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

GAFA (2016) (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.

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

Duke Math J. (2013). (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→ ∞.

Geometry

Youden's demon is Sylvester's problem (with Florian Frick and Andrew Newman)

In the arXiv since 2024. Show AbstractHide Abstract

Abstract: If four people with Gaussian-distributed heights stand at Gaussian positions on the plane, the probability that there are exactly two people whose height is above the average of the four is exactly the same as the probability that they stand in convex position; both probabilities are 6 π arcsin(⅓)≈.649. We show that this is a special case of a more general phenomenon: The problem of determining the position of the mean among the order statistics of Gaussian random points on the real line ("Youden's demon problem") is the same as a natural generalization of Sylvester's Four Point problem to Gaussian points in ℝ^d. Our main tool is the observation that the Gale dual of independent samples in ℝ^d itself can be taken to be a set of independent points (conditioned on barycenter at the origin) when the distribution of the points is Gaussian.

Unit sphere fibrations in Euclidean space (with Daniel Asimov, Michael Harrison, Florian Frick.)

Proceedings of the Edinburgh Mathematical Society (2024). In the arXiv since Oct 25, 2022. Show AbstractHide Abstract

Abstract: We show that if an open set in ℝ^d can be fibered by unit n-spheres, then d≥2n+1, and if d=2n+1, then the spheres must be pairwise linked, and n∈{0,1,3,7}. For these values of n, we construct unit n-sphere fibrations in ℝ²ⁿ⁺¹.

Random volumes in d-dimensional polytopes (with Alan Frieze, Tomasz Tkocz.)

Discrete Analysis (2020). Also in the arXiv. Show AbstractHide 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.

Sets resilient to erosion

Advances in Geometry (2011). (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.

Randomness

Sampling balanced forests of grids in polynomial time (with Sarah Cannon, Jamie Tucker-Foltz)

STOC 2024 Also in the arXiv. Show AbstractHide Abstract

Abstract: We prove that a polynomial fraction of the set of k-component forests in the m×n grid graph have equal numbers of vertices in each component. This resolves a conjecture of Charikar, Liu, Liu, and Vuong. It also establishes the first provably polynomial-time algorithm for (exactly or approximately) sampling balanced grid graph partitions according to the spanning tree distribution, which weights each k-partition according to the product, across its k pieces, of the number of spanning trees of each piece. Our result has applications to understanding political districtings, where there is an underlying graph of indivisible geographic units that must be partitioned into k population-balanced connected subgraphs. In this setting, tree-weighted partitions have interesting geometric properties, and this has stimulated significant effort to develop methods to sample them.

The bright side of simple heuristics for the TSP (with Alan Frieze)

Electronic Journal of Combinatorics (2024) . Also in the arXiv. Show AbstractHide Abstract

Abstract: The greedy and nearest-neighbor TSP heuristics can both have log(n) approximation factors from optimal in worst case, even just for n points in Euclidean space. In this note, we show that this approximation factor is only realized when the optimal tour is unusually short. In particular, for points from any fixed d-Ahlfor's regular metric space (which includes any d-manifold like the d-cube [0,1]^d in the case d is an integer but also fractals of dimension d when d is real-valued), our results imply that the greedy and nearest-neighbor heuristics have additive errors from optimal on the order of the optimal tour length through random points in the same space, for d>1.

Direct sampling of short paths for contiguous partitioning (with Anish Sevekari)

In the arXiv since July 2023 Show AbstractHide Abstract

Abstract: In this paper, we provide a family of dynamic programming based algorithms to sample nearly-shortest self avoiding walks between two points of the integer lattice ℤ². We show that if the shortest path of between two points has length n, then we can sample paths (self-avoiding-walks) of length n+O(n^1−δ) in polynomial time. As an example of an application, we will show that the Glauber dynamics Markov chain for partitions of the Aztec Diamonds in ℤ² into two contiguous regions with nearly tight perimeter constraints has exponential mixing time, while the algorithm provided in this paper can be used be used to uniformly (and exactly) sample such partitions efficiently.

Sequentially constrained Hamilton cycles in random graphs (with Alan Frieze)

In the arXiv since May 2023. Show AbstractHide Abstract

Abstract: We discuss the existence of Hamilton cycles in the random graph G_n,p where there are restrictions caused by (i) coloring sequences, (ii) a subset of vertices must occur in a specific order and (iii) there is a bound on the number of inversions in the associated permutation.

Subexponential mixing for partition chains on grid-like graphs (with Alan Frieze)

SODA 2023 . Also in the arXiv. Show AbstractHide Abstract

Abstract: We consider the problem of generating uniformly random partitions of the vertex set of a graph such that every piece induces a connected subgraph. For the case where we want to have partitions with linearly many pieces of bounded size, we obtain approximate sampling algorithms based on Glauber dynamics which are fixed-parameter tractable with respect to the bandwidth of G, with simple-exponential dependence on the bandwidth. For example, for rectangles of constant or logarithmic width this gives polynomial-time sampling algorithms. More generally, this gives sub-exponential algorithms for bounded-degree graphs without large expander subgraphs (for example, we obtain 2^O(√n) time algorithms for square grids). In the case where we instead want partitions with a small number of pieces of linear size, we show that Glauber dynamics can have exponential mixing time, even just for the case of 2 pieces, and even for 2-connected subgraphs of the grid with bounded bandwidth.

On the intersecting family process (with Patrick Bennett, Alan Frieze, Andrew Newman)

In the arXiv since February 2023. Show AbstractHide Abstract

Abstract: We study the intersecting family process initially studied in Bohman, Cooper, Frieze, Marti, and Ruszinko (2003). Here k=k(n) and E₁,E₂,…,E_m is a random sequence of k-sets from ([n] choose k) where E_r+1 is uniformly chosen from those k-sets that are not already chosen and that meet E_i,i=1,2,…,r. We prove some new results for the case where k=cn^1/3 and for the case where k≫n^1/2.

Comb inequalities for typical Euclidean TSP instances (with Anish Sevekari)

In the arXiv, updated March 2023. Show AbstractHide 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.

Multitrees in random graphs (with Alan Frieze)

Electronic Journal of Combinatorics (2023) . Also in the arXiv. Show AbstractHide Abstract

Abstract: Let N=(n choose 2) and s≥2. Let e_i,j,i=1,2,…,N,j=1,2,…,s be s independent permutations of the edges E(K_n) of the complete graph K_n. A MultiTree is a set I⊆[N] such that the edge sets E_I,j induce spanning trees for j=1,2,…,s. In this paper we study the following question: what is the smallest m=m(n) such that w.h.p. [m] contains a MultiTree. We prove a hitting time result for s=2 and an O(n log n) bound for s≥3

Spanners in randomly weighted graphs: Euclidean cacse (with Alan Frieze)

Journal of Graph Theory (2023) . Also in the arXiv. Show AbstractHide Abstract

Abstract: Given a connected graph G=(V,E) and a length function ℓ:E→R we let d_v,w denote the shortest distance between vertex v and vertex w. A t-spanner is a subset E′⊆E such that if d′_v,w denotes shortest distances in the subgraph G′=(V,E′) then d′_v,w≤td_v,w for all v,w∈V. We show that for a large class of graphs with suitable degree and expansion properties with independent exponential mean one edge lengths, there is w.h.p. a 1-spanner that uses ≈12n log n edges and that this is best possible. In particular, our result applies to the random graphs G_n,p for np≫logn.

Spanners in randomly weighted graphs: independent edge lengths (with Alan Frieze)

Discrete Applied Mathematics (2022) . Also in the arXiv. Show AbstractHide Abstract

Abstract: Given a connected graph G=(V,E) and a length function ℓ:E→R we let d_v,w denote the shortest distance between vertex v and vertex w. A t-spanner is a subset E′⊆E such that if d′_v,w denotes shortest distances in the subgraph G′=(V,E′) then d′_v,w≤td_v,w for all v,w∈V. We show that for a large class of graphs with suitable degree and expansion properties with independent exponential mean one edge lengths, there is w.h.p. a 1-spanner that uses ≈12n log n edges and that this is best possible. In particular, our result applies to the random graphs G_n,p for np≫logn.

On the cover time of the emerging giant (with Alan Frieze, Tomasz Tkocz)

Siam Journal on Discrete Mathematics (2022). Also in the arXiv. Show AbstractHide Abstract

Abstract: Let p=(1+ε)/n. It is known that if N=ε³n→∞ then w.h.p. G_n,p has a unique giant largest component. We show that if in addition, ε=ε(n)→0 then w.h.p. the cover time of G_n,p is asymptotic to nlog²N; previously Barlow, Ding, Nachmias and Peres had shown this up to constant multiplicative factors.

Minimum-weight combinatorial structures under random cost-constraints (with Alan Frieze, Gregory Sorkin, Tomasz Tkocz)

The Electronic Journal of Combinatorics (2021). Also in the arXiv. Show AbstractHide 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.

Separating effect from significance in Markov chain tests (with Maria Chikina, Jonathan Mattingly, and Alan Frieze)

Statistics and Public Policy (2020). Also in the arXiv. Show AbstractHide 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.

Scalefree hardness of average-case Euclidean TSP approximation (with Alan Frieze)

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

On random multi-dimensional assignment problems (with Alan Frieze, Tomasz Tkocz)

Discrete Applied Mathematics (2020). Also in the arXiv. Show AbstractHide 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 W_i,j,k=a_i,j+b_i,k+c_j,k where the a_i,j,b_i,k,c_j,k are independent exponential rate 1 random variables. Our objective is to minimize the total cost and we show that w.h.p. a simple greedy algorithm is a (3+o(1))-approximation. This is in contrast to the case where the W_i,j,k are independent exponential rate 1 random variables. Here all that is known is an n^o(1)-approximation, due to Frieze and Sorkin.

On the cover time of the dense graphs (with Alan Frieze, Tomasz Tkocz)

SIAM J. Discrete Math (2019). Also in the arXiv. Show AbstractHide 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 G as the solution to an explicit transcendental equation. Failing this, if the mixing time of a random walk on G is of a lesser magnitude than the cover time, then we can obtain an asymptotic deterministic estimate via a decomposition into a bounded number of dense sub-graphs with high conductance. Failing this we give a deterministic asymptotic (2+o(1))-approximation of C_G.

On the rank of a random binary matrix (with Colin Cooper, Alan Frieze)

SODA 2019. Also in the arXiv. Show AbstractHide 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₂. 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∈CX_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).

Diffusion limited aggregation in the Boolean lattice (with Alan Frieze)

Annals of Applied Probability 28 (2018). In the arXiv, updated December 2017. Show AbstractHide Abstract

Abstract: In the Diffusion Limited Aggregation (DLA) process on on ℤ², 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}ⁿ, 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).

A note on dispersing particles on a line (with Alan Frieze)

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

A note on the localization number of random graphs: diameter two case (with Andrzej Dudek, Alan Frieze)

Discrete Applied Mathematics (2019). Also in the arXiv. Show AbstractHide 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₁,W₂,…,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.

The distribution of minimum-weight cliques and other subgraphs
in graphs with random edge weights (with Alan Frieze, Gregory Sorkin)

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

Constraining the clustering transition for colorings of sparse random graphs (with Michael Anastos, Alan Frieze)

Electronic Journal of Combinatorics (2018). Also in the arXiv. Show AbstractHide Abstract

Abstract: Let Ω_q denote the set of proper q-colorings of the random graph G_n,m, m=dn/2 and let H_q 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. H_q 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.

Assessing significance in a Markov chain without mixing (with Maria Chikina, Alan Frieze)

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

Minors of a random binary matroid (with Colin Cooper, Alan Frieze)

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

Abstract: Let A=A_n,m,k be a random n×m matrix over GF₂ 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.

Online purchasing under uncertainty (with Alan Frieze)

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

Looking for vertex number one (with Alan Frieze)

Annals of Applied Probability (2017). Also in the arXiv, last updated May 2016. Show AbstractHide Abstract

Abstract: Given an instance of the preferential attachment graph G_n=([n],E_n), 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.

Separating subadditive Euclidean functionals (with Alan Frieze)

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

Traveling in randomly embedded random graphs (with Alan Frieze)

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

Between 2- and 3-colorability (with Alan Frieze)

Electronic Journal of Combinatorics (2015). Also in the arXiv. Extra: bound.cpp. Show AbstractHide 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$.

An extension of the Moser-Tardos algorithmic local lemma

SIAM J. Discrete Math (2014). Also in the arXiv. 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.

The Lefthanded Local Lemma characterizes chordal dependency graphs

Random Structures (2012). Also in the arXiv. Show AbstractHide Abstract

Abstract: Suppose there is a collection x₁,x₂,...,x_N 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 x_i ahead of time. Instead, we inspect the random variables x_i one at a time, and after each inspection, choose to either keep the vertex i at cost x_i, 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.

Highly nonrepetitive sequences: winning strategies from the Local Lemma

Random Structures & Algorithms (2010) Also in the arXiv. 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.

Graph Theory

Critical graphs without triangles: an optimum density construction

Combinatorica (2013) Also in the arXiv. 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 >(¼ - ε)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 (2006) (preprint 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)² 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.

Games

(see also the RSA 38 paper, above)

Maker-Breaker on Digraphs (with Alan Frieze)

Journal of Graph Theory (2021). Also in the arXiv. Show AbstractHide 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.

Walker-Breaker games (with Lisa Espig, Alan Frieze, Michael Krivelevich )

SIAM J. Discrete Math. 29 (2015). Also in the arXiv. 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 topology of competitively constructed graphs (with Alan Frieze)

The Electronic Journal of Combinatorics (2014). Also in the arXiv. 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.

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) (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 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 (2008). Also in the arXiv. 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.

CS Theory

Semi-bandit Optimization in the Dispersed Setting (with Nina Balcan, Travis Dick)

Uncertainty in Artificial Intelligence (2020). Also in the arXiv. Show AbstractHide 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.

A partisan districting protocol with provably nonpartisan outcomes (with Ariel Procaccia, Dingli Yu)

In the arXiv since October 24, 2017. Show AbstractHide 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.

Extremal problems

Extremal Collections of k-Uniform Vectors (with Joseph Briggs)

In the arXiv since January 2018. Show AbstractHide 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.

COVID-19

Failure of montonicity in epidemic models (with Maria Chikina)

Manuscript. preprint available. In the arXiv since April 2020. Extra: Simulation code. Show AbstractHide 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.

Modeling strict age-targeted mitigation strategies for COVID-19 (with Maria Chikina)

PLOS ONE 15 (2020). Extra: Simulation code, updated April 19. Seminar Video: PIMS/UBC Math-Bio Seminar. Show AbstractHide 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.

Fighting COVID-19: the heterogeneous transmission thesis (with Maria Chikina)

online preprint. Show AbstractHide 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.