Library Header Image
LSE Theses Online London School of Economics web site

On some problems in extremal hypergraph theory

Sgueglia, Amedeo (2022) On some problems in extremal hypergraph theory. PhD thesis, London School of Economics and Political Science.

[img] Text - Submitted Version
Download (1MB)
Identification Number: 10.21953/lse.00004460


In this thesis, we study several problems in extremal (hyper)graph theory. We begin by investigating the problem of subgraph containment in the model of randomly perturbed graphs. In particular, we study the perturbed threshold for the appearance of the square of a Hamilton cycle and the problem of finding pairwise vertex-disjoint triangles. We provide a stability version of these results and we discuss their implications on the perturbed thresholds for 2-universality and for a triangle factor. We then turn to the notion of threshold in the context of transversals in hypergraph collections. Here the question is, given a fixed m-edge hypergraph F, how large the minimum degree of each hypergraph Hi needs to be, so that the hypergraph collection (H1, …, Hm) necessarily contains a transversal copy of F. We prove a widely applicable sufficient condition on F such that the following holds. The needed minimum degree is asymptotically the same as the minimum degree required for a copy of F to appear in each Hi. The condition is general enough to obtain transversal variants of various classical Dirac-type results for (powers of) Hamilton cycles. Finally, we initiate the study of a new variant of the Maker-Breaker positional game, which we call the (1:b) multistage Maker-Breaker game. Starting with a given hypergraph, we play several stages of a usual (1:b) Maker-Breaker game where, in each stage, we shrink the board by keeping only the elements that Maker claimed in the previous stage and updating the collection of winning sets accordingly. The game proceeds until no winning sets remain, and the goal of Maker is to prolong the duration of the game for as many stages as possible. We estimate the maximum duration of the (1:b) multistage Maker-Breaker game for several standard graph games played on the edge set of Kn with biases b subpolynomial in n.

Item Type: Thesis (PhD)
Additional Information: © 2022 Amedeo Sgueglia
Library of Congress subject classification: Q Science > QA Mathematics
Sets: Departments > Mathematics
Supervisor: Böttcher, Julia and Skokan, Jozef

Actions (login required)

Record administration - authorised staff only Record administration - authorised staff only


Downloads per month over past year

View more statistics