Abstract
dc:description.abstractIn this thesis we present new results in graph and hypergraph theory all of which feature paths or cycles. A \(k\)-uniform tight cycle C(k)n is a \(k\)-uniform hypergraph on \(n\) vertices with a cyclic ordering of its vertices such that the edges are all \(k\)-sets of consecutive vertices in the ordering. We consider a generalisation of Lehel's Conjecture, which states that every 2-edge-coloured complete graph can be partitioned into two cycles of distinct colour, to \(k\)-uniform hypergraphs and prove results in the 4- and 5-uniform case. For a \(k\)-uniform hypergraph~\(H\), the Ramsey number \({r(H)}\) is the smallest integer \(N\) such that any 2-edge-colouring of the complete \(k\)-uniform hypergraph on \(N\) vertices contains a monochromatic copy of \(H\). We determine the Ramsey number for 4-uniform tight cycles asymptotically in the case where the length of the cycle is divisible by 4, by showing that r(C(4)n) = (5+\(o\)(1))\(n\). We prove a resilience result for tight Hamiltonicity in random hypergraphs. More precisely, we show that for any γ >0 and \(k\) \(\geq\) 3 asymptotically almost surely, every subgraph of the binomial random \(k\)-uniform hypergraph G(k)(n, nγ -1) in which all \((k-1)\)-sets are contained in at least (\frac{1}{2}+2γ)pn edges has a tight Hamilton cycle. A random graph model on a host graph \(H\) is said to be 1-independent if for every pair of vertex-disjoint subsets \(A,B\) of \(E(H)\), the state of edges (absent or present) in \(A\) is independent of the state of edges in \(B\). We show that \(p\) = 4 - 2\(\sqrt{3}\) is the critical probability such that every 1-independent graph model on \mathbb{Z}2 \times Kn where each edge is present with probability at least \(p\) contains an infinite path.
Degree
thesis:*- Name dc:type.qualificationname
- d_ph
- Level dc:type.qualificationlevel
- d_ph
- Grantor dc:publisher.institution
- University of Birmingham
- Year dc:date.issued
- 2023
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Pfenninger, Vincent
Subjects
dc:subject × 1Rights
- Language dc:language.dcterms_iso639_2
- eng