Source author record

Catherine Greenhill

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Data Structures and Algorithms math-ph math.MP math.PR math.ST Statistics Theory

Catalog footprint

Research overview

15works

8topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Asymptotic enumeration of constrained bipartite, directed and oriented graphs by degree sequence

In the sufficiently sparse case, we find the probability that a uniformly random bipartite graph with given degree sequence contains no edge from a specified set of edges. This enables us to enumerate loop-free digraphs and oriented graphs with given in-degree and out-degree sequences, and obtain subgraph probabilities. Our theorems are not restricted to the near-regular case. As an application, we determine the expected permanent of sparse or very dense random matrices with given row and column sums; in the regular case, our formula holds over all densities. We also draw conclusions about the degrees of a random orientation of a random undirected graph with given degrees, including its number of Eulerian orientations.

preprint2022arXiv

Balanced Allocation on Hypergraphs

We consider a variation of balls-into-bins which randomly allocates $m$ balls into $n$ bins. Following Godfrey's model (SODA, 2008), we assume that each ball $t$ , $1\le t\le m$ , comes with a hypergraph $\mathcal{H}^{(t)}=\{B_1,B_2,\ldots,B_{s_t}\}$ , and each edge $B\in\mathcal{H}^{(t)}$ contains at least a logarithmic number of bins. Given $d\ge 2$ , our $d$ -choice algorithm chooses an edge $B\in \mathcal{H}^{(t)}$ , uniformly at random, and then chooses a set $D$ of $d$ random bins from the selected edge $B$ . The ball is allocated to a least-loaded bin from $D$ , with ties are broken randomly. We prove that if the hypergraphs $\mathcal{H}^{(1)},\ldots, \mathcal{H}^{(m)}$ satisfy a \emph{balancedness} condition and have low \emph{pair visibility}, then after allocating $m=Θ(n)$ balls, the maximum number of balls at any bin, called the \emph{maximum load}, is at most $\log_d\log n+O(1)$ , with high probability. The balancedness condition enforces that bins appear almost uniformly within the hyperedges of $\mathcal{H}^{(t)}$ , $1\le t\le m$ , while the pair visibility condition measures how frequently a pair of bins is chosen during the allocation of balls. Moreover, we establish a lower bound for the maximum load attained by the balanced allocation for a sequence of hypergraphs in terms of pair visibility, showing the relevance of the visibility parameter to the maximum load. In Godfrey's model, each ball is forced to probe all bins in a randomly selected hyperedge and the ball is then allocated in a least-loaded bin. Godfrey showed that if each $\mathcal{H}^{(t)}$ , $1\le t\le m$ , is balanced and $m=O(n)$ , then the maximum load is at most one, with high probability. However, we apply the power of $d$ choices paradigm, and only query the load information of $d$ random bins per ball, while achieving very slow growth in the maximum load.

preprint2022arXiv

Degree sequences of sufficiently dense random uniform hypergraphs

We find an asymptotic enumeration formula for the number of simple $r$ -uniform hypergraphs with a given degree sequence, when the number of edges is sufficiently large. The formula is given in terms of the solution of a system of equations. We give sufficient conditions on the degree sequence which guarantee existence of a solution to this system. Furthermore, we solve the system and give an explicit asymptotic formula when the degree sequence is close to regular. This allows us to establish several properties of the degree sequence of a random $r$ -uniform hypergraph with a given number of edges. More specifically, we compare the degree sequence of a random $r$ -uniform hypergraph with a given number edges to certain models involving sequences of binomial or hypergeometric random variables conditioned on their sum.

preprint2020arXiv

Threshold functions for substructures in random subsets of finite vector spaces

The study of substructures in random objects has a long history, beginning with Erdős and Rényi's work on subgraphs of random graphs. We study the existence of certain substructures in random subsets of vector spaces over finite fields. First we provide a general framework which can be applied to establish coarse threshold results and prove a limiting Poisson distribution at the threshold scale. To illustrate our framework we apply our results to $k$ -term arithmetic progressions, sums, right triangles, parallelograms and affine planes. We also find coarse thresholds for the property that a random subset of a finite vector space is sum-free, or is a Sidon set.

preprint2016arXiv

Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees

