dc.contributor.author | Behague, Natalie C. | |
dc.date.accessioned | 2020-11-16T15:42:46Z | |
dc.date.available | 2020-11-16T15:42:46Z | |
dc.date.issued | 2020 | |
dc.identifier.uri | https://qmro.qmul.ac.uk/xmlui/handle/123456789/68332 | |
dc.description | PhD Thesis | en_US |
dc.description.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 | en_US |
dc.language.iso | en | en_US |
dc.publisher | Queen Mary University of London | en_US |
dc.title | Topics in Extremal and Probabilistic Combinatorics. | en_US |
dc.type | Thesis | en_US |
rioxxterms.funder | Default funder | en_US |
rioxxterms.identifier.project | Default project | en_US |