Extremal combinatorics is concerned with how large or small a combinatorial structure can be if we insist it satis es certain properties. In this thesis we investigate four different problems in extremal combinatorics, each with its own unique flavour. We begin by examining a graph saturation problem. We say a graph G is H-saturated if G contains no copy of H as a subgraph, but the addition of any new edge to G creates a copy of H. We look at how few edges a Kp- saturated graph can have when we place certain conditions on its minimum degree. We look at a problem in Ramsey Theory. The k-colour Ramsey number Rk(H) of a graph H is de ned as the least integer n such that every k- colouring of Kn contains a monochromatic copy of H. For an integer r > 3 let Cr denote the cycle on r vertices. By studying a problem related to colourings without short odd cycles, we prove new lower bounds for Rk(Cr) when r is odd. Bootstrap percolation is a process in graphs that can be used to model how infection spreads through a community. We say a set of vertices in a graph percolates if, when this set of vertices start off as infected, the whole graph ends up infected. We study minimal percolating sets, that is, percolating sets with no proper percolating subsets. In particular, we investigate if there is any relation between the smallest and the largest minimal percolating sets in bounded degree graph sequences. A tournament is a complete graph where every edge has been given an orientation. We look at the maximum number of directed k-cycles a tournament can have and investigate when there exist tournaments with many more k-cycles than expected in a random tournament.

Given two set systems $\mathscr{A}$ and $\mathscr{B}$ over an $n$-element set, we say that $(\mathscr{A,B})$ forms a recovering pair if the following conditions hold: \\ $ \forall A, A' \in \mathscr{A}$ and $ \forall B, B' \in \mathscr{B}$, $A \setminus B = A' \setminus B' \Rightarrow A=A'$ \\ $ \forall A, A' \in \mathscr{A}$ and $ \forall B, B' \in \mathscr {B}$, $B \setminus A = B' \setminus A' \Rightarrow B=B'$ \\ In 1989, G\'bor Simonyi conjectured that if $(\mathscr)$ forms a recovering pair, then $|\mathscr||\mathscr|\leq 2^n$. This conjecture is the focus of this thesis. This thesis contains a collection of proofs of special cases that together form a complete proof that the conjecture holds for all values of $n$ up to 8. Many of these special cases also verify the conjecture for certain recovering pairs when $n>8$. We also present a result describing the nature of the set of numbers over which the conjecture in fact holds. Lastly, we present a new problem in graph theory, and discuss a few cases of this problem.

