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)=nr1 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)=nr1 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
nk1
. 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
Authors
Behague, Natalie C.Collections
- Theses [4248]