MPCS 50103 — Problem Set 8

Instructions

This problem set is due on Wednesday March 4, 2020 at 17:00. Solutions to Problems should be submitted on Gradescope and will be graded. Solutions to Exercises will not be graded and you should not submit them, although we will be happy to discuss them with you.

Problems

    1. Prove that $V(X) = 0$ if and only if $X$ is constant.
    2. Recall Problem 4 from the previous problem set. Use Chebyshev's inequality to give an upper bound on the probability that the number of $G$s and $C$s in a DNA string of length 10000 generated randomly according to those probabilities deviates from the expected number of $G$s and $C$s by more than 100. You may use results from the solution for Problem 4.
  2. Consider the following graphs $F, G, H$, in order from left to right. For each pair of graphs $(F,G)$, $(G,H)$, and $(F,H)$, determine with justification which pairs of graphs are isomorphic and which pairs are not.
  3. Let $G$ be a $k$-regular bipartite graph.
    1. Prove that if $(V_1,V_2)$ is a bipartition of $G$, then $|V_1| = |V_2|$.
    2. Show that $G$ has a complete matching.
  4. Let $G = (V,E)$ be a graph such that all vertices have degree $\leq d$. Show that $G$ is $(d+1)$-colourable.

Exercises

Expectation and Variance

  1. Prove that if $X:\Omega \to \mathbb R$ is constant (i.e. for all $\omega \in \Omega$, $X(\omega) = c$ for some $c \in \mathbb R$), then $E(X) = c$.
  2. Prove that if $X$ and $Y$ are independent random variables, then $$E(X \cdot Y) = E(X) \cdot E(Y).$$
  3. Prove that $$\min_{\omega \in \Omega} X(\omega) \leq E(X) \leq \max_{\omega \in \Omega} X(\omega).$$
    1. Prove that if $c$ is a constant, then $V(X) = V(X+c)$.
    2. Prove that if $c$ is a constant, then $V(cX) = cV(X)$.
  5. Rosen 7.4 Exercises 19, 25, 27, 35, 39, 45

Graph theory

  1. Show that for any graph $G = (V,E)$, $|E| \leq \binom{|V|}{2}$.
    1. For any graph $G = (V,E)$, with $|V| = n$, show that $G$ is a spanning subgraph of $K_n$.
    2. Consider $K_n = (V_n,E_n)$. Show that for any subset $V_m \subseteq V_n$ with $|V_m| = m$, the subgraph induced by $V_m$ is (isomorphic to) $K_m$.
  3. Rosen 10.2 Exercises 5, 55, 59
  4. Rosen 10.3 Exercises 9, 29, 45, 49