For integers $n \geq k \geq 2$, let $V$ be an $n$-element set, and let $\binom{V}{k}$ denote the family of all $k$-element subsets of $V$. For disjoint subsets $A, B \subseteq V$, we say that $\{A, B\}$ {\it covers} an element $K \in \binom{V}{k}$ if $K \subseteq A \dot\cup B$ and $K \cap A \neq \emptyset \neq K \cap B$. We say that a collection $\cC$ of such pairs {\it covers} $\binom{V}{k}$ if every $K \in \binom{V}{k}$ is covered by at least one $\{A, B\} \in \cC$. When $k=2$, covers $\cC$ of $\binom{V}{2}$ were introduced in~1961 by R\'enyi~\cite{Renyi}, where they were called {\it separating systems} of $V$ (since every pair $u \neq v \in V$ is separated by some $\{A, B\} \in \cC$, in the sense that $u \in A$ and $v \in B$, or vice-versa). Separating systems have since been studied by many authors. For a cover $\cC$ of $\binom{V}{k}$, define the {\it weight} $\omega(\cC)$ of $\cC$ by $\omega(\cC) = \sum_{\{A, B\} \in \cC} (|A|+|B|)$. We define $h(n, k)$ to denote the minimum weight $\omega(\cC)$ among all covers $\cC$ of $\binom{V}{k}$. In~1964, Hansel~\cite{H} determined the bounds $\lceil n \log_2 n \rceil \leq h(n, 2) \leq n\lceil \log_2 n\rceil$, which are sharp precisely when $n = 2^p$ is an integer power of two. In~2007, Bollob\'as and Scott~\cite{BS} extended Hansel's bound to the exact formula $h(n, 2) = np + 2R$, where $n = 2^p + R$ for $p = \lfloor \log_2 n\rfloor$. The primary result of this dissertation extends the results of Hansel and of Bollob\'as and Scott to the following exact formula for $h(n, k)$, for all integers $n \geq k \geq 2$. Let $n = (k-1)q + r$ be given by division with remainder, and let $q = 2^p + R$ satisfy $p = \lfloor \log_2 q \rfloor$. Then h(n, k) = np + 2R(k-1) + \left\lceil\frac{r}{k-1}\right\rceil (r + k - 1). A corresponding result of this dissertation proves that all optimal covers $\cC$ of $\binom{V}{k}$, i.e., those for which $\omega(\cC) = h(n, k)$, share a unique {\it degree-sequence}, as follows. For a vertex $v \in V$, define the {\it $\cC$-degree} $\deg_{\cC}(v)$ of $v$ to be the number of elements $\{A, B\} \in \cC$ for which $v \in A \dot\cup B$. We order these degrees in non-increasing order to form $\bd(\cC)$, and prove that when $\cC$ is optimal, $\bd(\cC)$ is necessarily binary with digits $p$ and $p+1$, where uniquely the larger digits occur precisely on the first $2R(k-1) + \lceil r/(k-1) \rceil (r + k - 1)$ many coordinates. That $\bd(\cC)$ satisfies the above for optimal $\cC$ clearly implies the claimed formula for $h(n,k)$, but in the course of this dissertation, we show these two results are, in fact, equivalent. In this dissertation, we also consider a $d$-partite version of covers $\cC$, written here as {\it $d$-covers} $\cD$. Here, the elements $\{A,B\} \in \cC$ are replaced by $d$-element families $\{A_1, \dots, A_d\} \in \cD$ of pairwise disjoint sets $A_i \subset V$, $1 \leq i \leq d$. We require that every element $K \in \binom{V}{k}$ is covered by some $\{A_1, \dots, A_d\} \in \cD$, in the sense that $K \subseteq A_1 \dot\cup \cdots \dot\cup A_d$ where $K \cap A_i \neq \emptyset$ holds for each $1 \leq i \leq d$. We analogously define $h_d(n,k)$ as the minimum weight $\omega(\cD) = \sum_{D \in \cD} \sum_{A \in D} |A|$ among all $d$-covers $\cD$ of $\binom{V}{k}$. In this dissertation, we prove that for all $2 \leq d \leq k \leq n$, the bound $h_d(n,k) \geq n \log_{d/(d-1)} (n/(k-1))$ always holds, and that this bound is asymptotically sharp whenever $d = d(k) = O (k/\log^2 k)$ and $k = k(n) = O(\sqrt{\log \log n})$.

In this dissertation we consider several extremal and probabilistic problems in bootstrap percolation on various families of graphs, including grids, hypercubes and trees. Bootstrap percolation is one of the simplest cellular automata. The most widely studied model is the so-called r-neighbour bootstrap percolation, in which we consider the spread of infection on a graph G according to the following deterministic rule: infected vertices of G remain infected forever and in successive rounds healthy vertices with at least r already infected neighbours become infected. Percolation is said to occur if eventually every vertex is infected. In Chapter 1 we consider a particular extremal problem in 2-neighbour bootstrap percolation on the n \times n square grid. We show that the maximum time an infection process started from an initially infected set of size n can take to infect the entire vertex set is equal to the integer nearest to (5n^2-2n)/8. In Chapter 2 we relax the condition on the size of the initially infected sets and show that the maximum time for sets of arbitrary size is 13n^2/18+O(n). In Chapter 3 we consider a similar problem, namely the maximum percolation time for 2-neighbour bootstrap percolation on the hypercube. We give an exact answer to this question showing that this time is \lfloor n^2/3 \rfloor. In Chapter 4 we consider the following probabilistic problem in bootstrap percolation: let T be an infinite tree with branching number \br(T) = b. Initially, infect every vertex of T independently with probability p > 0. Given r, define the critical probability, p_c(T,r), to be the value of p at which percolation becomes likely to occur. Answering a problem posed by Balogh, Peres and Pete, we show that if b \geq r then the value of b itself does not yield any non-trivial lower bound on p_c(T,r). In other words, for any \varepsilon > 0 there exists a tree T with branching number \br(T) = b and critical probability p_c(T,r) < \varepsilon. However, in Chapter 5 we prove that this is false if we limit ourselves to the well-studied family of Galton--Watson trees. We show that for every r \geq 2 there exists a constant c_r>0 such that if T is a Galton--Watson tree with branching number \br(T) = b \geq r then \[ p_c(T,r) > \frac{c_r}{b} e^{-\frac{b}{r-1}}. \] We also show that this bound is sharp up to a factor of O(b) by describing an explicit family of Galton--Watson trees with critical probability bounded from above by C_r e^{-\frac{b}{r-1}} for some constant C_r>0.

