Back to search

University of Birmingham

Paths and cycles in graphs and hypergraphs

Abstract

dc:description.abstract

In 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 × 1

Rights

Language dc:language.dcterms_iso639_2
eng

Chain of custody

source
Harvested from
University of Birmingham
Base URL
etheses.bham.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Pfenninger, Vincent. Paths and cycles in graphs and hypergraphs. d_ph thesis, University of Birmingham, 2023.