Posted: September 13th, 2017

Discrete Math

Paper, Order, or Assignment Requirements

 

 
I have a coursework in Discrete Math that contains 14 questions. I need logical answers for each question, that explain the solution to each question properly. The topics include matching, graph colouring, embedding, complexity of graph theoretic algorithms, probabilistic methods.

 

These are some corrections and clarifications to questions in the file Coursework.pdf:

• First, on line 2 of Q1 the words `for each i neq j’ have been added – so the directed graph A_c does NOT contain loops.
• Second, in 1(c) the `rge 2k’ condition has been moved to the front so it’s clear it applies to both parts of the question.
• In (f), the ‘what can we say about…’ bit, the expected answer is a description of how the edges look – in particular, if you can say that there are no edges of some particular form, then this is a good description. Your answer to this part is supposed to be useful for the later parts: so the criterion for getting the marks here is that you can use it to answer the later parts.
• In (a) through (e), there is an assumption that the maximum degree of G is at most k (written before (a)). The answer to these parts wouldn’t change if we said that the maximum degree of G is exactly k. The idea you should have in mind is that the larger the maximum degree of G is, the harder it is to colour G; so if I can prove that there is an equitable 10-colouring of all graphs with maximum degree exactly 5, then I should certainly be able to prove it for all G with maximum degree at most five (that is, also for graphs with maximum degree 4, 3, 2, 1 or 0).
• In (b), the `n’ should have been `r’ (twice).
• In (c), the ‘largest’ and ‘smallest’ do indeed refer to the sizes of the colour classes. Note that you can easily enough come up with graphs G and r-colourings such that there is no directed path in A_c from a largest to a smallest colour class, but these won’t satisfy the condition rge 2k. Note that if you don’t use some colour from [r] in an r-colouring, then it means there is a colour class of size zero (which is thus a smallest colour class).
• In (h), it should be G_{2k^2n,p} not G_{n,p}.

 

Quick note on the Embed algorithm:

Another way of looking at the edges added in each iteration of the outer ForEach loop, is that the pairs we choose from independently with probability p are all pairs {x,y} where both are at most i.n and at least one is between (i-1)n+1 and i.n .

On the penultimate line phi_r was supposed to be phi_{2k^2}.