Szemere´di’s Regularity Lemma [32, 33] is an important tool in combinatorics, with numerous appli- cations in combinatorial number theory, discrete geometry, extremal graph theory, and theoretical computer science. The Regularity Lemma hinges on the following concepts. Let G = (V, E) be a graph and let ∅ /= X, Y ⊂ V be a pair of disjoint vertex subsets. We define the density of the pair (X, Y ) by dG(X, Y ) = |E[X, Y ]|/(|X||Y |) where E[X, Y ] denotes the set of edges {x, y} ∈ E with x ∈ X and y ∈ Y . We say the pair (X, Y ) is ε-regular if all subsets XI ⊆ X and Y I ⊆ Y satisfying |XI| > ε|X| and |Y I| > ε|Y | also satisfy |dG(XI, Y I) − dG(X, Y )| < ε. The Regularity Lemma states that, for all ε > 0, all large n-vertex graphs G = (V, E) admit a partition V = V1 ∪ · · · ∪ Vt, where t = t(ε) depends on ε but not on n, so that all but εt2 pairs (Vi, Vj), 1 ≤ i < j ≤ t, are ε-regular. While Szemere´di’s original proof demonstrates the existence of such a partition, it gave no method for (efficiently) constructing such partitions. Alon, Duke, Lefmann, Ro¨dl, and Yuster [1, 2] showed that such partitions can be constructed in time O(M (n)), where M (n) is the time needed to multiply two n × n {0, 1}-matrices over the integers. Kohayakawa, Ro¨dl, and Thoma [17, 18] improved this time to O(n2). The Regularity Lemma can be extended to k-uniform hypergraphs, as can algorithmic for- mulations thereof. The most straightforward of these extends the concepts above to k-uniform hypergraphs H = (V, E) in a nearly verbatim way. Let ∅ /= X1, . . . , Xk ⊂ V be pairwise disjoint subsets, and let E[X1, . . . , Xk] denote the set of k-tuples {x1, . . . , xk} ∈ E satisfying x1 ∈ X1, . . . , xk ∈ Xk. We define the density of (X1, . . . , Xk) as dH(X1, . . . , Xk) = |E[X1, . . . , Xk]| / |X1| · · · |Xk|. We say that (X1, . . . , Xk) is ε-regular if all subsets XiI ⊆ Xi, 1 ≤ i ≤ k, satisfying |XiI| > ε|Xi| also satisfy |dH (X1I , . . . , XkI ) − dH (X1, . . . , Xk)| < ε. With these concepts, Szemeredi’s original proof can be applied to give that, for all integers k ≥ 2 and for all ε > 0, all n-vertex k-uniform hypergraphs H = (V, E) admit a partition V = V1 ∪· · ∪ Vt, where t = t(k, ε) is independent of n, so that all but εtk many k-tuples (Vi1 , . . . , Vik) are ε-regular, where 1 ≤ i1 < · · · < ik ≤ t. Czygrinow and Ro¨dl [4] gave an algorithm for such a regularity lemma, which in the context above, runs in time O(n2k−1 log5 n). In this dissertation, we consider regularity lemmas for 3-uniform hypergraphs. In this setting, our first main result improves the algorithm of Czygrinow and Ro¨dl to run in time O(n3), which is optimal in its order of magnitude. Our second main result shows that this algorithm gives a stronger notion of regularity than what is described above, where this stronger notion is described in the course of this dissertation. Finally, we discuss some ongoing applications of our constructive regularity lemmas to some classical algorithmic hypergraph problems.

This thesis lies in the field of probabilistic and extremal combinatorics: we study discrete structures, with a focus on thresholds, when the behaviour of a structure changes from one mode into another. From a probabilistic perspective, we consider models for a random structure depending on some parameter. The questions we study are then: When (i.e. for what values of the parameter) does the probability of a given property go from being almost 0 to being almost 1? How do the models behave as this transition occurs? From an extremal perspective, we study classes of structures depending on some parameter. We are then interested in the following questions: When (for what value of the parameter) does a particular property become unavoidable? What do the extremal structures look like? The topics covered in this thesis are random geometric graphs, dependent percolation, extremal hypergraph theory and combinatorics in the hypercube.

We give an overview of recent progress in the research of hypergraph jumps -- a problem from extremal combinatorics. The number $\alpha \in [0, 1)$ is a jump for $r$ if for any $\epsilon > 0$ and any integer $m \ge r$ any $r$-graph with $N > N(\epsilon, m)$ vertices and at least $(\alpha + \epsilon) {N \choose r}$ edges contains a subgraph with $m$ vertices and at least $(\alpha + c) {m \choose r}$ edges, where $c := c(\alpha)$ does depend only on $\alpha$. Baber and Talbot \cite{Baber} recently gave first examples of jumps for $r = 3$ in the interval $[2/9, 1)$. Their result uses the framework of flag algebras \cite{Raz07} and involves solving a semidefinite optimization problem. A software implementation of their method is a part of this work.

