Paths and cycles in graphs and hypergraphs

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

Preview

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 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 $\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 $(k-1)$ -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 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 K_n$ where each edge is present with probability at least $p$ contains an infinite path.