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.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):