Section A

1. Let X = {1, 2, 3, 4, 5}. Carefully justifying your answers:

(a)  Give an example of a chain of maximum size in 伫(X).

(b)  Give an example of an antichain of maximum size in 伫(X).

(c) What is the maximum size of a family in 伫(X) that is both a chain and an antichain?

(d)  Give a partition of 伫(X) into symmetric chains.

2.   (a)  State Ramsey’s theorem.

(b)  Given that R(3, 4) = 9 prove directly (without using Ramsey’s theorem) that R(3, 5) ≤ 14.

(c) For t > 2 define R4 (t) to be the smallest integer n such that any edge colouring of Kn with 4 colours contains a monochromatic copy of Kt . Prove that for t > 6 we have R4 (t) > 2t .

3.   (a)  Give an example of a complete bipartite graph of order 6 containing a Hamilton cycle. Justify your answer.

(b)  Give an example of a complete bipartite graph of order 6 that does not contain a Hamilton cycle. Justify your answer.

(c) Let n > 2 and define Gn  to be the graph with vertex set {一1, +1}n  and edges given by

E(Gn ) = {uv | u, v ∈ {一1, +1}n  differ in exactly one coordinate}.

(i) For each n > 2 compute χ(Gn ). Justify your answer.

(ii) For which n > 2 does Gn  contain an Euler circuit? Justify your answer.   (iii) For which n > 2 does Gn  contains a Hamilton cycle? Justify your answer.

Figure 1: The graphs H1  and H2

5.   (a) How many edges does the Tur´an graph T4 (9) contain?

(b) For which values of n > r > 2 does T4 (9) contain a copy of Tr (n)? Justify your answer.

(c)  Calculate, with justification, the Tur´an density of each of the following graphs: K3 , K3,3 , T4 (2020).

(d) Let H be a graph with at least one edge and Tur´an density π(H) = α.  Let H*  be formed from H by adding two new vertices a, b and adding new edges {ab} U {va, vb | v ∈ V (H)}.  What is the Tur´an density of H* ?  Justify your answer.