Extremal, Probabilistic, and Infinitary Problems in Combinatorics

This dissertation consists of an introduction and six chapters, covering a variety of combinatorial problems, with common themes running throughout. Chapter 2 is devoted to the study of partially ordered sets, or posets, in particular the structure of chains and antichains in infinite posets. A poset P is said to satisfy the finite antichain condition, or FAC, if it has no infinite antichain. It was conjectured by Aharoni and Korman in 1992 that any FAC poset P possesses a chain C and a partition into antichains such that C meets every antichain of the partition. Our main results are twofold. We provide a counterexample to the conjecture but, despite this, we also prove that the conjecture does hold true for a broad class of posets. In particular, we prove that the Aharoni–Korman conjecture holds for countable posets avoiding intervals I such that either I or its reverse I* is of the form ⊕x∈ω Qx, where each Qx is infinite and co-wellfounded. In pursuit of these goals, we also investigate other facets of the structure of FAC posets. In particular, we consider strongly maximal chains in FAC posets, proving some results, and posing several questions and conjectures. In Chapter 3, we address several related problems on combinatorial discrepancy of trees in a setting introduced by Erdős, Füredi, Loebl, and Sós. Given a fixed tree T on n vertices and an edge-colouring of the complete graph Kn, for every colour, we find a copy of T in Kn where the number of edges in that colour significantly exceeds its expected count in a uniformly random embedding. In particular, this resolves a problem posed by Erdős, Füredi, Loebl, and Sós by generalising their work from two to more colours. Furthermore, if T has maximum degree ∆ ≤ εn for sufficiently small ε > 0 and the edge-colouring of Kn is both balanced and “not too close” to one particular colouring, we show that, for every colour i, there is a copy of T in Kn where colour i appears on Θ(n) more edges than any other colour. Several related examples are provided to demonstrate the necessity of the introduced structural restrictions. Moreover, when ∆ is a constant, we extend these results to sufficiently dense host graphs in place of Kn. Our proofs combine saturation arguments for the existence of particular coloured substructures and analysis of conveniently defined local exchanges. Using similar methods, we investigate the existence of copies of a graph H with prescribed number of edges in each colour inside 2-edge-coloured dense host graphs. In particular, for a graph H with bounded maximum degree and balanced 2-edge-colourings c of a host graph G with minimum degree at least (1 − ε)n for some ε > 0, we show that, for any sufficiently large n and sufficiently small ε, there exists a copy of H where the number of edges in the two colours differ by at most 2. Moreover, we completely characterise the pairs (H, c) for which the difference of 2 cannot be improved. As a consequence, we refute a conjecture by Mohr, Pardey, and Rautenbach. In Chapter 4, we are interested in finding a colour-balanced perfect matching within a colour-balanced complete graph K_(2nk) with a palette of k colours. An edge-colouring of a graph G is said to be colour-balanced if there are equally many edges of each available colour. While it is not necessarily possible to find such a perfect matching, one can ask for a perfect matching as close to colour-balanced as possible. In particular, for a colour-balanced colouring c : E(K2nk) → [k], we seek to find a perfect matching M minimising f(M) := Σ_(i=1)^k |c^(−1)(i) ∩ M| − n . The previous best upper bound, due to Pardey and Rautenbach, was min f(M) ≤ O(k√nk log k). We remove the n-dependence, proving the existence of a matching M with f(M) ≤ 4^(k^2) for all k. In Chapter 5, we provide an extended abstract of a series of results centred around Rademacher sums. The object of interest is P(Σ_(i=1)^n ξ_i v_i ∈ S), where ξ_i are independent random variables sampled uniformly on {−1, +1}, each v_i is a vector in R^d for some fixed d, and S is some set. We first consider anti-concentration probabilities of the form P(|X| ≥ x), where X = Σ_(i=1)^n a_i ξ_i and a_i are positive real constants normalised so Σ_(i=1)^n a_i^2 = 1. We determine the value of inf_X P(|X| ≥ x) for all values x ≥ 0, giving a partial answer to a question by Keller and Klein. In particular, for x = 1, we prove the optimal lower bound P(|X| ≥ 1) ≥ 7/32, which improves on a sequence of results by Burkholder, Oleszkiewicz, Hitczenko and Kwapién, and Dvořák and Klein, and confirms a 1994 conjecture of Hitczenko and Kwapién. We then move on to consider the case of d ≥ 2, and investigate a 1945 conjecture of Erdős, which states that, for any unit vectors v_1, . . . , v_n in R2, the sum σ = Σ_(i=1)^n ξ_i v_i satisfies ∥σ∥_2 ≤ 1 with probability Ω(1/n). While this conjecture is false for even n, Beck has proved that ∥σ∥_2 ≤ √2 always holds with probability Ω(1/n). Recently, He, Juškevičius, Narayanan, and Spiro conjectured that the Erdős’ conjecture holds when n is odd. We disprove this conjecture by exhibiting vectors v_1, . . . , v_n for which ∥σ∥_2 ≤ 1 occurs with probability O(2^(−n/2)). On the other hand, an approximated version of their conjecture holds: we show that we always have ∥σ∥_2 ≤ 1 + δ with probability Ω_δ(1/n), for all δ > 0. This shows that, when n is odd, the minimum probability that ∥σ∥_2 ≤ r exhibits a double-jump phase transition at r = 1, as we can also show that ∥σ∥_2 ≤ 1 occurs with probability at least Ω((1/2 + µ)^n) for some µ > 0. Additionally, and using a different construction, we give a negative answer to a question of Beck and two other questions of He, Juškevičius, Narayanan, and Spiro, concerning the optimal constructions minimising the probability that ∥σ∥_2 ≤ √2. We also make some progress on the higher dimensional versions of these questions. Finally, we demonstrate that the parity of n continues to be a significant factor for dimensions d ≥ 3. In particular, we prove that, for any d ≥ 3, there is some ε = ε(d) > 0 such that for any n̸ ≡ d (mod 2) and unit vectors v_1, . . . , v_n ∈ R^d, there are signs η_1, . . . , η_n ∈ {−1, +1} such that ∥ Σ_(i=1)^n η_i v_i∥ ≤ √(d − ε), and so P(∥ξ_1 v_1 + · · · + ξ_n v_n∥ ≤ √(d − ε)) > 0. This is in contrast to the case of n ≡ d (mod 2), wherein the above probability can be zero. The final two chapters concern percolation on finite graphs. Percolation is a topic of central importance to probability theory, and we consider two different problems in this area. In Chapter 6, we consider the bunkbed conjecture, which has featured in the folklore of probability theory since at least 1985, and concerns bond percolation on the product graph G□K2. We have two copies G0 and G1 of G, and if x(0) and x(1) are the copies of a vertex x ∈ V (G) in G0 and G1 respectively, then edge x(0)x(1) is present. The conjecture states that, for vertices u, v ∈ V (G), percolation from u(0) to v(0) is at least as likely as percolation from u(0) to v(1). In this chapter we consider three natural generalisations of the bunkbed conjecture; to site percolation, to hypergraphs, and to directed graphs. Our main aim is to show that all these generalisations are false, and to this end we construct a sequence of counterexamples to these statements. However, we also consider under what extra conditions these generalisations might hold, and give some classes of graph for which the bunkbed conjecture for site percolation does hold. In Chapter 7, we work with percolation on vertex expander graphs. Given a graph G, the percolated graph Gp is formed by retaining each edge independently with probability p. Collares, Diskin, Erde, and Krivelevich initiated the study of large structures in percolated single-scale vertex-expander graphs, wherein every set of exactly k vertices of G has at least dk neighbours before percolation. We extend their result to a conjectured stronger form, proving that if p = (1 + ε)/d and G is a graph on at least k vertices which expands as above, then Gp contains a cycle of length Ω_ε(kd) with probability at least 1 − exp(−Ω_ε(k/d)) as k → ∞.

Name dc:type.qualificationname

Doctor of Philosophy (PhD)

Level dc:type.qualificationlevel

Doctoral

Grantor dc:publisher.institution

University of Cambridge

Year dc:date.issued

2025

Author dc:creator

• Hollom, Lawrence

Advisor dc:contributor.advisor

• Bollobás, Béla

• combinatorics
• probability
• graph theory
• posets

Licence

• https://www.repository.cam.ac.uk/bitstreams/bad6a59b-4bdd-478c-8260-d72f087d8901/download
• https://creativecommons.org/licenses/by/4.0/

Language dc:language

eng

DOI dc:identifier.doi

https://doi.org/10.17863/CAM.126682

OAI identifier oai:identifier

oai:www.repository.cam.ac.uk:1810/397587