Nesta tese estudamos dois problemas em digrafos: um problema de empacotamento e um problema de contagem. Estudamos o problema de empacotamento máximo de arborescências no digrafo aleatório D(n,p), onde cada possvel arco é inserido aleatoriamente ao acaso com probabilidade p = p(n). Denote por (D(n,p)) o maior inteiro possvel 0 tal que, para todo 0 l , temos ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}| Provamos que a quantidade máxima de arborescências em D(n,p) é (D(n,p)) assintoticamente quase certamente. Nós também mostramos estimativas justas para (D(n, p)) para todo p [0, 1]. As principais ferramentas que utilizamos são relacionadas a propriedades de expansão do D(n, p), o comportamento do grau de entrada do digrafo aleatório e um resultado clássico de Frank que serve como ligação entre subpartições em digrafos e a quantidade de arborescências. Para o problema de contagem, estudamos a densidade de subtorneios fortemente conexos com 5 vértices em torneios grandes. Determinamos a densidade assintótica máxima para 5 torneios bem como as famlias assintóticas extremais de cada torneios. Como subproduto deste trabalho caracterizamos torneios que são blow-ups recursivos de um circuito orientado com 3 vértices como torneios que probem torneios especficos de tamanho 5. Como principal ferramenta para esse problema utilizados a teoria de álgebra de flags e configurações combinatórias obtidas através do método semidefinido. / In this thesis we study two problems dealing with digraphs: a packing problem and a counting problem. We study the problem of packing the maximum number of arborescences in the random digraph D(n,p), where each possible arc is included uniformly at random with probability p = p(n). Let (D(n,p)) denote the largest integer 0 such that, for all 0 l , we have ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}|. We show that the maximum number of arc-disjoint arborescences in D(n, p) is (D(n, p)) asymptotically almost surely. We also give tight estimates for (D(n, p)) for every p [0, 1]. The main tools that we used were expansion properties of random digraphs, the behavior of in-degree of random digraphs and a classic result by Frank relating subpartitions and number of arborescences. For the counting problem, we study the density of fixed strongly connected subtournaments on 5 vertices in large tournaments. We determine the maximum density asymptotically for five tournaments as well as unique extremal sequences for each tournament. As a byproduct of this study we also characterize tournaments that are recursive blow-ups of a 3-cycle as tournaments that avoid three specific tournaments of size 5. We use the theory of flag algebras as a main tool for this problem and combinatorial settings obtained from semidefinite method.

In this dissertation we solve several combinatorial problems in different areas of mathematics: automata theory, combinatorics of partially ordered sets and extremal combinatorics. Firstly, we focus on some new automata that do not seem to have occurred much in the literature, that of solvability of mazes. For our model, a maze is a countable strongly connected digraph together with a proper colouring of its edges (without two edges leaving a vertex getting the same colour) and two special vertices: the origin and the destination. A pointer or robot starts in the origin of a maze and moves naturally between its vertices, according to a sequence of specific instructions from the set of all colours; if the robot is at a vertex for which there is no out-edge of the colour indicated by the instruction, it remains at that vertex and proceeds to execute the next instruction in the sequence. We call such a finite or infinite sequence of instructions an algorithm. In particular, one of the most interesting and very natural sets of mazes occurs when our maze is the square lattice Z2 as a graph with some of its edges removed. Obviously, we need to require that the origin and the destination vertices are in the same connected component and it is very natural to take the four instructions to be the cardinal directions. In this set-up, we make progress towards a beautiful problem posed by Leader and Spink in 2011 which asks whether there is an algorithm which solves the set of all such mazes. Next, we address a problem regarding symmetric chain decompositions of posets. We ask if there exists a symmetric chain decomposition of a 2 × 2 × ... × 2 × n cuboid (k 2’s) such that no chain has a subchain of the form (a1,...,ak,0) ≺ ... ≺ (a1,...,ak,n−1)? We show this is true precisely when k≥5 and n≥3. Thisquestion arises naturally when considering products of symmetric chain decompositions which induce orthogonal chain decompositions — the existence of the decompositions provided in this chapter unexpectedly resolves the most difficult case of previous work by Spink on almost orthogonal symmetric chain decompositions (2017) which makes progress on a conjecture of Shearer and Kleitman. Moreover, we generalize our methods to other finite graded posets. Finally, we address two different problems in extremal combinatorics related to mathematical physics. Firstly, we study metastable states in the Ising model. We propose a general model for 1-flip spin systems, and initiate the study of extremal properties of their stable states. By translating local stability conditions into Sperner- type conditions, we provide non-trivial upper bounds which are often tight for large classes of such systems. The last topic we consider is a deterministic bootstrap percolation type problem. More specifically, we prove several extremal results about fast 2-neighbour percolation on the two dimensional grid.

