Extremal combinatorics, graph limits and computational complexity

Thesis

This thesis is primarily focused on problems in extremal combinatorics, although we will also consider some questions of analytic and algorithmic nature.

The d-dimensional hypercube is the graph with vertex set {0,1}^d where two vertices are adjacent if they differ in exactly one coordinate. In Chapter 2 we obtain an upper bound on the 'saturation number' of Q_m in Q_d. Specifically, we show that for m ≥ 2 f...

Expand abstract

Authors: Noel, J

• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: Weak Saturation; Counting Antichains; Saturation Problems; Antichains in Random Posets; Supersaturation in Posets; Bootstrap Percolation; Graph Limits; Sperner Theory; Combinatorial Reconfiguration; Circular Colouring; Weak Regularity
• Subjects: Graph coloring; Mathematics; Combinatorial probabilities; Computational complexity; Graph theory; Combinatorial analysis; Extremal problems (Mathematics); Percolation (Statistical physics)--Mathematical models