Asymptotic enumeration of sparse uniform hypergraphs, with applications

Download files
Access & Terms of Use
open access
Copyright: Aldosari, Haya
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.
Persistent link to this record
Link to Publisher Version
Additional Link
Author(s)
Aldosari, Haya
Supervisor(s)
Greenhill, Catherine
Creator(s)
Editor(s)
Translator(s)
Curator(s)
Designer(s)
Arranger(s)
Composer(s)
Recordist(s)
Conference Proceedings Editor(s)
Other Contributor(s)
Corporate/Industry Contributor(s)
Publication Year
2020
Resource Type
Thesis
Degree Type
PhD Doctorate
UNSW Faculty
Files
download public version.pdf 918.41 KB Adobe Portable Document Format
Related dataset(s)