The {balls-into-bins model} randomly allocates n sequential balls into n bins, as follows: each ball selects a set D of d ⩾ 2 bins, independently and uniformly at random, then the ball is allocated to a least-loaded bin from D (ties broken randomly). The maximum load is the maximum number of balls in any bin. In 1999, Azar et al. showed that, provided ties are broken randomly, after n balls have been placed the maximum load, is log_d log n + 𝒪(1), with high probability. We consider this popular paradigm in a dynamic environment where the bins are structured as a dynamic hypergraph. A dynamic hypergraph is a sequence of hypergraphs, say ℋ^(t), arriving over discrete times t = 1,2,…, such that the vertex set of ℋ^(t)’s is the set of n bins, but (hyper)edges may change over time. In our model, the t-th ball chooses an edge from ℋ^(t) uniformly at random, and then chooses a set D of d ⩾ 2 random bins from the selected edge. The ball is allocated to a least-loaded bin from D, with ties broken randomly. We quantify the dynamicity of the model by introducing the notion of pair visibility, which measures the number of rounds in which a pair of bins appears within a (hyper)edge. We prove that if, for some ε > 0, a dynamic hypergraph has pair visibility at most n^{1-ε}, and some mild additional conditions hold, then with high probability the process has maximum load 𝒪(log_dlog n). Our proof is based on a variation of the witness tree technique, which is of independent interest. The model can also be seen as an adversarial model where an adversary decides the structure of the possible sets of d bins available to each ball.

We consider the problem of $q$-coloring a $k$-uniform random hypergraph, where $q,k \geq 3$, and determine the rigidity threshold. For edge densities above the rigidity threshold, we show that almost all solutions have a linear number of vertices that are linearly frozen, meaning that they cannot be recolored by a sequence of colorings that each change the color of a sublinear number of vertices. When the edge density is below the threshold, we prove that all but a vanishing proportion of the vertices can be recolored by a sequence of colorings that recolor only one vertex at a time. This change in the geometry of the solution space has been hypothesized to be the cause of the algorithmic barrier faced by naive coloring algorithms. Our calculations verify predictions made by statistical physicists using the nonrigorous cavity method. The traditional model for problems of this type is the random coloring model, where a random hypergraph is chosen and then a random coloring of that hypergraph is selected. However, it is often easier to work with the planted model, where a random coloring is selected first, and then edges are randomly chosen which respect the coloring. As part of our analysis, we show that up to the condensation phase transition, the random coloring model is contiguous with respect to the planted model. This result is of independent interest.

The problem of efficiently sampling from a set of (undirected) graphs with a given degree sequence has many applications. One approach to this problem uses a simple Markov chain, which we call the switch chain, to perform the sampling. The switch chain is known to be rapidly mixing for regular degree sequences. We prove that the switch chain is rapidly mixing for any degree sequence with minimum degree at least 1 and with maximum degree dmax which satisfies , where M is the sum of the degrees. The mixing time bound obtained is only an order of n larger than that established in the regular case, where n is the number of vertices.

Let $J$ and $J^*$ be subsets of $\mathbb{N}$ such that $0,1\in J$ and $0\in J^*$. For infinitely many $n$, let ${\boldsymbol{k}}=(k_1,\ldots, k_n)$ be a vector of nonnegative integers whose sum $M$ is even. We find an asymptotic expression for the number of multigraphs on the vertex set $\{1,\ldots, n\}$ with degree sequence given by ${\boldsymbol{k}}$ such that every loop has multiplicity in $J^*$ and every nonloop edge has multiplicity in $J$. Equivalently, these are symmetric integer matrices with values $J^*$ allowed on the diagonal and $J$ off the diagonal. Our expression holds when the maximum degree $k_{\mathrm{max}}$ satisfies $k_{\mathrm{max}} = o(M^{1/3})$. We prove this result using the switching method, building on an asymptotic enumeration of simple graphs with given degrees [B. D. McKay and N. C. Wormald, Combinatorica, 11 (1991), pp. 369--382]. Our application of the switching method introduces a novel way of combining several different switching operations into a single computation.

A new method for analyzing the mixing time of Markov chains is described. This method is an extension of path coupling and involves analyzing the coupling over multiple steps.The expected behavior of the coupling at a certain stopping time is used to bound the expected behavior of the coupling after a fixed number of steps. The new method is applied to analyze the mixing time of the Glauber dynamics for graph colorings. We show that the Glauber dynamics has O(n log(n)) mixing time for triangle-free $\Delta$-regular graphs if k colors are used, where $k\geq (2-\eta)\Delta$, for some small positive constant $\eta$. This is the first proof of an optimal upper bound for the mixing time of the Glauber dynamics for some values of k in the range $k\leq 2\Delta$.

We consider approximate counting of colorings of an n-vertex graph using rapidly mixing Markov chains. It has been shown by Jerrum and by Salas and Sokal that a simple random walk on graph colorings would mix rapidly, provided the number of colors k exceeded the maximum degree $\Delta$ of the graph by a factor of at least 2. We prove that this is not a necessary condition for rapid mixing by considering the simplest case of 5-coloring graphs of maximum degree 3. Our proof involves a computer-assisted proof technique to establish rapid mixing of a new "heat bath" Markov chain on colorings using the method of path coupling. We outline an extension to 7-colorings of triangle-free 4-regular graphs. Since rapid mixing implies approximate counting in polynomial time, we show in contrast that exact counting is unlikely to be possible (in polynomial time). We give a general proof that the problem of exactly counting the number of proper k-colorings of graphs with maximum degree $\Delta$ is $# P$-complete whenever $k\geq 3$ and $\Delta \geq 3$.