Back to search

University of Birmingham

Extremal and probabilistic problems for discrete structures

Abstract

dc:description.abstract

In this thesis we present a collection of new results in extremal and probabilistic combinatorics. More precisely, we answer various questions from the following five topics. The first topic is graph discrepancy. Balogh, Csaba, Jing and Pluh´ ar determined the minimum degree threshold that ensures a 2-edge-coloured graph G contains a Hamilton cycle with large discrepancy, that is, a Hamilton cycle with significantly more than half of its edges in one colour. We prove an analogous result for r-colourings. The second topic is the study of Dirac-type problems for (vertex) ordered graphs. For any fixed ordered graph H, we determine the asymptotic minimum degree threshold for forcing (i) a perfect H-tiling in an ordered graph, under the assumption that χ<(H) ≥ 3; (ii) an H-tiling in an ordered graph G covering a fixed proportion of the vertices of G; (iii) an H-cover in an ordered graph. Our results combined with the work of Balogh, Li and Treglown determine completely the asymptotic minimum degree thresholds for forcing a perfect H-tiling and an almost perfect H-tiling in an ordered graph (for any fixed ordered graph H). The third topic is graph deficiency. Given a property P, the deficiency def(G) of a graph G with respect to P is the smallest non-negative integer t such that G ∗ Kt has property P, where G ∗ Kt is the graph obtained by adding t new vertices to G and all edges incident to such vertices. This notion was introduced by Nenadov, Sudakov and Wagner, who raised the question of determining how many edges an n-vertex graph G needs to ensure G ∗ Kt contains a Kr-factor (for any fixed r ≥ 3). We present a full resolution of this problem. The fourth topic is saturation for induced posets. For a fixed poset P, a family F of subsets of [n] := {1,2,...,n} is induced P-saturated if F does not contain an induced copy of P and, for every subset S of [n] such that S ̸∈ F, the family F ∪{S} does containan induced copy of P. The size of the smallest such family F is denoted by sat∗(n,P). Keszegh, Lemons, Martin, P´alv¨ olgyi and Patk´os proved that there is a dichotomy of behaviour for this parameter: for any poset P, either sat∗(n,P) = O(1) or sat∗(n,P) ≥ log2 n. Furthermore, they conjectured that the log2 n term can be replaced with n + 1. We make progress towards this conjecture by showing that either sat∗(n,P) = O(1) or sat∗(n,P) ≥ min{2√n,n/2 + 1}. Our proof makes use of a Tur´ an-type result for digraphs. We also prove that the aforementioned conjecture holds for a certain class of posets P and determine the exact value of sat∗(n,P) in some cases. The fifth topic is the study of typical Ramsey properties of abelian groups. A classical result of Rado characterises all integer matrices A such that any finite colouring of N yields a monochromatic solution to the system of equations Ax = 0. R¨odl and Ruci´nski, and Friedgut, R¨odl and Schacht proved a random version of Rado’s theorem where one considers a random subset of [n] instead of N. We investigate the analogous random Ramsey problem in the more general setting of abelian groups: given a sequence (Sn)n∈N of finite subsets of abelian groups and a positive integer r ≥ 2, we are interested in determining the probability threshold ˆ p := ˆ p(n) such that Any r-colouring of Sn,p yields a lim n→∞ P    monochromatic solution to Ax = 0.    =        0 if p=o(ˆ p), 1 if p=ω(ˆ p). where Sn,p denotes the random subset of Sn obtained by including each element of Sn with probability p, independently. We develop a general black box, which we refer to as the random Rado lemma, to tackle problems of this type. Among various applications, we obtain a random version of the van der Waerden theorem for the primes (a consequence of the Green–Tao theorem) and an integer lattice generalisation of the random version of Rado’s theorem (using a novel supersaturation result for Sn := [n]d). Furthermore, we prove a 1-statement and a 0-statement for hypergraphs that imply several of the previously known 1- and 0-statements in various settings, as well as the random Rado lemma.

Degree

thesis:*
Name dc:type.qualificationname
d_ph
Level dc:type.qualificationlevel
d_ph
Grantor dc:publisher.institution
University of Birmingham
Year dc:date.issued
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Freschi, Andrea
ORCID person:identifier.orcid

Subjects

dc:subject × 1

Rights

Language dc:language.dcterms_iso639_2
eng

Chain of custody

source
Harvested from
University of Birmingham
Base URL
etheses.bham.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Freschi, Andrea. Extremal and probabilistic problems for discrete structures. d_ph thesis, University of Birmingham, 2025.