Σ-hypergraphs : colouring, independence, matchings and hamiltonicity

Abstract

A hypergraph H is a nite set V (H) of vertices together with a family E(H) of subsets of V (H) called hyperedges (or simply edges). An r-uniform hypergraph is one in which all the edges are of the same size r. So a standard graph can be defined as a 2-uniform hypergraph. Hypergraphs arose naturally as an extension to graphs, with the main intent of extending important and interesting results from Graph Theory to this generalised setting. The results were sometimes simplified, and in other instances unexpected. In this thesis we study various properties of a special family of hypergraphs, the -hypergraphs, a generalisation of -hypergraphs, first defined by Caro and Lauri and studied in the context of Voloshin colourings, focusing mainly on non-monochromatic-non-rainbow (NMNR) colourings. The most interesting aspect of these types of colourings is arguably the appearance of gaps in the chromatic spectrum of the hypergraph. Results in this area of study often required ad-hoc and complex hypergraph structures such as designs. Both - and -hypergraphs proved to be a simple unifying construction in this respect giving interesting results and chromatic spectra by controlling the parameters which define the structure. Furthermore, they also proved to have interesting properties with respect to other hypergraph theoretic properties such as independence, matchings and Hamiltonicity, as we shall see in this thesis.