How does the answer change if in addition you are told that

Question

1. Given a graph G and a proper vertex r-colouring c : V(G) → [r], we can draw an auxiliary directed graph A_c on vertex set [r] by putting, for each i ≠ j, an arc ij^→ if there is a vertex in c^-1(i) which has no neighbours in c^-1(j) (in other words, if there is a vertex with colour i which we could recolour to j and still have a proper colouring).

An equitable r-colouring of G is a proper vertex r-colouring c : V(G) → [r] such that |c^-1(i)| = |c^-1(j)| ± 1 for each i, j ∈ [r] (in other words, any two colour classes differ in size by at most one).

Suppose from now on that ?(G) ≤ k, for some integer k ≥ 1, and that c is a proper vertex r-colouring of G such that 1 ≤ |c^-1(1)| ≤ ..... ≤ |c^-1(r)|.

(a) What is the minimum number of arcs in A_c leaving each i? (Your answer should not depend on G or i, but only on r and k, and you must both give an example (G, c, i) showing that you can have so few arcs leaving i, and also a proof that for any G, c and i you cannot have fewer)

(b) What is the minimum number of arcs entering 1? How does the answer change if in addition you are told that n1^→ is not in A_c, and |c^-1(n)| > |c^-1(1)|? In both cases, give both a lower bound on the minimum number and also an example showing it is best possible.

(c) Suppose that r ≥ 2k. Prove that there is a directed path in Ac from a largest to a smallest colour class. Deduce that G has an equitable r-colouring.

(d) Give a polynomial-time algorithm which, on input a graph G with maximum degree k and any r ≥ 2k, returns an equitable r-colouring. Prove your algorithm is correct and has polynomial running time.

(e) (Bonus Points) Prove that if k ≥ 2 then G also has an equitable (2k - 1)-colouring.

The distance square G(2) of G is the graph on V(G) with xy ∈ E.G⁽²⁾. if either xy ∈ E(G) or x ≠ y and xz and yz are in E(G) for some z ∈ V(G) (In other words, xy is in E.G⁽²⁾. if x and y are at distance one or two from each other in G).

(f) If ?(G) ≤ k, how large can ?.G⁽²⁾. be? Give an upper bound and an example which shows it is best possible. If c is a proper vertex r-colouring of G(2), then what structure does c reveal in G? (In other words, what can we say about the edges of G within one, or between two, colour classes of c?)

Given two graphs G and H, we say φ is an embedding of G into H if φ : V(G) → V(H) is injective (so φ(x) ≠ φ(y) whenever x ≠ y), and for all edges xy of G, the pair φ(x)φ(y) is an edge of H. (Note that this is not an ‘if and only if' condition, so if xy is not an edge of G then φ(x)φ(y) may or may not be an edge of H). If there exists an embedding of G into H, we say H contains G.

Suppose that G has 2k²n vertices (we assume V(G) is disjoint from [2k²n]), and c is an equitable (2k²)-colouring of G⁽²⁾. Consider the following algorithm, which for input (G, c, p), where p ∈ [0, 1] may depend on n, returns a graph H on 2k²n vertices and either an embedding φ of G into H or ‘Fail'.

Algorithm 1: Embed(G, c, p)

Let V(H) = [2k²n] ;

Let φ1 : c-1(1) → V(H) be an arbitrary injective map with image {1, . . . , n} ;

For each unordered pair x, y in {1, . . . , n}, independently, add xy to H with probability p ;

foreach i = 2, . . . , 2k² do
              For each unordered pair x, y with x ∈ [in] and y ∈ {(i - 1)n + 1, . . . , in},
              independently, add xy to H with probability p ;
               if φ_i-1 ≠ ‘Fail' then
                  Let V(Fi ) = c^-1(i) ∪ {(i - 1)n + 1, . . . , in} ;
                  foreach u ∈ c-1(i) and x ∈ {(i - 1)n + 1, . . . , in} do
                         If φi-1(v)x is an edge of H for each neighbour v of u with c(v) < i, add ux
                         to Fi ;
                  end
if Fi has a perfect matching then

      Let M be a perfect matching in Fi ;
      Define φi : c-1({1, . . . , i}) → V(H) by φi (u) = φi 1(u) if c(u) < i and
      φi (u) = x if c(u) = i and ux ∈ M ;
end else
     Let φi = ‘Fail' ;
end
end else
Let φi = ‘Fail' ;
end
end
Let φ = φr ;
return H, φ ;

(g) Explain (briefly) why if Embed(G, c, p) does not return ‘Fail', then the map φ it returns is an embedding of G into H.

(h) Explain why the graph H returned by Embed(G, c, p) is distributed according to Gn,p. (Hint: for each fixed 2k2 n-vertex graph Hr , what is the probability that the returned H is equal to Hr ?)

(i) For each i = 2, . . . , r, if φ_i-1 ≠ ‘Fail', the graph F_i constructed in Embed(G   , c, p) is a bipartite graph with n vertices in each part. If φ_i-1 is given (formally: conditioning on φ_i-1), what is the probability that ux ∈ F for some u ∈ c^-1 (i) and x ∈ {(i - 1)n + 1, . . . , n}? (Hint: your answer should depend on u but not x.) Explain why the edges of Fi are independent.

(j) Find some (not necessarily optimal!) n₀ and C such that if n ≥ n₀ and p ≥ C. (logn/n)1/k, then this algorithm succeeds with probability at least 0.99.

(k) For each k ≥ 1, find constants C' and n'₀ , and modify Embed(G, c, p), to give an algorithm which runs in polynomial time and does the following. For input graphs G and H, both on n ≥ n_r vertices, with ?(G) ≤ k, your algorithm should try to construct an embedding of G into H.

It is permitted to fail, but your algorithm must succeed with probability at least 0.99 when H is drawn from the distribution Gn,p if p ≥ Cr(logn/n)1/k. Prove that your algorithm has these properties.

(l) Suppose that C' and n₀' are as above for k = 2. Suppose n ≥ n_r , and that G = C_n and H is drawn from Gn,p, with p ≥ C'(logn/n)^1/2. Show that it is possible (i.e., that there is some non-zero probability) that H does not contain G.

(m) Suppose that C' and n₀^' are as above for k = 2. Suppose n ≥ n'₀ , and that G = Cn and H is drawn from Gn,p, with p ≥ Cr (log n/n)^1/2. Suppose your algorithm fails to construct an embedding of G into H. Can we conclude that H does not contain G?