Pfenninger, Vincent (2023). Paths and cycles in graphs and hypergraphs. University of Birmingham. Ph.D.

Pfenninger2023PhD.pdf
Text  Accepted Version Available under License All rights reserved. Download (1MB)  Preview 
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 2edgecoloured complete graph can be partitioned into two cycles of distinct colour, to \(k\)uniform hypergraphs and prove results in the 4 and 5uniform case.
For a \(k\)uniform hypergraph~\(H\), the Ramsey number \({r(H)}\) is the smallest integer \(N\) such that any 2edgecolouring of the complete \(k\)uniform hypergraph on \(N\) vertices contains a monochromatic copy of \(H\). We determine the Ramsey number for 4uniform 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 \(\gamma\) >0 and \(k\) \(\geq\) 3 asymptotically almost surely, every subgraph of the binomial random \(k\)uniform hypergraph \(G^{(k)}(n, n^{\gamma 1})\) in which all \((k1)\)sets are contained in at least \((\frac{1}{2}+2\gamma)pn\) edges has a tight Hamilton cycle.
A random graph model on a host graph \(H\) is said to be 1independent if for every pair of vertexdisjoint 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 1independent graph model on \(\mathbb{Z}^2 \times K_n\) where each edge is present with probability at least \(p\) contains an infinite path.
Type of Work:  Thesis (Doctorates > Ph.D.)  

Award Type:  Doctorates > Ph.D.  
Supervisor(s): 


Licence:  All rights reserved  
College/Faculty:  Colleges (2008 onwards) > College of Engineering & Physical Sciences  
School or Department:  School of Mathematics  
Funders:  Engineering and Physical Sciences Research Council  
Subjects:  Q Science > QA Mathematics  
URI:  http://etheses.bham.ac.uk/id/eprint/13250 
Actions
Request a Correction  
View Item 
Downloads
Downloads per month over past year