The notation "MN" refers to the Matoušek--Nešetříl text (second edition). The first edition is also entirely adequate for this class. Note that a new Chapter 2 has been inserted in the second edition so for $i\ge 3$ if you can find something in Chapter $i$ in the second edition, it will appear in Chapter $i-1$ in the first edition.
The notation "LIN" refers to the instructor's Linear Algebra notes, currently in progress.
"DO" problems are strongly recommended to check your understanding of the concepts; do not hand them in.
Problems labeled "HW" must be handed in at the beginning of the next class unless expressly stated otherwise.
BONUS PROBLEMS are not mandatory but the same deadline applies as to ordinary homework.
CHALLENGE PROBLEMS have no point value (but they earn you the instructor's attention) and no deadline (except they expire when discussed in class). Make sure you hand them in on a separate sheet, state your name, the fact that this is a challenge problem solution, and indicate the problem being solved. One further request: if you hand in a solution to a challenge problem, send email to the instructor giving the problem number and a brief indication of the problem (copied from the problem announcement: like "n+1 numbers" or "another limit related to the def of "e"" -- no detailed description needed, this suffices to remind me which problem it was). Such email will create an easy record and help avoid mistakes in bookkeeping.
REWARD PROBLEMS are challenge problems that you should NOT hand in. The solution is its own reward. No deadline. Of course you are welcome to discuss your thoughts with the TA, the instructor, and your peers.
If you hand in material before its due date, make sure you put it on a separate sheet since solutions are graded in batches by their due dates.
13.1 DO: LN 8.1.5, 8.1.6, 8.1.7: study the finite Markov Chain corresponding to the transition matrix $\displaystyle{ T = \left(\matrix{0.7 & 0.3 \\ 0.2 & 0.8 }\right) }.$ (Draw, compute the powers (use a calculator or computer), experience that the powers converge, guess the limit.)
13.2 DO: LN 8.1.8 (prove the convergence observed).
13.3 DO: LN 8.1.9, 8.1.14 (equations for left/right action, left/right eigenvalues, $\lambda = 1$ is a right eigenvalue).
13.4 DO: LN 8.1.13, 8.1.16, 8.1.17, 8.1.18, 8.1.20: (a) stationary distribution does not evolve; (b) if $\lim_{k\to\infty} T^k$ exists then its rows are stationary distributions; (c-d) examples where the matrices $T^k$ do not converge yet a stationary distribution exists [directed cycles] - note that according to a difficult theorem, a stationary distribution always exists; (e) the uniform distribution is stationary if and only if the transition matrix is doubly stochastic.
13.5 DO: LN 8.1.10, 8.1.15: find the eigenvalues and the corresponding right and left eigenvectors for the matrix $T$ of exercise 13.1. In particular, find the stationary distribution of the MC defined by $T$ (appropriately normalized left eigenvector to eigenvalue 1).
13.6 DO: LN 8.1.11 (for a stochatic matrix, $|\lambda|\le 1$ for all (complex) eigenvalues $\lambda$).
13.7 DO: LN 8.1.12, 8.1.22 (left and right eigenvectors to distinct eigenvalues are orthogonal; nonnegative left eigenvector of a stochastic matrix corresponds to eigenvalue 1).
13.8 DO: LN 8.1.21 (every MC has a stationary distribution). Use the version of the Frobenius-Perron Theorem stated before LN 8.1.21. (Hint: Use the preceding exercise.)
13.9 DO: (a) Find a MC which has more than one stationary distribution. Use as few states as possible. (b) Prove: if a MC has more than one stationary distribution then it has infinitely many.
13.10 DO: LN 8.1.24 - 8.1.27 (an irreducible MC has a unique stationary distribution, and all entries in this distribution are positive).
13.11 DO: LN 8.1.28 (in a MC, at least one state has nonzero period; construct a MC with $n$ states, $n-1$ of which have period zero).
13.12 DO: LN 8.1.30 (if transition digraph undirected then all periods are 1 or 2).
13.13 DO: LN 8.1.31 (if an irreducible MC is not aperiodic then the powers of the transition matrix do not converge).
13.14 DO: LN 8.1.32: eigenvalues of the random walk MC on a directed cycle of length $n$ are the complex $n$-th roots of unity. (Note that this "random walk" is quite deterministic.)
13.15 DO: LN 8.1.33: eigenvalues of a MC of period $d$ can be multiplied by $d$-th roots of unity.
13.16 DO: LN 8.1.35, 8.1.36: if $T$ is ergodic and then all rows of the limit $\lim_k T^k$ are equal; from any initial distribution, the process converges.
13.17 DO: LN 8.2.1 (refer to Figure 8.3 rather than 8.2): a MC with 5 states to practice the concepts.
13.18 CHALLENGE PROBLEM. LN 8.1.34 (powers of the transition matrix of an ergodic MC converge).
13.19 DO: Prove: (a) If $A,B$ are $k\times\ell$ matrices then $\rank(A+B)\le \rank(A)+\rank(B)$. (b) If $A$ is a $k\times \ell$ matrix and $B$ is an $\ell\times m$ matrix then $\rank(AB)\le \min\{\rank(A),\rank(B)\}$.
13.20 DO: A diad is a $k\times\ell$ matrix of the form xy where x is a $k\times 1$ matrix (column vector) and y is an $1\times\ell$ matrix (row vector). (a) Prove that the rank of a diad is at most 1. (b) Prove that every matrix of rank at most 1 is a diad. (c) Prove that every matrix of rank $r$ is the sum of $r$ diads.
13.21 DO: Let $A$ be an $n\times n$ matrix. Prove: if $v_1,\dots,v_k$ are eigenvectors of $A$ corresponding to distinct eigenvalues then $v_1,\dots, v_k$ are linearly independent.
13.22 DO: Let $R = \left( \matrix{1 & 1 \\ 0 & 1}\right).$ (a) Compute the eigenvalues and eigenvectors of $R$. (b) Compute $R^k$ for all $k$. (Experiment, observe pattern, prove by induction.)
13.23 DO: Let $F = \left( \matrix{1 & 1 \\ 1 & 0}\right).$ (a) Compute the eigenvalues and eigenvectors of $F$. (b) Compute $F^k$ for all $k$. (Experiment, observe pattern, prove by induction. The answer to this problem is highly self-rewarding.)
13.24 DO: (a) Study "determinant expansion by minors" from Wolfram's Math World (google "determinant expansion"). (b) Compute the value $d_n$ of the determinant of the following $n\times n$ matrix: $$ \left( \matrix{ 1 & 1 & 0 & 0 & 0 & \cdots & 0 & 0 & 0 \\ -1 & 1 & 1 & 0 & 0 & \cdots & 0 & 0 & 0 \\ 0 & -1 & 1 & 1 & 0 & \cdots & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots &\vdots &\vdots &\vdots\\ 0 & 0 & 0 & 0 & 0 & \cdots & -1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & \cdots & 0 & -1 & 1 \\ } \right) $$ (Each diagonal entry and each entry just above the diagonal is $1$, each entry just below the diagonal is $-1$; all other entries are $0$.) (Experiment, notice pattern, prove by induction. Self-rewarding.)
13.25 DO: Consider an $n\times n$ matrix $A$. (a) Prove that elementary column operations do not change the value of the determinant. Same about elementary row operations. (b) Prove: a transposition of columns switches the sign of the determinant. (c) Prove: if we multiply a row (or column) by a scalar $\beta$, the value of the determinant is multiplied by $\beta$. (d) Given $\det(A)$ and $\beta$, what is $\det(\beta A)$ ? (Warning: in general, not $\beta\det(A)$.)
13.26 DO (rank-nullity theorem): Let $A$ be a $k\times n$ matrix. Let $U = \{x\in\rrr^n \mid Ax = 0 \}$ denote the set of solutions of the system $Ax=0$ of $k$ homogeneous linear equations in $n$ unknowns. (a) Prove that $U$ is a subspace of $\rrr^{\ell}$. Prove: $\dim(U) = n - \rank(A)$.
13.27 DO: An upper triangular matrix is a square matrix $A=(\alpha_{ij})$ such that if $i< j$ then $\alpha_{ij}=0$ (all entries below the diagonal are zero). Let $A$ be an $n\times n$ upper triangular matrix. Prove: (a) $\det(A)=\prod_{i=1}^n \alpha_{ii}$ (product of the diagonal entries). (b) The eigenvalues, with proper multiplicity, are exactly the diagonal entries $\alpha_{ii}$. (c) What are the eigenvalues of the matrix $B$ below, and what are their multiplicities? $$ B = \left( \matrix{ 2 & 1 & 17 \\ 0 & 5 & 41 \\ 0 & 0 & 2} \right) $$ (d) Prove that this matrix has no eigenbasis. (e) Prove: if we replace the entry $41$ by $51$, the matrix will have an eigenbasis. (Your solutions to (d) and (e) should involve virtually no calculation. Use the rank-nullity theorem (preceding exercise).)
13.28 DO: Let $A$ and $B$ be $n\times n$ matrices. We say that $A$ and $B$ are similar if there exists a nonsingular matrix $C$ such that $B = C^{-1}AC$. We say that a matrix $A$ is diagonalizable if $A$ is similar to a diagonal matrix. (a) Prove: a matrix is diagonalizable if and only if it has an eigenbasis. (b) Suppose all (complex) eigenvalues of the matrix $A$ are equal to 1. Prove: $A$ is diagonalizable if and only if $A$ is the identity matrix. (b) (REWARD PROBLEM) Prove: over $\ccc$, every square matrix is similar to an upper triangular matrix. If all eigenvalues of $A$ are real then this is true over the reals.
13.29 DO: Prove, without using the Spectral Theorem, that all eigenvalues of a real symmetric matrix are real. Hint: Use the standard Hermitian dot product $x\cdot y = \sum_{i=1}^n {\overline x_i}y_i$ where $x,y\in \ccc^n$ with coordinates $x_i$ and $y_i$, respectively, and the bar denotes the complex conjugate.
13.30 DO: Find the complex eigenvalues and eigenvectors of the "rotation matrix" (corresponding to the rotation by $\theta$ of the plane) $$ R_{\theta} = \left( \matrix{ \cos \theta & \sin \theta \\ -\sin \theta & \cos \theta } \right) $$ Notice that these matrices have a common eigenbasis, which is orthogonal with respect to the standard Hermitian dot product.
13.31 DO: (a) Find a real $2\times 2$ matrix which has no real eigenvaules. (b) Prove: every real $3\times 3$ matrix has at least one real eigenvalue. The same is true if we replace $3$ by any odd number.
13.32 DO: Let $\lambda_1,\dots,\lambda_n$ denote the (complex) eigenvalues of the $n\times n$ (complex) matrix $A$. The $\lambda_i$ are listed with proper multiplicities (as the roots of the characteristic polynomial). Prove: (a) $\sum_{i=1}^n \lambda_i = \trace(A)$ (the trace of $A$, i.e., the sum of the diagonal elements); (b) $\prod_{i=1}^n \lambda_i = \det(A)$. (c) Verify these statements for all those matrices for which we previously calculated the eigenvalues.
12.1 HW: Recall that the period of a vertex $v$ (denoted $\period(v)$) in a digraph $G=(V,E)$ is the g.c.d. of the lengths of all closed walks passing through $v$. Prove: if the vertices $v$ and $w$ belong to the same strong component of $G$ then $\period(v)=\period(w)$. Hint. Prove that $\period(v)$ divides $\period(w)$. Your proof should be very short (some notation plus 3 or 4 essential lines). (12 points)
12.2 HW: Assume the digraph $G$ is strongly connected; its period $\period(G)$ is defined as the common value of the periods of its vertices. Prove that the period of $G$ is equal to the g.c.d. of the lengths of all cycles in $G$. Hint. Let $p$ denote the period of $G$ and $d$ the g.c.d. of the lengths of all cycles. Prove the two statements $p\mid d$ and $d\mid p$ separately; make it clear which one you are proving. One of these is immediate based on the preceding exercise; which one? To prove the other direction, prove the following Lemma: the length of every closed walk in $G$ is a linear combination (with integer coefficients) of the lengths of cycles. (12 points)
11.1 HW: Let $G=(V,E)$ be an Eulerian digraph, i.e., assume $(\forall v\in V)(\deg^+(v) = \deg^-(v))$. (Here $\deg^+(v)$ is the outdegree of $v$, and $\deg^-(v)$ is the indegree.) Prove: if $G$ is weakly connected then $G$ is strongly connected. ("Weakly connected" means it is connected if we ignore orientation. "Strongly connected" means $(\forall v,w\in V)(\exists v\to\dots\to w$ directed path $)$.) Hint: prove the following lemma. Let $H=(W,F)$ be a (not necessarily Eulerian) digraph and let $A\subseteq W$. Let $\delta^+(A)$ denote the number of edges going from $A$ to ${\overline A}$ (the complement of $A$ in $V$) and let $\delta^-(A)$ denote the number of edges going from ${\overline A}$ to $A$. Then $\delta^+(A) - \delta^-(A) = \sum_{v\in A}(\deg^+(v) - \deg^-(v))$. (12 points) (Note: in class I stated that this problem was due Friday. The submission date has been changed to Monday.)
11.2 HW: Diseases $A$ and $B$ have similar symptoms. Let $W$ be the population of all patients showing these symptoms. The two diseases can only be differentiated by costly tests. We know (from sampling the population and performing these costly tests) that 70 % of $W$ have disease $A$, 25 % have disease $B$, and 5 % have some other disease. We consider the effectiveness of treatment $T$. We know that 60 % of the patients with disease $A$ respond to $T$, while only 12 % of the patients with disease $B$ respond to treatment $T$. From the rest of the population $W$, 40 % respond to treatment $T$.
(a) A new patient arrives at the doctor's office. The doctor determines that the patient belongs to $W$. What is the probability that the patient will respond to treatment $T$? (5 points)
(b) ("Probability of causes") The patient's insurance will not pay for the expensive tests to differentiate between the possible causes of the symptoms. The doctor bets on treatment $T$. A week later it is found that the patient did respond to the treatment. What is the probability that the patient had disease $A$? (Hint: review LN 7.1.9 ("Theorem of Complete Probability").) (10 points)
11.3 DO: Let $A$ denote the adjacency matrix of a digraph $G$. Prove that the $(i,j)$ entry of $A^t$ counts the directed walks of length $t$ from vertex $i$ to vertex $j$.
11.4 DO: Let $T$ be the transition matrix of a finite Markov Chain. Prove that the $(i,j)$ entry of $T^t$ is $P(X_{k+t}=j \mid X_k=i)$, the probability of transition in $t$ steps from state $i$ to state $j$. Hint. Theorem of Complete Probability.
11.5 DO: Prove that the product of two stochastic matrices is a stochastic matrix. As a consequence, the powers of a stochastic matrix are stochastic.
11.6 DO: Let $X$ be a random variable which takes nonnegative integer values. The expression $g_X(t) = \sum_{k=0}^{\infty} P(X=k)t^k$ defines the generating function of $X$. Over a finite sample space this function is a polynomial. Prove: if $X,Y$ are two random variables that take integer values and they are independent then $g_{X+Y}=g_Xg_Y$.
11.7 READ: MN Chapters 10.1--10.3 (pp 294--317) (generating functions)
11.8 HW: LN 5.2.3 (Fibonacci-type sequence) (6+6 points)
11.9 DO: LN 5.2.4 (generating functions of known sequences)
11.10 READ LN Chap 6.2 (digraphs) pp 56-61.
11.11 READ LN Chap 8 pp 79-81 (first three pages of the Finite Markov Chains chapter)
11.12 READ MN Chapters 4.4 and 4.5 (Eulerian graphs/digraphs) (Chapters 3.4 and 3.6 (!) in the first edition).
10.1 HW: Solve Problem 2 of Quiz-3: prove that for almost all graphs, $\chi(G) > (\omega(G))^{100}.$ (12 points)
DO exercises will be posted later.
9.1 HW: Prove that every (nonempty) planar graph has a vertex of degree at most five. (Your proof should be just one essential line based on a result proved in class.) (5 points)
9.2 HW ("6-Color Theorem"): Prove that every planar graph is 6-colorable (i.e., the chromatic number of every planar graph is at most 6). (8 points)
9.3 DO: Prove: if $G$ is planar then $\alpha(G)\ge n/6$.
9.4 DO: (a) Prove: If $G$ is a triangle-free planar graph with $n\ge 3$ vertices and $m$ edges then $m\le 2n-4$. (b) Infer that the complete bipartite graph $K_{3,3}$ is not planar.
9.5 DO: Let $G$ be a graph with $n$ vertices. Prove: if both $G$ and its complement $\overline G$ are planar then $n\le 10$.
9.6 DO (cases of Ramsey's Theorem): Using the Erdös-Rado arrow notation, prove: (a) $6\to (3,3)$ (b) $10\to (4,3)$ (c) $17\to (3,3,3)$ (d) (Erdös - Szekeres) For all $k,\ell \ge 0$ we have $$ \binom{k+\ell}{\ell} \to (k+1,\ell+1).$$ Use induction on $k+\ell$. Note that you will need infinitely many base cases. (e) Infer from (d): $4^k \to (k+1,k+1)$.
9.7 HW: Prove: $(\forall n\ge 1)(n^2 \not\to (n+1,n+1))$. (Your solution should be very simple; the essence should fit on half a line.) (8 points)
9.8 DO: Let $n\ge 2$ and $d_1,\dots,d_n \ge 1$ such that $\sum_{i=1}^n d_i = 2n-2$. Let $N(d_1,\dots,d_n)$ denote the number of trees on the vertex set $[n]=\{1,2,\dots,n\}$ satisfying $(\forall i)(\deg(i)=d_i)$. Prove: $$N(d_1,\dots,d_n) =\frac{(n-2)!}{\prod_{i=1}^n (d_i-1)!}$$ Hint: Induction on $n$. To reduce the current instance of the problem to a smaller instance (an instance with a smaller value of $n$) (for the inductive step), infer from the given constraints that $(\exists i)(d_i = 1)$.
9.9 HW: Use 9.8 to prove Cayley's formula in one essential line. Cayley's formula says that the number of trees on a given set of $n$ vertices is $n^{n-2}$. Hint: Multinomial Theorem. (5 points)
9.10 DO (due Tuesday, Nov 9, before the tutorial): Study the inclusion-exclusion principle. Read MN, Chapters 3.7 ("Inclusion-exclusion principle") and 3.8 ("The hatcheck lady & co.") (numbered 2.7 and 2.8 in the first edition). Understand all the three proofs given in Chap. 3.7. Prove the following version which is stated in terms of probabilities of events.
(a) Let $A_1,\dots,A_k$ be events and let $B$ denote the complement of their union: $$B = {\overline{A_1\cup\dots\cup A_k}}.$$ Then $$P(B) = \sum_{I\subseteq [k]} (-1)^{|I|}P\left(\bigcap_{i\in I} A_i\right),$$ where $[k] = \{1,\dots,k\}$. (How many terms are there in this sum? What is the term corresponding to the empty set $I = \emptyset$ ?) The most elegant proof mimics the third proof given in MN; use indicator variables and the linearity of expectation for a particularly elegant rendering.
(b) Show that the version stated in MN, Chap. 3.7, is an immediate consequence of this version. We shall refer to the MN version as the "counting version" whereas the version in (a) the "probability version."
(c) Let $$S_j = \sum_{I\subseteq [k], |I|=j} P\left(\bigcap_{i\in I} A_i\right).$$ (This is the sum of the probabilities of the $j$-wise intersections of the $k$ events. What is the number of terms in this sum?) Then $$P(B) = \sum_{j=0}^k (-1)^j S_j = S_0 - S_1 + S_2 - + \dots.$$ (Note that this is just a rearrangement of the expression given under (a).)
(d) Explain why $S_0 = 1$ and $S_1 = P(A_1)+\dots+P(A_k)$.
9.11 DO: Prove: for all $r,n$ satisfying $0\le r < n$ we have $$\sum_{j=0}^r (-1)^j\binom{n}{j} = (-1)^r \binom{n-1}{r}.$$ Solve the cases $r=0,1,2$ first. (The original posting contained a typo: summation running from $1$ to $r$ instead of $0$ to $r$. Typo corrected Monday 1:30pm. Thanks and bonus points to the student who warned me.)
9.12 HW (due Wednesday, Nov 10). The counting version of "Bonferroni's inequalities" is stated at the end of MN, Chap. 3.7. Prove the probability version, stated below using the notation of Exercise 9.10:
If $r$ is even then
$P(B) \le \sum_{j=0}^r (-1)^j S_j$; and
if $r$ is odd then
$P(B) \ge \sum_{j=0}^r (-1)^j S_j$.
(In other words, the alternating sums $S_0$, $S_0-S_1$,
$S_0-S_1+S_2$, etc., fall on alternate sides of
the value $P(B)$.) Hint. Try to mimic the second proof of
the inclusion-exclusion principle given in MN. Use the
preceding exercise (Exercise 9.11). Do not prove 9.11.
Your solution should take just a few lines.
(12 points)
If you cannot solve this in general, solve it for $r=0,1,2$.
(1+1+3 points).
(The original posting contained typos: the right-hand side
of both inequalities showed $S_r$ instead of $S_j$.
Typos corrected Monday 2:15pm. Thanks and bonus points
to the student who warned me.)
8.1 HW (stated in class): (a) Prove that almost all graphs are not planar. In other words, let $p_n$ denote the probability that a random graph on a given set of $n$ vertices is planar; you need to show that $p_n \to 0$. (Our random graphs are uniform, i.e., edges are drawn independently with probability $1/2$.) (b) Prove that $p_n$ is exponentially small, i.e., $(\exists c<1)($ for all sufficiently large $n)(p_n < c^n)$. State your value of $c$ explicitly. (c) Prove that $p_n$ is square-exponentially small, i.e., $(\exists d<1)($ for all sufficiently large $n)(p_n < d^{n^2})$. State your value of $d$ explicitly. (d) Prove that $(\forall \epsilon >0)($ for all sufficiently large $n)(p_n < (2-\epsilon)^{-n^2/2})$. (6 + 3 + 3 + 3 points) Note that $(d) \Rightarrow (c) \Rightarrow (b) \Rightarrow (a)$; so if you solve, say, (c), you also get the points for (a) and (b). If you solve (d), you get all the 15 points. - In class the due date was stated as "Wednesday." The due date has been postponed to Friday. - Added on Nov 5, 4am: in part (d) we also need to require $\epsilon < 2$, so the first quantifier needs to be changed to $(\forall \epsilon\in (0,2))$.
7.1 HW (stated in class): Construct two random variables over the same probability space that are uncorrelated but not independent. Make your sample space small. ($X$ and $Y$ are uncorrelated if $E(XY)=E(X)E(Y)$.) (8 points)
6.1 HW (was due Oct 20, do not hand in now): prove that $\chi(G) \le \deg_{\max}(G)+1$. (7 points)
6.2 HW: Problem 6.1 was solved by the "greedy coloring algorithm" as follows. The set of vertices is $\{1,\dots,n\}$; the "colors" are the positive integers. The algorithm:
For $i=1$ to $n$ color vertex $i$ by the smallest color $c$
such that
$(\forall j)($ if $j < i$ and $j$ is adjacent to $i$ then
the color of $j$ is not $c)$.
Prove that this is a very poor algorithm: for every $n$, construct a bipartite graph with $2n$ vertices such that the greedy coloring algorithm will use $n$ colors. (8 points)
6.3 HW (Due Wednesday, Oct 27): Prove that every triangle-free graph on $n$ vertices is colorable by $O(\sqrt{n})$ colors. Give a specific (small) value for the constant hidden in the big-Oh notation. (10 points)
6.4 HW: LN 7.2.13 (club with 2000 members). Assume the club serves vodka to all its members. - Make sure you give a clear definition of the random variables you use. The clarity of the definition accounts for 3/4 of the credit. Hint. Learn about indicator variables (LN 7.2.6, 7.2.7). Represent the number of lucky members as a sum of indicator variables. (8 points) What is the size of the sample space for this experiment? (1 point) NOTE: This problem was posted with the wrong LN problem number. Corrected and hint added: 10/22, 9pm.
6.5 HW (due Wednesday, Oct 27): We construct a random graph $G$ on a given set of $n$ vertices by flipping a fair coin for each pair $\{i,j\}$ of distinct vertices to decide whether or not they will be adjacent. What is the expected number of cycles of length $k$ in this graph? Give a closed-form expression. Define your variables. A clear definition accounts for 1/2 of the credit. (8 points) What is the size of the sample space for this experiment? (1 point) NOTE: The Wednesday due date was added on 10/22, 9pm
6.6 DO: LN 6.1.37 (Grötzsch's graph.) Give a nice drawing of your graph.
6.7 HW (due Wednesday, Oct 27): LN 6.1.43 (Hamiltonicity of the grid) (8 points)
6.8 HW: LN 6.1.35 (chromatic number vs. independence number) (8 points)
6.9 HW: Find a graph $G$ with a maximal independent set $S$ such that $\alpha(G) = 100|S|$. (An independent set is maximal if it cannot be extended to a larger independent set. You are asked to show that maximal independent sets can be quite small compared to maximum independent sets, i.e., independent sets of maximum size.) (8 points)
6.10 REWARD PROBLEM. Verify Cayley's $n^{n-2}$ formula for $n = 7$ by computing the number of automorphisms (self-isomorphisms) for each tree in problem 4.1.
6.11 HW: Let us consider the uniform distribution over a sample space of size $p$ where $p$ is a prime number. Prove: no two nontrivial events in this probability space are independent. (The trivial events are $\Omega$ and the empty set.) (6 points)
6.12 DO: (a) Prove: if $X$ is a random variable then $\min X \le E(X) \le \max X$. (b) If equality holds in either of these inequalities then what can we say about $X$ ?
6.13 DO: (a) Prove that for $k = 0,\dots,n$ the binomial coefficients $\binom{n}{k}$ increase until the middle and then decrease. (b) Let us consider a sequence of $n$ independent Bernoulli trials with parameter $p$ (biased coin flips with probability $p$ of "heads"). Determine the probability $P(n,k)$ that exactly $k$ of the coins come up "heads." (c) Prove that the sequence $P(n,0), P(n,1),\dots, P(n,n)$ increases up to $P(n,k^*)$ and decreases afterwards, where $|k^* - np| < 1$.
6.14 DO: LN 7.1.5 (Union bound)
6.15 DO: LN 7.1.7 (conditional probabilities for intersection of three events)
6.16 DO: LN 7.1.9 (Theorem of Complete Probability)
6.17 DO: LN 7.1.12 (independence of complement of event)
6.18 DO: LN 7.1.17 (three pairwise but not fully independent events)
6.19 DO: LN 7.1.18 (independence of functions of blocks of independent events)
6.20 DO: LN 7.1.19 (three-colored balls in an urn)
6.21 DO: LN 7.1.25 (if we have n nontrivial independent events, the sample space must have size ≥ 2n).
6.22 DO: LN 7.1.24 (k events that are (k-1)-wise but not fully independent)
6.23 CHALLENGE PROBLEM. LN 7.1.26 (small sample spaces for pairwise independent events)
6.24 CHALLENGE PROBLEM. LN 7.1.27 (lower bound for sample spaces for pairwise independent events) (Hint. Prove the same lower bound for pairwise independent non-constant random variables with zero expected value.)
6.25 HW, due Wednesday, Oct 27; parts (c) and (d) due Friday, Oct 29. (triangles in random graph): Let $X_n$ denote the number of triangles in a random graph $G = (V,E)$ on a given set $V$ of $n$ vertices, generated in the way described in Problem 6.5. (a) What is the size of the sample space for this experiment? (b) Determine $E(X_n)$. (c) Determine ${\var}(X_n)$. Your answer should be a closed-form expression (no dot-dot-dots or summation or product symbols). (d) Asymptotically evaluate $\var(X_n)$. Your answer should be a formula of the form $\var(X_n)\sim cn^d$. Determine the constants $c$ and $d$. (1+4+10+6 points)
If you have not responded to the Questionnaire yet, please do NOW.
5.1 HW: Let $a_n >1$ and $b_n >1$ be sequences. True or false: If $a_n=o(b_n)$ then (a) $\ln(a_n) = o(\ln(b_n))$; (b) $\ln(a_n) = O(\ln(b_n))$. Prove your answers. (6+6 points)
5.2 HW: Let $(\Omega, P)$ be a finite probability space and let $X,Y\,:\,\Omega\to\rrr$ be two random variables. (a) Prove: $E(X+Y)=E(X)+E(Y).$ (b) Prove that $E(XY)$ is not necessarily equal to $E(X)E(Y)$. Make your counterexample as small and simple as you can. (6+6 points)
5.3 HW: (a) Let us roll a (6-sided) die and let $X$ denote the number that comes up. Calculate $E(X)$. Show your work. (b) Let us roll $k$ dice. (b1) What is the size of the sample space for this experiment? (b2) Let $Y$ denote the sum of the $k$ numbers that come up. Determine $E(Y)$. Your answer should be a simple closed-form expression. (6+6 points)
4.1 HW: Draw all trees with seven vertices. Draw each of them only once (up to isomorphism). State how many non-isomorphic trees you got. (9 points; lose 2 points for each mistake) (Omitted trees and repeated trees count as mistakes.)
4.2 DO (stated in class): A graph is self-complementary if it is isomorphic to its complement. (a) Find a self-complementary graph with 4 vertices. (b) Find a self-complementary graph with 5 vertices. (c) Prove: if a self-complementary graph has $n$ vertices then $n\equiv 0$ or $1 \pmod 4$.
4.3 DO (stated in class): Prove that every tree on $n$ vertices has $n-1$ edges. Hint: Prove that every tree with $n\ge 2$ vertices has a vertex of degree 1. Then use induction.
4.4 DO What is the chromatic number of the cycle of length $n$?
4.5 DO Count the $k$-cyles in the complete graph $K_n$, i.e., those subgraphs of $K_n$ which are cyles of length $k$.
4.6 DO Count the strings of length $n$ over the alphabet $\{A,B\}$ without consecutive occurrences of $A$. (For instance, $ABBA$ counts but $BAAB$ does not.) Hint. Experiment with small values of $n$. Notice pattern, make conjecture. Prove.
4.7 CHALLENGE PROBLEM. True or false? (Prove.) $(1+1/n)^{n^2} \sim \eee^n$.
3.1 DO: LN 4.1.19 (decide whether or not system of simultaneous congruences is solvable; if YES, solve, if NO, prove)
3.2 DO: LN 4.1.20 (system of simultaneous congruences)
3.3. DO: Let $\gcd(x,y)=d$ and $\gcd(x+y,x-y)=D$. Prove: either $D=d$ or $D=2d$.
3.4. DO: LN 2.2.1 - 2.2.5 (basic properties of asymptotic equality)
3.5 DO: LN 2.2.6 (a) - (d) (basic asymptotic equalities)
3.6 DO: LN 2.2.7 (find $a_n\sim b_n$ such that $a_n^n\not\sim b_n^n$)
3.7 DO: LN 2.2.12 (asymptotics of the $n$-th prime)
3.8 HW: LN 2.2.9 (asymptotically evaluate the middle binomial coefficient). Hint: use Stirling's formula. (8 points)
3.9 DO: LN 2.2.13 (chance of picking a prime)
3.10 DO: LN 5.1.4 (number of odd subsets = number of even subsets: two proofs)
3.11 DO: LN 5.1.2 ($p$ divides binomial coefficient)
3.12 HW: Use the preceding exercise (without proof) to give an inductive proof of Fermat's little Theorem. Hint: show that FlT is equivalent to the statement that $(\forall a)(\forall$ primes $p)(a^p\equiv a \pmod p)$. Prove this statement by induction on $a$ for positive $a$; then extend it to negative values of $a$. (10 points)
3.13 REWARD PROBLEM: LN 5.1.6 (count sets of size divisible by 4)
3.14 HW: LN 5.1.9 (lower bound for binomial coefficients) (6 points)
3.15 DO: Prove: $(\forall k)(k!\ge (k/\eee)^k)$. Do not use Stirling's formula, only the elements of calculus. Hint. Use the power series expansion of $\eee^k$. Note: Stirling's formula implies a stronger lower bound for all sufficiently large $k$ but not for all $k$.
3.16 HW (due Friday, Oct 15): LN 5.1.10 (upper bound for binomial coefficients) Use the preceding exercise without proof. (6 points) NOTE: in the original posting, it said "Use exercise 3.13" instead of the preceding exercise (3.15). Error corrected Monday, Oct 11, 11pm.
3.17 CHALLENGE PROBLEM: LN 5.1.11 (upper bound on tail of binomial series)
3.18 CHALLENGE PROBLEM: LN 4.3.4 (determinant of gcd's)
2.1 DO: (a) Find a relation on the integers, frequently used in class, that is reflexive and transitive but not symmetric. (b) Is the relation "$x$ and $y$ are relatively prime" (b1) reflexive? (b2) symmetric? (b3) transitive? (c) Find an equivalence relation on the integers where all equivalence classes are finite and have at least 100 elements. (An "equivalence class" is a block of the partition corresponding to the equivalence relation.)
2.2 DO: Compute $2^{1,000,000} \bmod{55}$ without the help of a calculator. Your answer should be a number between $0$ and $54$. Hint. First calculate this number modulo $5$ and modulo $11$ using Fermat's little Theorem; then combine the two results via the Chinese Remainder Theorem.
2.3 DO: Prove: $(\forall a)(a^{13}\equiv a \pmod{91})$. Hint. $91 = 7\cdot 13$. Prove the congruence modulo 7 and separately modulo 13. Remember that FlT requires the base to be relatively prime to the modulus, and we have no such assumption here, so you will need to consider the cases when this condition does not hold separately.
2.4 DO: Does the pair of congruences $2x\equiv 1 \pmod{35}$ and $3x\equiv 26 \pmod{77}$ have a common solution? Hint. Reduce to congruences modulo primes.
2.5 DO: Write $1$ as a linear combination of $71$ and $38$. You may use a calculator for division/multiplication but not for more advanced operations such as multiplicative inverse. Hint: Find the multiplicative inverse of $71$ modulo $38$ as shown in the tutorial (Euclid's algorithm).
2.6 DO: Prove the basic properties of congruences: (a) congruence modulo $m$ is an equivalence relation; (b) congruences modulo $m$ can be added and multiplied.
2.7 DO: Prove: if $a\equiv b\pmod m$ then $\gcd(a,m)=\gcd(b,m)$.
2.8 DO: Porve: if $a_n, b_n$ are sequences of positive real numbers, $a_n \to\infty$, and $a_n = \Theta(b_n)$, then $\ln a_n \sim \ln b_n$.
2.9 DO: (a) Prove: $F_{n+1} = \Theta(F_n)$ where $F_n$ is the $n$-th Fibonacci number. (b) Find an increasing sequence $a_n$ of positive real numbers such that $a_{n+1} \neq \Theta(a_n)$. Your answer should be very simple.
2.10 DO: Find $\lim_{n\to\infty} \sqrt{n^2+n}-n.$
2.11 DO: Assume $a_n\sim b_n$. (a) Does it follow that $a_n+1\sim b_n+1$ ? (b) Does it follow that $a_{n+1}\sim b_{n+1}$ ?
1.1. DO: review the concept of limits, especially at infinity. Define them using properly quantified formulas.
1.2 (due Fri, Oct 9) STUDY asymptotic equality (LN Chap 2.2)
1.3. DO: Prove: every equivalence relation arises from a partition. (Two elements are equivalent if and only if they belong to the same block of the partition.)
1.4. DO: (a) When are two integers congruent modulo 1? (b) When are two integers congruent modulo 0? (c) List the residue classes modulo 4 (by representatives). Construct their addition and multiplication tables. (These will be 4 by 4 tables with entries 0,1,2,3.) (d) Prove: every prime number other than 2 is congruent to 1 or -1 modulo 4. (e) Prove: every prime number other than 2 and 3 is congruent to 1 or -1 modulo 6.
1.5. DO: Prove: if $a \mid x$ and $a \mid y$ then $a \mid x+y$ and $a \mid x-y$. (The vertical bar stands for divisibility: "$a$ divides $x$," etc.)
1.6. DO: LN 1.2.5 (a)(b)(c) (Numbers and quantifiers) Give clear TRUE/FALSE answers to each problem and prove your answers. The proofs should be very short.
1.7. HW (due Mon, Oct 4): True or false? Give very simple proofs. Remember: to prove the statement, you need to devise a winning strategy for the existential player (tell its moves as a function of the histroy of the game so far); to disprove it, you need to devise a winning strategy for the universal player. (The domain of the variables is $\zzz)$. (5+5+5+5 points)
(a) $(\forall x)(\exists y)(\forall z)(z\mid x+y)$.
(b) $(\forall x)(\exists y)(x+y \mid x^2+y^2)$.
(c) $(\exists x,y)(\forall z)(\gcd(x+z,y+z) \mid \gcd(x+z+1,y+z+1))$
(d) $(\forall x,y)(\exists z)(\gcd(x+z,y+z) \mid \gcd(x+z+1,y+z+1))$
1.8 DO: Recall that two integers are relatively prime if their gcd is 1. Find three integers $x,y,z$ such that $\gcd(x,y,z)=1$ but $x,y,z$ are pairwise not relatively prime (i.e., $\gcd(x,y)\neq 1$, $\gcd(y,z)\neq 1$, $\gcd(x,z)\neq 1$).
1.9 HW (due Mon, Oct 4): Prove: $(\forall x,y)(x^2+y^2\not\equiv -1 \pmod 4).$ Hint: first determine, to which modulo 4 residue classes do the square integers belong. (8 points)
1.10: (a) Prove: if $x \equiv -1 \pmod{8}$ then $x$ cannot be written as a sum of 3 squares. ("$\equiv$" stands for congruence.) (b) Write this statement as a properly quantified expression.
1.11. DO: LN 4.1.15 (a)(b) (Number of divisors)
1.12. HW (Due Mon, Oct 4): LN 4.2.12 (10 points) (Periodicity of the Fibonacci numbers modulo $m$).
1.13. DO: Study Euclid's Algorithm (LN Sec 4.1)
1.14. HW (due Wed, Oct 6): LN 4.1.15 (c) (10 points) (Upper bound on the number of divisors)
1.15 DO: LN 1.2.5 (d)(f)(h) (logic and numbers)
1.16 DO: LN 4.1.27 (logic and gcd)
1.17 HW (due Wed, Oct 6): Prove: if $d$ is a common divisor of $a$ and $b$ and at the same time $d$ is a linear combination of $a$ and $b$ then $d$ is a greatest common divisor of $a$ and $b$. (10 points)
1.18. DO: LN 4.2.9 (members in a mod $m$ residue class have the same gcd with $m$) (8 points)
1.19. DO (Due Tue, Oct 5, before tutorial): LN 4.14 (a) (b) (compute gcd's using Euclid's Algorithm). In addition, find a representation of the gcd's obtained as linear combinations.
1.20. HW (Due Wed, Oct 6) LN 4.1.17 (a)-(e) (multiplicative inverse) (2+5+5+5+5 points)
1.21 (due Wed, Oct 6). REVIEW mathematical induction.
1.22. DO (due Wed, Oct 6) LN 4.1.22 (a) (consecutive Fibonacci numbers are relatively prime)
1.23. DO (due Fri, Oct 9): (a) Define the least common multiple in analogy with our definition of the greatest common divisor.
(b) Prove that l.c.m. exists. Hint: do not try to mimic the proof of the existence of a g.c.d.; use instead the fact that g.c.d. exist: represent the l.c.m. as the g.c.d. of a certain set of numbers (which numbers?).
(c) LN 4.2.10: $\gcd(a,b)\lcm(a,b)= |ab|$.
1.24. DO (due Fri, Oct 9): LN 4.1.27 (tiny questions on gdc, lcm, congruence mod 24)
1.25. CHALLENGE PROBLEM. LN 4.3.4. (Determinant of gcd's.)
1.26. CHALLENGE PROBLEM. LN 4.2.13 (Integer-preserving polynomials)
1.27. CHALLENGE PROBLEM. LN 4.2.2, part 2. (Divisor game)
1.28. REWARD PROBLEM: LN 4.2.6: $\gcd(a^m-1, a^n-1)$.
1.29. CHALLENGE PROBLEM: LN 4.2.8 (gcd of Fibonacci numbers)
1.30 DO: Find a sequence of real numbers which is bounded but has no limit.
1.31 DO: Determine the limits of the following sequences as $n\to\infty$.
(a) $\frac{7n^2+3n-100}{3n^2+10n+1000}$ ; (b) $\frac{\ln n}{\sqrt{n}}$ ; (c) $\frac{n^{100}}{1.001^n}$.
1.32 DO: Determine the limits of the following functions as $x\to 0$.
(a) $\frac{\ln(1+x)}{x}$ ; (b) $\frac{\sin x}{x}$; (c) $\frac{\sqrt{1+x} -1}{x}$;
1.33 DO: Recall that two sequences $a_n$ and $b_n$ are asymptotically equal if $\lim_{n\to\infty} a_n/b_n = 1.$ Notation: $a_n \sim b_n$. Here, fractions of the form $0/0$ are replaced by 1. Find very simple expressions that are asymptotically equal to each of the following expressions.
(a) $3n^4 +5n -100$ (b) $n + \cos n$ ; (c) $\sqrt{n^2+1}$ ; (d) $\sqrt{n^2+1}-n$ ; (e) $\binom{n}{5}$ ; (f) $\sum_{k=1}^n 1/k$.
1.34 DO: Prove: $\ln(n!) \sim n\ln n.$ Do not use any theorems, just the definition of asymptotic equality and basic properties of limits and logarithms. (Hint: notice that trivially, $\ln(n!) \le n\ln n$. Prove that for every $\epsilon >0$ we have $\ln(n!) > (1-\epsilon)n\log n$. In order to prove this, delete all the "small" terms from the product that defines $n!$; define "small" appropriately.)
1.35 DO: True or false (prove): If $a_n \sim b_n$ then
(a) $a_n^2 \sim b_n^2$ ; (b) $\sqrt{a_n} \sim \sqrt{b_n}$ ; (c) $2^{a_n} \sim 2^{b_n}$.
1.36 HW (due Mon, Oct 4): Assume $a_n, b_n > 1$.
Consider the following statement:
"If $a_n\sim b_n$ then $\ln a_n \sim \ln b_n.$"
(a) Prove that the statement is false. (Remember: $a_n, b_n >1$.)
(b) Prove that the statement becomes true if $a_n$ is bounded away from 1, i.e., $(\exists c>0)$ such that $a_n \ge 1+c$ for all sufficiently large $n$. (5+8 points)