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): | Supervisor(s) Email ORCID Kühn, Daniela UNSPECIFIED UNSPECIFIED Osthus, Deryk UNSPECIFIED UNSPECIFIED |
| Licence: | All rights reserved |
| College/Faculty: | Colleges > College of Engineering & Physical Sciences |
| School or Department: | School of Mathematics |
| Funders: | European Research Council |
| Subjects: | Q Science > QA Mathematics |
| URI: | https://bham-theses.eprints-hosting.org/id/eprint/15642 |
Actions
![]() |
Request a Correction |
![]() |
View Item |
Downloads
Downloads per month over past year
Tools
Tools
