Extremal and probabilistic problems for discrete structures

Freschi, Andrea ORCID: 0000-0003-4993-7411 (2025). Extremal and probabilistic problems for discrete structures. University of Birmingham. Ph.D.

Preview

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

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.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):