Absorptions in combinatorics

Thesis

This thesis mainly focuses on the following transversal problem, which is closely related to the absorption technique in extremal combinatorics: Given a collection of simple graphs G₁, . . . , G_t defined on the same vertex set V, where each graph G_i (1 ≤ i ≤ t) satisfies some property P, can we find a copy of any graph F of order |V| with at most t edges in V, such that the edges of F are chosen from different G_i's?

We provide frameworks and techniques for such problems when each G_i (1 ≤ i ≤ t) is dense in V. First, we generalize the traditional absorption technique to graph collections, which allows us to modify the original absorption structure to obtain a new absorption structure that is helpful for transversal problems. Second, we establish regularity tools for graph collections. One of the key lemmas we prove is a blow-up result for transversal structures. This allows us to demonstrate more complicated results when the absorption technique does not apply.

We will further show two direct applications. One is a new proof of the asymptotic solution to the transversal Pósa-Seymour conjecture. The other is a stability result for Ahroni's conjecture on transversal Hamilton cycles.

Authors: Cheng, Y

• DOI: 10.5287/ora-zrqx4mwvq
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Subjects: Combinatorics