Topics in Extremal and Probabilistic Combinatorics.

Abstract

This thesis encompasses several problems in extremal and probabilistic combinatorics. Chapter 1. Tuza's famous conjecture on the saturation number states that for r-uniform hypergraphs F the value sat(F; n)=nrð€€€1 converges. I answer a question of Pikhurko concerning the asymptotics of the saturation number for families of hypergraphs, proving in particular that sat(F; n)=nrð€€€1 need not converge if F is a family of r-uniform hypergraphs. Chapter 2. Cern y's conjecture on the length of the shortest reset word of a synchronizing automaton is arguably the most long-standing open problem in the theory of nite automata. We consider the minimal length of a word that resets some k-tuple. We prove that for general automata if this is nite then it is ð€€€ nkð€€€1

. For synchronizing automata we improve the upper bound on the minimal length of a word that resets some triple. Chapter 3. The existence of perfect 1-factorizations has been studied for various families of graphs, with perhaps the most famous open problem in the area being Kotzig's conjecture which states that even-order complete graphs have a perfect 1-factorization. In my work I focus on another well-studied family of graphs: the hypercubes. I answer almost fully the question of how close (in some particular sense) to perfect a 1-factorization of the hypercube can be. Chapter 4. The k-nearest neighbour random geometric graph model puts vertices randomly in a d-dimensional box and joins each vertex to its k nearest neighbours. I nd signi cantly improved upper and lower bounds on the threshold for connectivity for the k-nearest neighbour graph in high dimensions. iii