| Phase transitions in real-world situations are an established part of the scientific scenery; they occur because the world is discrete, rather than continuous. Combinatorics is the study of discrete systems, and in this dissertation we shall investigate phase transitions in various combinatorial problems.; In the first part of the dissertation, we study properties of ordered graphs and properties of oriented graphs. A collection of ordered or oriented graphs is called a hereditary property if it is closed under renaming vertices, and taking induced sub structures. The speed of a property is the function n | Pn |, where Pn denotes the collection of distinct structures with exactly n vertices.; We conjecture that there is a 'jump' from exponential speed (≤ cn for some constant c) to factorial speed (≥ ncn for some constant c) for hereditary properties of ordered graphs, and prove various special cases of our conjecture. Each of our results generalize a well-known conjecture of Stanley and Wilf, which was recently proved by the combined results of Klazar, and of Marcus and Tardos. We also determine the possible speeds of a hereditary property of ordered graphs below 2n -1, and prove a jump from polynomial to exponential speed for hereditary properties of unlabelled tournaments. Our results on ordered graphs generalize a theorem of Kaiser and Klazar, who proved that the same jumps hold for hereditary properties of permutations.; In the second part of the dissertation we shall investigate the following question of Bollobas: in bootstrap percolation on the grid [ n]2, how large can a minimal percolating set be? Bootstrap percolation is a deterministic process on a graph G, in which a subset A of the vertices are initially infected, and a vertex becomes infected if at least two of its neighbours are already infected. The set A is said to percolate if eventually all of the vertices are infected. A percolating set is said to be minimal if none of its proper subsets percolate. We show that the largest minimal percolating set in the graph [n]2 has order (1 + o (1))cn2, and that c ∈ [4/33,1/6]. |
