1.

(a) Describe (up to isomorphism) all bipartite graphs with 6 vertices and 8 edges. For each such graph describe a Hamilton cycle or explain why it does not contain one.

(b) State Dirac’s theorem on the existence of Hamilton cycles.

(c) For which integers 2 < r < n does the Tur´an graph Tr (n) contain a Hamil- ton cycle?

(d) Let G be a graph of order n ≥ 3 containing a path of length n−1: v1 v2 ··· vn . Prove that if d(v1 )+ d(vn ) ≥ n then G contains a Hamilton cycle. (25 marks)

(a) Up to isomorphism, the only bipartite graphs of order 6 and size 8 are K2 ,4 and K3 ,3  with an edge removed. (Any other vertex class sizes result in too few edges.)

Since any Hamilton cycle in a bipartite graph must alternate between vertex classes K2 ,4  does not contain a Hamilton cycle. However K3 ,3  with an edge removed does contain a Hamilton cycle. Let V (K3 ,3 ) = {1, 2, 3} [ {4, 5, 6} and 26 be the deleted edge then it contains the Hamilton cycle: 142536.

(b) If G is a graph of order n ≥ 3 and 6(G) ≥ n/2 then G contains a Hamilton cycle.

(c) For r = 2 we have T2 (n) = K「n/2c , dn/2」 which is Hamiltonian i↵ n is even and greater than 2. For r ≥ 3 we know that every vertex is adjacent to all vertices not in the same class and hence for 3 < r < n

6(Tr (n)) = n −dn/re ≥ n/2.

Hence Dirac’s theorem implies that Tr (n) contains a Hamilton cycle for all 3 < r < n.

(d) We can adapt the proof of Ore’s theorem as follows.

If v1 vn  2 E(G) then we clearly have a Hamilton cycle, so suppose this is not the case. Let A = Γ(vn )/{vn−1) and B = {vi  | vi+1  2 Γ(v1 )}/{v1 }. If we show that A \ B ; then we are done since if vi   2 A \ B then v1 v2 ··· vi vn vn−1 ··· vi+1  is a Hamilton cycle.

Now A,B ✓ {v2 , . . . ,vn−2} and |A|+|B| = d(vn )− 1+d(v1 ) − 1 ≥ n − 2 and so by the pigeonhole principle A \ B ; and the proof is complete.

2.

(a) Describe the Tur´an graph T3 (8). For which 2 < r < n does T3 (8) contain a copy of Tr (n)?

(b) For a graph F and an integer n ≥ 1, let ex3 (n,F) be the maximum number of copies of K3 in an F-free graph of order n. Prove that the following limit

exists:

ex3 (n,F)

(c) Prove that ⇡3 (K4 ) ≥ 2/9. (25 marks)

(a) T3 (8) is the complete 3-partite graph with vertex classes of order 3,3,2. It cannot contain any Tr (n) with r > 3 or n > 8. By deleting vertices it is easy to see that it contains T3 (n) for 3 < n < 8. For r = 2 it clearly contains T2 (n) for n = 2, 3, 4, 5, 6 (simply remove the smaller vertex class and then delete vertices). It also contains T2 (7): delete a vertex from the smallest class and remove edges from the remaining vertex in that class to one of the larger classes.. However it does not contain T2 (8) since any 2-colouring of T3 (8) must result in a pair of vertices from the same class in T3 (8) being given di↵erent colours and so the corresponding edge is missing.

(b) We adapt the proof of existence of the standard Tur´an density as follows. Let G be an F-free graph of order n with ex3 (n,F) copies of K3 . If

v 2 V(G) then G/{v} contains at most ex3 (n − 1,F) copies of K3 . Let t(H) denote the number of copies of K3  in a graph H. By double counting and using the fact that every K3  contains 3 vertices we have

(n − 3)t(G) =  X   t(G/{v}) < nex3 (n − 1,F)

v 2V (G)

Thus (n − 3)ex3 (n,F) < nex3 (n − 1,F) and hence

ex3 (n,F) ex3 (n − 1,F)

Thus the sequence is descreasing and bounded below (by zero) so converges.  (c) This follows by observing that T3 (n)is K4-free and contains「c「c「c

copies of K3 . Hence

t3 (n) 「n/3c「(n + 1)/3c「(n + 2)/3c 6 2

3.

(a) Give an example of an intersecting chain of maximum size in P([5]).   (b) Give an example of an intersecting antichain of maximum size in P([5]).

(c) State the LYM-inequality.

(d) Let n ≥ 1 and suppose that F ✓ P([2n+1]) does not contain three distinct sets A,B,C such that A ⇢ B ⇢ C. Prove that |F| < 2(2n(n+1)). (25 marks)

(a) 1, 12, 123, 1234, 12345 is a maximum sized intersecting chain (any larger chain must also contain ; since it can contain at most one set of each size, but this would no longer be intersecting).

(b) The largest antichain has size at most (2(5)) (by Sperner’s Theorem). The unique intersecting antichain of this size is ([  ]3(5) ).

(c) If A is an antichain in P([n]) then

XA2A < 1.

(d) We can adapt the proof of LYM to this case. Let F satisy the conditions given in the question and N = 2n + 1. Construct a bipartite graph G with vertex classes F and SN  and an edge from F to ⇡ i↵ the first |F| elements of ⇡ are F. For each F we have dG (F) = |F|!(N − |F|)! (since the first |F| elements of any neighbour are F in some order and then we are free to choose the order of the elements in Fc . We claim no ⇡ 2 SN  has degree greater than 2. If not, say ⇡ is adjacent to distinct sets A,B,C 2 F then these sets are all intial elements from ⇡, thus all have di↵erent sizes, wlog |A| < |B| < |C| and so we must have A ⇢ B ⇢ C, a contradiction. Hence dG (⇡) < 2. Hence by double counting edges in G we have

X 1 < 2.

Finally we note that since N = 2n + 1 then for any F 2 F we have (|F(N)|) < (2n(n+1)) and the desired result follows.

4. For an integer n ≥ 3 and p 2 [0, 1], let F be a random graph from G(n,p). (a) Calculate the expected number of edges in F .

(b) Calculate the expected number of triangles in F .

(c) Calculate the expected number of vertices in F of degree 0.

(d) Set p = 2/n and let t(F) be the expected number of pairs of distinct vertices x,y 2 V (F) such that the length of the shortest path from x to y is at least

3. Explain carefully why t(F) is given by the following expression

(n − 1)(n − 2)n−1(n + 2)n−2

(25 marks)

(a) Each possible edge is present with probability p so by linearity of expecta- tion this is p (2(n)).

(b) For each of of the (3(n)) possible triangles T let XT be the associated indicator variable. For a fixed triangle the probability it is present is p3  (since it con- tains three edges and these are each present independently with probability p). So by linearity of expectation this is (3(n))p3 .

(c) For v 2 V (F), d(v) = 0 i↵ each of the n−1 possible edges vw , w 2 V (F)/{v} is absent. These are all absent independently with probability (1−p), so any single vertex has degree 0 with probability (1 − p)n−1  and so the expected number of such vertices (by linearity of expectation) is n(1 − p)n−1 .

(d) For a pair of vertices x,y the shortest path from x to y has length at least

3 i↵ xy is not an edge and not both of xi and yi are edges for any i x,y . The probability that not both of xi and yi are edges for any fixed i x,y is 1 −p2  and these edges are distinct for the n− 2 di↵erent choices of i x,y . Since these edges are distinct the associated events are independent and hence the probability that there is no i x,y such that xi and yi are both edges is (1 − p2 )n−2 . Finally the probabilty that xy is not an edge is (1 − p) and this edge is di↵erent from those considered previously so is absent independently of the other edges. Hence the probability that the shortest path from x to y has length at least 3 is (1 − p)(1 − p2 )n−2 .

Linearity of expectation then tells us that the expected number of such pairs is (2(n))(1 − p)(1 − p2 )n−2 . Finally substituting p = 2/n we obtain the desired expression.