Asymptotic enumeration of sparse uniform hypergraphs, with applications

Abstract

A hypergraph is a generalisation of a graph where the edges may contain more than two vertices. This thesis concentrates on asymptotic enumeration of some families of sparse uniform hypergraphs, when the number of vertices is sufficiently large and each vertex degree is given. Our first result gives an asymptotic formula for the number of simple uniform hypergraphs with a given degree sequence which contain no edges of another specified hypergraph. This formula holds under some restrictions on the number of forbidden edges, and the maximum degree and edge size of the hypergraph. We apply a combinatorial argument known as the switching method to obtain our estimates.

This formula allows us to calculate the probability that a random uniform hypergraph with given degrees contains a specified set of edges. As a result, we find an asymptotic formula for the expected number of perfect matchings and the expected number of loose Hamilton cycles in random regular uniform hypergraphs. As another application of our first result, we study the average number of uniform spanning hypertrees.

Finally, we give a new proof of Blinovsky and Greenhill's asymptotic formula for the number of sparse linear uniform hypergraphs with given degrees. Our proof uses a more complicated switching and extends the range of degrees and edge size for which the formula holds.