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

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