On resolvable decomposition problems

Oviedo Timoneda, Pablo (2024). On resolvable decomposition problems. University of Birmingham. Ph.D.

OviedoTimoneda2024PhD.pdf
Text - Accepted Version
Available under License All rights reserved.
Download (1MB)

Abstract

Given graphs \(F\) and \(G\), a resolvable \(F\)-decomposition of \(G\) is a partition of its edges into \(F\)-factors. We study the existence of resolvable cycle and clique decompositions in graphs with high minimum degree and pseudo-random graphs.
We show a Dirac-type result for the uniform case of the Oberwolfach problem and make progress towards a conjecture by Glock, Joos, Kim, Kühn and Osthus. Specifically, we prove that for any \(\alpha>0\) there is an integer \(r_0\) such that for any \(r\geq r_0\), any sufficiently large graph \(G\) on \(n\) vertices, with \(r\mid n\), even degree, and minimum degree \((1/2+\alpha)n\), has a resolvable \(C_r\)-decomposition. The term \(1/2\) in the minimum degree bound is best possible.
We show that any sufficiently large pseudo-random graph that satisfies the necessary divisibility conditions has a resolvable \(K_r\)-decomposition.
We also prove the analogue for multipartite graphs. That is, any sufficiently large \(r\)-partite pseudo-random graph that satisfies the necessary divisibility conditions has a resolvable \(K_r\)-decomposition.
Our methods are purely combinatorial and combine iterative absorption with a new technique on finding a fractional decomposition in an extended graph.
Finally, we discuss the consequences of our results and some potential applications of the methods into other resolvable decomposition problems.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):