A hypergraph is simple if it has no loops and no repeated edges, and a hypergraph is linear if it is simple and each pair of edges intersects in at most one vertex. For $n\geq 3$ , let $r= r(n)\geq 3$ be an integer and let $\boldsymbol{k} = (k_1,\ldots, k_n)$ be a vector of nonnegative integers, where each $k_j = k_j(n)$ may depend on $n$ . Let $M = M(n) = \sum_{j=1}^n k_j$ for all $n\geq 3$ , and define the set $\mathcal{I} = \{ n\geq 3 \mid r(n) \text{ divides } M(n)\}$ . We assume that $\mathcal{I}$ is infinite, and perform asymptotics as $n$ tends to infinity along $\mathcal{I}$ . Our main result is an asymptotic enumeration formula for linear $r$ -uniform hypergraphs with degree sequence $\boldsymbol{k}$ . This formula holds whenever the maximum degree $k_{\max}$ satisfies $r^4 k_{\max}^4(k_{\max} + r) = o(M)$ . Our approach is to work with the incidence matrix of a hypergraph, interpreted as the biadjacency matrix of a bipartite graph, enabling us to apply known enumeration results for bipartite graphs. This approach also leads to a new asymptotic enumeration formula for simple uniform hypergraphs with specified degrees, and a result regarding the girth of random bipartite graphs with specified degrees.

preprint2015arXiv

Asymptotic enumeration of sparse uniform hypergraphs with given degrees

Let $r \geq 2$ be a fixed integer. For infinitely many $n$ , let $\boldsymbol{k} = (k_1,..., k_n)$ be a vector of nonnegative integers such that their sum $M$ is divisible by $r$ . We present an asymptotic enumeration formula for simple $r$ -uniform hypergraphs with degree sequence $k$ . (Here "simple" means that all edges are distinct and no edge contains a repeated vertex.) Our formula holds whenever the maximum degree $k_{\mathrm{max}}$ satisfies $k_{\mathrm{max}}^3 = o(M)$ .

preprint2015arXiv

On the chromatic number of a random hypergraph

We consider the problem of $k$ -colouring a random $r$ -uniform hypergraph with $n$ vertices and $cn$ edges, where $k$ , $r$ , $c$ remain constant as $n$ tends to infinity. Achlioptas and Naor showed that the chromatic number of a random graph in this setting, the case $r=2$ , must have one of two easily computable values as $n$ tends to infinity. We give a complete generalisation of this result to random uniform hypergraphs.

preprint2014arXiv

Mixing of the Glauber dynamics for the ferromagnetic Potts model

We present several results on the mixing time of the Glauber dynamics for sampling from the Gibbs distribution in the ferromagnetic Potts model. At a fixed temperature and interaction strength, we study the interplay between the maximum degree ( $Δ$ ) of the underlying graph and the number of colours or spins ( $q$ ) in determining whether the dynamics mixes rapidly or not. We find a lower bound $L$ on the number of colours such that Glauber dynamics is rapidly mixing if at least $L$ colours are used. We give a closely-matching upper bound $U$ on the number of colours such that with probability that tends to 1, the Glauber dynamics mixes slowly on random $Δ$ -regular graphs when at most $U$ colours are used. We show that our bounds can be improved if we restrict attention to certain types of graphs of maximum degree $Δ$ , e.g. toroidal grids for $Δ= 4$ .

preprint2014arXiv

Structure and eigenvalues of heat-bath Markov chains

We prove that heat-bath chains (which we define in a general setting) have no negative eigenvalues. Two applications of this result are presented: one to single-site heat-bath chains for spin systems and one to a heat-bath Markov chain for sampling contingency tables. Some implications of our main result for the analysis of the mixing time of heat-bath Markov chains are discussed. We also prove an alternative characterisation of heat-bath chains, and consider possible generalisations.

preprint2014arXiv

The switch Markov chain for sampling irregular graphs

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 $d_{\max}$ which satisfies $3\leq d_{\max}\leq \frac{1}{4}\, \sqrt{M}$ , 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.

preprint2013arXiv

Asymptotic enumeration of sparse multigraphs with given degrees