In this dissertation, we are interested in studying several parameters of graphs and understanding their extreme values. We begin in Chapter~$2$ with a question on edge colouring. When can a partial proper edge colouring of a graph of maximum degree $\Delta$ be extended to a proper colouring of the entire graph using an `optimal' set of colours? Albertson and Moore conjectured this is always possible provided no two precoloured edges are within distance $2$. The main result of Chapter~$2$ comes close to proving this conjecture. Moreover, in Chapter~$3$, we completely answer the previous question for the class of planar graphs. Next, in Chapter~$4$, we investigate some Ramsey theoretical problems. We determine exactly what minimum degree a graph $G$ must have to guarantee that, for any two-colouring of $E(G)$, we can partition $V(G)$ into two parts where each part induces a connected monochromatic subgraph. This completely resolves a conjecture of Bal and Debiasio. We also prove a `covering' version of this result. Finally, we study another variant of these problems which deals with coverings of a graph by monochromatic components of distinct colours. The following saturation problem proposed by Barrus, Ferrara, Vandenbussche, and Wenger is considered in Chapter~$5$. Given a graph $H$ and a set of colours $\{1,2,\ldots,t\}$ (for some integer $t\geq |E(H)|$), we define $sat_{t}(n, R(H))$ to be the minimum number of $t$-coloured edges in a graph on $n$ vertices which does not contain a rainbow copy of $H$ but the addition of any non-edge in any colour from $\{1,2,\ldots,t\}$ creates such a copy. We prove several results concerning these extremal numbers. In particular, we determine the correct order of $sat_{t}(n, R(H))$, as a function of $n$, for every connected graph $H$ of minimum degree greater than $1$ and for every integer $t\geq e(H)$. In Chapter~$6$, we consider the following question: under what conditions does a Hamiltonian graph on $n$ vertices possess a second cycle of length at least $n-o(n)$? We prove that the `weak' assumption of a minimum degree greater or equal to $3$ guarantees the existence of such a long cycle. We solve two problems related to majority colouring in Chapter~$7$. This topic was recently studied by Kreutzer, Oum, Seymour, van der Zypen and Wood. They raised the problem of determining, for a natural number $k$, the smallest positive integer $m = m(k)$ such that every digraph can be coloured with $m$ colours, where each vertex has the same colour as at most a proportion of $\frac{1}{k}$ of its out-neighbours. Our main theorem states that $m(k) \in \{2k-1, 2k\}$. We study the following problem, raised by Caro and Yuster, in Chapter~$8$. Does every graph $G$ contain a `large' induced subgraph $H$ which has $k$ vertices of degree exactly $\Delta(H)$? We answer in the affirmative an approximate version of this question. Indeed, we prove that, for every $k$, there exists $g(k)$ such that any $n$ vertex graph $G$ with maximum degree $\Delta$ contains an induced subgraph $H$ with at least $n-g(k)\sqrt{\Delta}$ vertices such that $V(H)$ contains at least $k$ vertices of the same degree $d \ge \Delta(H)-g(k)$. This result is sharp up to the order of $g(k)$. %Subsequently, we investigate a concept called $\textit{path-pairability}$. A graph is said to be path-pairable if for any pairing of its vertices there exist a collection of edge-disjoint paths routing the the vertices of each pair. A question we are concerned here asks whether every planar path pairable graph on $n$ vertices must possess a vertex of degree linear in $n$. Indeed, we answer this question in the affirmative. We also sketch a proof resolving an analogous question for graphs embeddable on surfaces of bounded genus. Finally, in Chapter~$9$, we move on to examine $k$-linked tournaments. A tournament $T$ is said to be $k$-linked if for any two disjoint sets of vertices $\{x_1,\ldots ,x_k\}$ and $\{y_1,\dots,y_k\}$ there are directed vertex disjoint paths $P_1,\dots, P_k$ such that $P_i$ joins $x_i$ to $y_i$ for $i = 1,\ldots, k$. We prove that any $4k$ strongly-connected tournament with sufficiently large minimum out-degree is $k$-linked. This result comes close to proving a conjecture of Pokrovskiy.