Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
MATH 2601 - FoMP - Homework 4
Problem 1. Recall that a tournament is an oriented complete graph and a Hamilton path is a directed path consisting of all the vertices in the graph. Compute the expected number of Hamilton paths in a random tournament on 3 players (vertices) in two ways:
i) Compute the expectation by writing it as a sum of 0-1 random variables and using the linearity of expectation, as done in class.
ii) Now compute the expectation as an average over all possible tournaments: First enumerate the 8 possible (labeled) tournaments on 3 vertices. Write the number of Hamilton paths in each of the tournaments. Take the average.
Problem 2. Determine R(k, 2) =? for k ≥ 2. (Recall that you need to argue both the upper bound and the lower bound.)
Problem 3. Show that R(4, 3) ≤ 10. Hint: Given an arbitrary Red-Blue coloring of the edges of K10, consider whether vertex v1 has at least 6 red edges incident to it or not.
Problem 4. (I will illustrate the following with examples for k = 2, 3 in class). Let k ≥ 2. Let Ω be a finite set of elements and let S1, S2, . . . , Sm ⊆ Ω be m subsets, each of cardinality k. We say such a collection of sets admits a proper Red-Blue coloring if there exists an assignment of Red/Blue color to the elements of Ω so that none of the Si is monochromatic. In other words : ∃χ : Ω → {Red, Blue} : ∀i ∈ {1, 2, . . . , m}, ∃x, y ∈ Si , with χ(x) = Red and χ(y) = Blue .
Show that whenever m < 2 n−1 , such a collection always admits a proper Red-Blue coloring.
Hint: Consider a random Red-Blue coloring and estimate the expected number of monochromatic sets.
Additionally, the following problems from Hammack’s book: Ch.7: 6, 8, 18 Ch.10: 2, 10, 24
Note. For Problem 10.24 above, feel free to use the following identities, which are true for all integers k, n, with 1 ≤ k ≤ n: n + 1 k ! = n k ! + n k − 1 ! and Xn k=0 n k ! = 2n .