Colourings, dominating sets and wreaths

Abstract

In this thesis, we explore various topics and techniques in Combinatorics and Graph Theory. After an introductory chapter, in Chapter $2$ we consider an extremal problem concerning dominating sets. We show that all forests with a given domination number $\gamma$ have at most ${5}^{\gamma/2}$ minimum dominating sets. Furthermore, for each $\gamma$, we construct a tree with domination number $\gamma$ which has more than $\frac{2}{5}{5}^{\gamma/2}$ minimum dominating sets. We also disprove a conjecture by Henning, Mohr and Rautenbach about the maximum number of minimum total dominating sets in a tree. Chapter $3$ concerns an extremal problem about sets with restrictions to their sizes. Motivated by the recently introduced notion of odd-sunflowers due to Frankl, Pach, and Pálvölgyi, we investigate the maximum possible size of a family $\mathcal{F}$ of subsets of $[n]$ where each set $A \in \mathcal{F}$ contains at most $|A|$ other elements of $\mathcal{F}$ as a subset. We show that the maximum size is attained by the middle two layers of the hypercube and characterise all the maximizing families. Moreover, we explore a more general notion as well as well as the case in which $\mathcal{F}$ satisfies the further condition that it is intersecting. Chapter $4$ is about an ``odd'' variant of graph colourings. A proper colouring $\varphi$ of a graph $G$ is an \emph{odd colouring} if for every non-isolated vertex $v \in V(G)$ there is a colour $c$ such that $|N(v)\cap \varphi^{-1}(c)|$ is odd. The \emph{odd chromatic number} of $G$ is the smallest $k$ such that there is an odd colouring of $G$ using $k$ colours. Building on the work of Aashtab, Akbari, Ghanbari and Shidani and of Caro, Petruševski and Škrekovski, as well as utilizing the discharging method, we show that the odd chromatic number of a planar graph is at most $8$. Chapter $5$ is a short detour into an application of Graph Theory to Physics. We show that the pyrochlore lattice does not contain an induced copy of the countably infinite $4$-regular triangular cactus. The final topic, covered in Chapter $6$, is the \emph{wreath conjecture} due to Baranyai. For $k \leq n$, an \emph{$(n,k)$-wreath} -- briefly, a \emph{wreath} -- is a subset of $\mathbb{Z}_n^{(k)}$ of a particular form. The wreath conjecture states that $\mathbb{Z}_n^{(k)}$ can be decomposed into disjoint wreaths. To attack the wreath conjecture, we define the \emph{wreath matrix} as the square matrix indexed by wreaths, with the $(i,j)$-th entry being the size of the intersection of the two corresponding wreaths. We compute the dimensions of every eigenspace of the wreath matrix and find a recursive formula for its eigenvalues, which all turn out to be integers. We also discuss more of its properties. Finally, we conjecture a connection between the wreath conjecture when $n=2k+1$ and Dyck paths, verifying its plausibility by computing a related statistic on Dyck paths. The results in this thesis are based on joint work with Julien Portier (Chapters $2$ and $4$), Pavel Turek (Chapters $3$ and $6$) and Leo Versteegen (Chapter $2$). Chapter $5$ benefited immensely from discussions with Cecilie Glittum.