Let J and J* be subsets of Z+ such that 0,1\in J and 0\in J*. For infinitely many n, let k=(k_1,..., 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,..., n} with degree sequence given by k, such that every loop has multiplicity in J* and every non-loop 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 satisfies K = o(M^(1/3)). We prove this result using the switching method, building on an asymptotic enumeration of simple graphs with given degrees (McKay and Wormald, 1991). Our application of the switching method introduces a novel way of combining several different switching operations into a single computation.

preprint2013arXiv

Making Markov chains less lazy

The mixing time of an ergodic, reversible Markov chain can be bounded in terms of the eigenvalues of the chain: specifically, the second-largest eigenvalue and the smallest eigenvalue. It has become standard to focus only on the second-largest eigenvalue, by making the Markov chain "lazy". (A lazy chain does nothing at each step with probability at least 1/2, and has only nonnegative eigenvalues.) An alternative approach to bounding the smallest eigenvalue was given by Diaconis and Stroock and Diaconis and Saloff-Coste. We give examples to show that using this approach it can be quite easy to obtain a bound on the smallest eigenvalue of a combinatorial Markov chain which is several orders of magnitude below the best-known bound on the second-largest eigenvalue.

preprint2012arXiv

Asymptotic enumeration of sparse nonnegative integer matrices with specified row and column sums

Let \svec = (s_1,...,s_m) and \tvec = (t_1,...,t_n) be vectors of nonnegative integer-valued functions of m,n with equal sum S = sum_{i=1}^m s_i = sum_{j=1}^n t_j. Let M(\svec,\tvec) be the number of m*n matrices with nonnegative integer entries such that the i-th row has row sum s_i and the j-th column has column sum t_j for all i,j. Such matrices occur in many different settings, an important example being the contingency tables (also called frequency tables) important in statistics. Define s=max_i s_i and t=max_j t_j. Previous work has established the asymptotic value of M(\svec,\tvec) as m,n\to\infty with s and t bounded (various authors independently, 1971-1974), and when \svec,\tvec are constant vectors with m/n,n/m,s/n >= c/log n for sufficiently large (Canfield and McKay, 2007). In this paper we extend the sparse range to the case st=o(S^(2/3)). The proof in part follows a previous asymptotic enumeration of 0-1 matrices under the same conditions (Greenhill, McKay and Wang, 2006). We also generalise the enumeration to matrices over any subset of the nonnegative integers that includes 0 and 1.

preprint2012arXiv

Corrigendum: Sampling regular graphs and a peer-to-peer network

In [Combinatorics, Probability and Computing 16 (2007), 557 - 593, Theorem 1] we proved a polynomial-time bound on the mixing rate of the switch chain for sampling d-regular graphs. This corrigendum corrects a technical error in the proof. In order to fix the error, we must multiply the bound on the mixing time by a factor of d^8 .

preprint2011arXiv

A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs

The switch chain is a well-known Markov chain for sampling directed graphs with a given degree sequence. While not ergodic in general, we show that it is ergodic for regular degree sequences. We then prove that the switch chain is rapidly mixing for regular directed graphs of degree d, where d is any positive integer-valued function of the number of vertices. We bound the mixing time by bounding the eigenvalues of the chain. A new result is presented and applied to bound the smallest (most negative) eigenvalue. This result is a modification of a lemma by Diaconis and Stroock, and by using it we avoid working with a lazy chain. A multicommodity flow argument is used to bound the second-largest eigenvalue of the chain. This argument is based on the analysis of a related Markov chain for undirected regular graphs by Cooper, Dyer and Greenhill, but with significant extension required.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Catherine Greenhill

Research overview

Is this your work?

15 publications

Asymptotic enumeration of constrained bipartite, directed and oriented graphs by degree sequence

Balanced Allocation on Hypergraphs

Degree sequences of sufficiently dense random uniform hypergraphs

Threshold functions for substructures in random subsets of finite vector spaces

Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees

Asymptotic enumeration of sparse uniform hypergraphs with given degrees

On the chromatic number of a random hypergraph

Mixing of the Glauber dynamics for the ferromagnetic Potts model

Structure and eigenvalues of heat-bath Markov chains

The switch Markov chain for sampling irregular graphs

Asymptotic enumeration of sparse multigraphs with given degrees

Making Markov chains less lazy

Asymptotic enumeration of sparse nonnegative integer matrices with specified row and column sums

Corrigendum: Sampling regular graphs and a peer-to-peer network

A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs

See the researcher in context

Building this map preview