Abstract: We answer a question of Sós by showing that, if a graph G of order n and density p has no complete minor larger than would be found in a random graph G(n, p), then G is quasi-random, provided either p > 0.45631... or κ(G) ≥ n(log log log n)/(log log n), where 0.45631... is an explicit constant.
The results proved can also be used to fill the gaps in an argument of Thomason, describing the extremal graphs having no Kt minor for given t.
Abstract: Erdős and Szekeres showed that
any permutation of length n ≥
k2 + 1 contains a monotone subsequence of
length k + 1. A simple example shows that there
need be no more than 
such
subsequences; we conjecture that this is the minimum number of such
subsequences. We prove this for k = 2, with a
complete characterisation of the extremal permutations. For
k > 2 and n ≥
k(2k − 1), we characterise the permutations containing the
minimum number of monotone subsequences of length k + 1
subject to the additional constraint that all such
subsequences go in the same direction (all ascending or all
descending); we show that there are 
such extremal permutations, where 
is the
kth Catalan number. We conjecture, with some
supporting computational evidence, that permutations with a minimum
number of monotone (k + 1)-subsequences must have all
such subsequences in the same direction if n ≥ k(2k − 1), except for the case
of k = 3 and n = 16.
Abstract: In the first part of this dissertation, the extremal theory of graph minors is developed as follows. The results of Bollobás, Catlin and Erdős showing how large a complete minor is found in a random graph are extended to showing how large a complete bipartite Ks,t minor is found for given t, even up to t = n − log n. The Hadwiger number of random graphs in a model where different parts of the graph have different edge probabilities is determined almost surely. For a class of dense graphs generalising that of complete bipartite graphs, ‘blown-up’ graphs, the extremal problem in terms of average degree is solved asymptotically, generalising results of Thomason, the extremal graphs being random graphs, and it is shown how a restricted class of blown-up graphs are ‘critical’ for this problem. For K2,t minors, the extremal problem is solved exactly (rather than asymptotically) with the exact best possible number of edges to force such a minor, the methods being substantially different from those for denser minors. For complete minors, it is shown that the extremal graphs are quasi-random in the sense of Chung, Graham and Wilson, or essentially disjoint unions of quasi-random graphs, answering a question of Sós. The extremal problem in terms of connectivity rather than average degree is also considered, with results that are significantly stronger than those in terms of average degree in the cases where they apply.
In the second part of this dissertation, extremal problems relating to directed graphs are considered. The minimum number of monotone subsequences of length k + 1 in a permutation of length n is considered; the extremal permutations are determined exactly for k = 2, and for k > 2 and n ≥ k(2k − 1) subject to an additional constraint, the number of extremal permutations being related to the Catalan numbers.
Abstract: We consider the question of what average degree forces a graph to have a Ks,t minor, for s fixed and t sufficiently large. In the case of s = 2, we show that if t is sufficiently large and G is a graph with more than ((t + 1) / 2)(|G| − 1) edges then G has a K2,t minor. This result is best possible for |G| ≡ 1 (mod t).
Abstract: We investigate the maximum number of edges that a graph G can have if it does not contain a given graph H as a minor (subcontraction). Let
c(H) = inf { c : e(G) ≥ c|G| implies G ≻ H }.
We define a parameter γ(H) of the graph H and show that, if H has t vertices, then
where α = 0.319... is an explicit constant and o(1) denotes a term tending to zero as t → ∞. The extremal graphs are unions of pseudo-random graphs.
If H has t1+τ edges then
,
equality holding for almost all H and for all
regular H. We show how
γ(H) might be evaluated for other
graphs H also, such as complete multi-partite
graphs.
Abstract: A longstanding open problem asks for an aperiodic monotile, also known as an “einstein”: a shape that admits tilings of the plane, but never periodic tilings. We answer this problem for topological disk tiles by exhibiting a continuum of combinatorially equivalent aperiodic polygons. We first show that a representative example, the “hat” polykite, can form clusters called “metatiles”, for which substitution rules can be defined. Because the metatiles admit tilings of the plane, so too does the hat. We then prove that generic members of our continuum of polygons are aperiodic, through a new kind of geometric incommensurability argument. Separately, we give a combinatorial, computer-assisted proof that the hat must form hierarchical—and hence aperiodic—tilings.
Abstract: The recently discovered “hat” aperiodic monotile mixes unreflected and reflected tiles in every tiling it admits, leaving open the question of whether a single shape can tile aperiodically using translations and rotations alone. We show that a close relative of the hat—the equilateral member of the continuum to which it belongs—is a weakly chiral aperiodic monotile: it admits only non-periodic tilings if we forbid reflections by fiat. Furthermore, by modifying this polygon’s edges we obtain a family of shapes called Spectres that are strictly chiral aperiodic monotiles: they admit only chiral non-periodic tilings based on a hierarchical substitution system.