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.