13.1 DO: (a) If $v_1,\dots,v_m\in\{0,1\}^n$ are $(0,1)$-vectors and they are linearly independent over $\fff_p$ then they are linearly independent over $\rrr$.    (b) The converse is false for all $p$.

13.2 DO: Prove: For any matrices $A,B$ for which the product $AB$ is defined, we have $\rank(AB)\le \min\{\rank(A),\rank(B)\}$.

13.3 DO: Review the proof of the Oddtown Theorem: If If $A_1,\dots,A_m\subseteq [n]$ are sets such that    (i) $(\forall i)(|A_i|$ is odd$)$ and    (ii) $(\forall i\neq j)(|A_i\cap A_j|$ is even$)$    then $m\le n$.

13.4 NOTATION: Diagonal case of Erdös--Rado arrow symbol: $n\to (k)_2$ indicates $n\to(k,k)$ and $n\to(k)_s$ indicates $\displaystyle{n\to (\underbrace{k,k,\dots,k}_{s\text{ times}})}$. 13.5 DO: Observe: $4^k > \binom{2k}{k}$. The diagonal case of Erdös--Szekeres: $\binom{2k}{k}\to (k+1)_2.$ Combining these two it follows that $4^k \to (k+1)_2$. In other words, $n \to (1+ (1/2)\log_2 n)_2$. Question: How tight is this bound? Answer: tight within a factor of 4, see next exercise.

13.6 REVIEW: (Erdös, 1950):   $n \nrightarrow (1+ 2\log_2 n)_2$. --- Method: we prove that with high probability, a random graph does not have either an independent set or a clique of size $\ge 1+2\log_2 n$. (This result inaugurated the Probabilistic Method in combinatorics: proof of existence without explicit construction.)

13.7 HW (Zsigmond Nagy's explicit Ramsey graph construction): Nagy constructed the following graph for every $s\ge 3$. The graph has $n=\binom{s}{3}$ vertices, labeled as $\{v_T : T\subseteq [s], |T|=3\}$. Vertices $v_T, v_S$ are adjacent if $|S\cap T|=1$. Prove that this graph does not have either and independent set of a clique of size greater than $v$.    (Note: this proves $n\nrightarrow (c n^{1/3})_2$ via an explicit construction.)       (8 points)

13.8 DO: Find $\Omega(s^2)$ triples in $[s]$ such that every two of them intersect in at most 1 element.

13.9 REVIEW the statement of Ramsey's Theorem (general case: for $t$-uniform hypergraphs).

13.10 REVIEW the proof that $n\to (c \log\log n)_2^{(3)}$    (3-uniform Ramsey).

12.1 DEF: Recall the Erdös-Rado arrow symbol: the statement $n\to(k,\ell)$ means that no matter how we partition the set of edges of the complete graph $K_n$ into "red" edges and "blue" edges as $E(K_n)=R\dot\cup B$, there will either be an all-red $K_k$ or and all-blue $K_{\ell}$, i.e., there will exist a subset $A\subseteq V(K_n)$ such that either $|A|=k$ and $\binom{A}{2}\subseteq R$ or $|A|=\ell$ and $\binom{A}{2}\subseteq B$. Analogously, the statement $n\to(k,\ell,m)$ means that no matter how we partition the set of edges of the complete graph $K_n$ into "red," "blue," and "green" edges, either there will be an all-red $K_k$ or and all-blue $K_{\ell}$ or an all-green $K_m$.

12.2 DO: Generalize this definition to $s$ colors: define the statement $n\to (k_1,\dots,k_s)$.

12.3 REVIEW from class:    (a)   $6\to (3,3)$    and    (b)   $5\nrightarrow (3,3)$

12.4 DO:    $10\to (4,3)$

12.5 CH:    $9\to (4,3)$       (5 points)

12.6 DO (Erdös-Szekeres 1935): For all $k,\ell \ge 1$ we have $$ \binom{k+\ell}{k} \to (k+1,\ell+1) $$ Hint. By induction on $k+\ell$. Base cases: $k=1$ or $\ell=1$. Then for the inductive step you may assume $k,\ell \ge 2$. Fix a vertex $v$. Let $R$ be the set of "red neighbors" of $v$ and $L$ the set of "blue neighbors" of $v$. If we find either and all-red $K_k$ or an all-blue $K_{\ell+1}$ in $R$, we are done (why?). Argue analogously for $L$. If both $R$ and $L$ are too small to guarantee that one of these necessarily occurs then show that $n$ is too small. For this last step, use Pascal's identity: $\binom{k+\ell}{k}=\binom{k+\ell-1}{k}+\binom{k+\ell-1}{k-1}$.

12.7 HW: Prove:    $17\to (3,3,3)$.       (5 points)

12.8 DO: Prove: for all $k\ge 1$ we have    $\displaystyle{N\to (\underbrace{3,3,\dots,3}_{k\text{ times}})}$    where $N = \lceil \eee k!\rceil$.
Note that this includes the statements $6\to (3,3)$ and $17\to (3,3,3)$.

12.9 DO: (Ramsey's Theorem for graphs): For all positive integers $s$ and $k_1,\dots,k_s$ there exists $n$ such that $n\to (k_1,\dots,k_s)$.   (Ramsey's full theorem is for uniform hypergraphs.)

12.10 REVIEW from May 10 class (exercise set #10): Sperner families, Sperner's Theorem, the proof of the BLYM Inequality via Lubell's permutation method.

12.11 HW (baby Littlewood-Offord problem) (Parts (a) and (c) were assigned in class on May 10):    (a) Prove that there exists a positive constant $c$ such that the following holds for every $n \ge 1$. Given $a_1,\dots,a_n,b\in\rrr$ where $a_i > 0$, take $I\subseteq [n]$ uniformly at random (so the size of the sample space is $|\Omega|=2^n$). Then    $P(\sum_{i\in I} a_i = b) \le c/\sqrt{n}$.    (b) Let $c_n$ denote the smallest value of $c$ for which the conclusion of part (a) holds for a given $n$. Determine $\lim_{n\to\infty} c_n$.    (c) Prove that part (a) remains valid if the condition $a_i > 0$ is replaced by $a_i\neq 0$.          (9+6+5 points)

10.1 DO: Review all course material for Thursday's test, including the DO exercises.

10.2 DO: Prove: if $x\neq 0$ then $1+x < \eee^x$. (This is true regardless of the sign of $x$.)

10.3 DO: Let $G$ be a transitive group of permutations of the set $V$. Fix $v\in V$ and $A\subseteq V$. Let $\pi$ be a random element of $G$ (chosen uniformly). Prove: $P(v\in \pi(A))= |A|/n$.

10.4 DO: Review the proof of problem 5.20 (CH) from class: If $\calH=(V,\calE)$ is a vertex-transitive hypergraph then $\alpha(\calH)\chi(\calH) < n (1+\ln n)$.
Outline of proof: pick a maximum independent set $A$ (so $|A|=\alpha$) and a list of random automorphisms $\pi_1,\dots,\pi_s\in\aut(\calH)$. The $\pi_i$ are uniform over $\aut(\calH)$ and independent.
(a) Prove: for a fixed $v\in V$ we have $P(v\in\pi_1(A))=\alpha/n$. (See the preceding exercise.)
(b) Let $B=\bigcup_{i=1}^s \pi_i(A)$. Prove: for a fixed $v\in V$ we have $P(v\notin B)=(1-\alpha/n)^s$.
(c) Use the union bound to show: $P(B\neq V)\le n(1-\alpha/n)^s$. State the events of which you are taking the union.
(d) Infer: If $n\eee^{-\alpha s/n} \le 1$ then $\chi(\calH)\le s$. (Use Ex. 10.2.)
(e) Show that the smallest $s$ for which the assumption of item (d) holds is $\lceil (n/\alpha)\ln n\rceil$. Infer the stated upper bound on $\alpha\chi$.

10.5 DO: Review the proof that for all hypergraphs $\calH=(V,\calE)$ we have $\nu^*\le\tau^*$.
Hint: let $f:V\to\rrr$ be a fractional cover and $g:\calE\to\rrr$ a fractional matching. Evaluate the sum $\displaystyle{S=\sum_{(v,E): v\in E}f(v)g(E)}$ in two ways (accountant's principle) (where the summation extends over all incident vertex-edge pairs).

10.6 DO: If $\calH$ is $k$-uniform then $\nu\le n/k$.

10.7 DO: True or false: If $\calH$ is $k$-uniform then $\nu^*\le n/k$. Decide this question for every $k\ge 2$.

10.8 DO: If $\calH$ is $k$-uniform then $\tau\le k\tau^*$.

10.9 DO: (a) If $\calH$ is $k$-uniform then $\nu^*\le k\nu$.    (b) For infinitely many values of $k$ find $k$-uniform hypergraphs such that $\nu^* > (k-1)\nu$.

10.10 DO: Prove: If $\calH$ is $k$-uniform and regular then $\nu^*=\tau^*=n/k$. Do NOT use the Duality Theorem $\nu^*=\tau^*$.

10.11 DO: Prove: If $\calH$ is $k$-uniform then $\displaystyle{\tau\le \left\lceil \frac{n}{k} \ln m\right\rceil}$.

10.12 DO: Derive Ex. 5.20 (discussed above as Ex. 10.4) from the preceding exercise. Do NOT rehash the arguments of Ex. 10.4; what you need to do is reduce Ex. 5.20 to Ex. 10.11. So from the input data of Ex. 5.20 (a vertex-transitive hypergraph $\calH_1$) you need to construct input data for Ex. 10.11 (a $k$-uniform hypergraph $\calH_2$ for some $k$) such that the parameters $\alpha$ and $\chi$ of $\calH_1$ correspond to certain parameters of $\calH_2$ and an application of Ex. 10.11 to these parameters of $\calH_2$ translates back to the desired relation between $\alpha$ and $\chi$ for $\calH_1$.

10.13 DEF: We say that the sets $A,B$ are comparable if $A\subseteq B$ or $B\subseteq A$. A Sperner family is a list of sets $A_1,\dots,A_m$, no two of which are comparable, i.e., $(\forall i\neq j)(A_i\not\subseteq A_j)$.

10.14 Sperner's Theorem. If $A_1,\dots,A_m\subseteq [n]$ is a Sperner family then $\displaystyle{m \le \binom{n}{\lfloor n/2\rfloor}}$. (To be proved later.)

10.15 Lemma (BLYM Inequality) (Bollobás, Lubell, Yamamoto, Meshalkin): If $A_1,\dots,A_m\subseteq [n]$ is a Sperner family then $\displaystyle{\sum_{i=1}^m\frac{1}{\binom{n}{|A_i|}}\le 1}$.

10.16 DO: Deduce Sperner's Theorem from the BLYM Inequality.

10.17 DO: For all $n$ find cases where equality holds in the BLYM Inequality. The number of cases you find should grow with $n$.

10.18 CH (due May 24): Find all Sperner families for which equality holds in eth BLYM Inequality.        (10 points)

10.19 DO: Evaluate the sum $\displaystyle{\sum_{i=1}^m\frac{1}{\binom{n}{|A_i|}}\le 1}$ for the case when $m=2^n$ and the $A_i$ are all subsets of $[n]$. Your answer should be a very simple closed-form expression.

9.1 DO: Prove: If $n\ge k \ge 1$ then     $\displaystyle{\left(\frac{n}{k}\right)^k \le\binom{n}{k} \le\frac{n^k}{k!}}$.

9.2 DO: Prove: If $n\ge k \ge 1$ then     $\displaystyle{\binom{n}{k}\le \left(\frac{\eee n}{k}\right)^k}$.

9.3 CH (due Thu, May 12): Prove: If $n\ge k \ge 1$ then     $\displaystyle{\sum_{j=0}^k\binom{n}{j}\le \left(\frac{\eee n}{k}\right)^k}$.        (4 points)

9.4 REVIEW: Let $S(n,k)=\sum_{t=0}^{\infty}\binom{n}{tk}$. Then $$S(n,k) = \frac{1}{k}\sum_{j=0}^{k-1}(1+\zeta^j)^n$$ where $\zeta=\eee^{2\pi i/k}$ is the "first" complex $k$-th root of unity. (In fact this formula would work with any primitive $k$-th root of unity in place of $\zeta$.)

9.5 HW: Prove: $|S(n,3)-2^n/3| <1$. Your proof should be very short and elegant; use the formula from the preceding exercise.        (6 points)

9.6 DO: Review the notion of gcd. (Check instructor's online lecture notes.)

9.7 DO: A $k$-th root of unity is a complex number $z$ such that $z^k=1$. A primitive $k$-th root of unity is a $k$-th root of unity that is not an $\ell$-th root of unity for any $\ell< k$. A root of unity is a number that is a $k$-th root of unity for some $k\ge 1$.

9.8 DEF: The order of a complex root of unity is the smallest $k$ such that $z^k=1$. We denote tis quantity by $\ord(z)$.

9.9 DO: $z$ is a primitive $k$-th root of unity if and only if $\ord(z)=k$.

9.10 DO: Let $\ord(z)=k$. Prove: $z^m=1 \iff k\mid m$.

9.11 DO: Prove: $\ord(z^m)=\ord(z) \iff \gcd(m,\ord(z))=1$.

9.12 DO: Prove: The sum of the $n$-th roots of unity is 0 if $n\ge 2$ and 1 if $n=1$.

9.13 CH (due Tue, May 17): Let $\mu(n)$ denote the sum of the primitive $n$-th roots of unity. (a) Compute $\mu(n)$ for all $n\le 20$.   (b) Observe a pattern: given the prime factorization of $n$, give a simple rule to calculate $\mu(n)$   (c) Prove that the pattern holds for all $n$.        (3+2+5 points)

9.14 DEF (sunflower): A set system $A_1,\dots,A_m$ is a sunflower with $m$ petals if the $A_i$ are distinct and $(\forall i\neq j)(A_i\cap A_j=K)$ where $K=\bigcap_{i=1}^m A_i$. We call $K$ the kernel of the sunflower and the sets $A_i\setminus K$ the petals. Note that the petals are disjoint.

9.15 HW (Erdös-Rado Sunflower Theorem): Let $A_1,\dots,A_m$ be distinct sets of size $|A_i|\le r$. Assume $m > (s-1)^r r!$. Prove: there is a sunflower with $s$ petals among the $A_i$.        (6 points)

9.16 OPEN PROBLEM (Erdös-Rado Sunflower Conjecture): Does there exist a constant $C$ such that the following is true: If $|A_i|\le r$ $(i=1,\dots,m)$ and $m > C^r$ then there is a sunflower with 3 petals among the $A_i$.

9.17 DEF: A matching in a hypegraph is a set of disjoint edges. Matching number: $\nu(\calH)$: max number of disjoint edges.

9.18 DEF: A cover or "hitting set" in a hypergraph $\calH=(V,\calE)$ is a subset $W\subseteq V$ that hits every edge, i.e., $(\forall E\in\calE)(W\cap E\neq\emptyset)$. Covering number ("hitting number") $\tau(\calH)$: the minimum size of a cover.

9.19 HW: Prove: (a) $\nu(\calH)\le \tau(\calH)$. (Do not use anything from the fractional concepts below.)     (b) If $\calH$ is $r$-uniform then $\tau(\calH)\le r\cdot\nu(\calH)$     (c) Show: $(\forall r\ge 2)(\forall \nu\ge 1)$ both (a) and (b) are tight.        (2+4+(1+5) points)

9.20 DEF: A fractional cover of a hypergraph $\calH=(V,\calE)$ is a function $f: V\to\rrr$ such that (i) $(\forall v\in V)(f(v)\ge 0)$; and (ii) $(\forall E\in\calE)(\sum_{v\in E} f(v)\ge 1)$. The value of the fractional cover is $\sum_{v\in V} f(v)$. The fractional covering number of $\calH$ is $\tau^* =$ min value of a fractional cover.

9.21 DO:   Prove: $\tau^* \le \tau$.

9.22 DEF: A fractional matching of a hypergraph $\calH=(V,\calE)$ is a function $g: \calE\to\rrr$ such that (i) $(\forall E\in\calE)(g(E)\ge 0)$; and (ii) $(\forall v\in V)(\sum_{E: v\in E} g(E)\le 1)$. The value of the fractional matching is $\sum_{E\in\calE} g(E)$. The fractional matching number of $\calH$ is $\nu^* =$ max value of a fractional matching.

9.23 DO: $\nu\le\nu^*$.

9.24 HW: Prove: $\nu^* \le \tau^*$.        (8 points)
(Therefore $\nu\le\nu^*\le\tau^*\le\tau$.)

9.25 FACT: $\nu^*=\tau^*$. This follows from the Linear Programming Duality Theorem.

9.26 HW: Find (a) $\nu$ (b) $\nu^*$ (c) $\tau^*$ (d) $\tau$ for a projective plane of order $n$. Your answers should be very simple expressions. Prove your answers. Do not use the Duality Theorem.        (1+3+3+7) points)

9.27 DO: Let $C_n$ denote the cycle (graph) of length $n$ (so $C_n$ has $n$ vertices and $n$ edges where $n\ge 3$). Observe that $\nu(C_n)=\lfloor n/2\rfloor$ and $\tau(C_n)=\lceil n/2\rceil$. Find $\nu^*(C_n)$ and $\tau^*(C_n)$. Prove your answers. Do not use the Duality Theorem.

8.1 FACT: Every nonempty regular bipartite graph has a perfect matching. (A matching in a graph is a set of pairwise disjoint edges. A perfect matching in a graph is matching that involves every vertex, so it consists of $n/2$ edges, where, as usual, $n$ denotes the number of vertices.)

8.2 HW: Use the FACT above to prove that every Latin rectangle can be completed to a Latin square. (For $k\le n$, a $k\times n$ Latin rectangle is a $k\times n$ matrix such that every entry is from the set $[n]$ and there is no repeated entry in any row or column. A "completion" of a $k\times n$ Latin square $A$ is an $n\times n$ Latin square $B$ of which the first $k$ rows constitute the matrix $A$.)        (6 points)

8.3 DO: find a nonempty regular graph with an even number of vertices that has no perfect matching.

8.4 DO: Give a one-line "AH-HA" proof of the inequality $n!/n^n > \eee^{-n}$ (for all $n\ge 1$). You cannot use Stirling's formula because it only gives results for "sufficiently large" $n$. Effective variants of Stirling's formula exist; do not use them, they won't give an AH-HA proof.

8.5 $L$-intersecting hypergraphs: Let $L=\{\ell_1,\dots,\ell_s\}$ be a set of nonnegative integers. The hypergraph $\calH=(V;A_1,\dots,A_s)$ is $L$-intersecting if $(\forall i\neq j)(|A_i\cap A_j|\in L)$.

8.6 THM (Ray-Chaudhuri -- Wilson Theorem): Let $\calH=(V;A_1,\dots,A_m)$ be an $r$-uniform, $L$-intersecting simple hypergraph where $|L|=s\le r\le n$. Then $m\le\binom{n}{s}$ (where, as usual, $n=|V|$). (Result by Dijen K. Ray-Chaudhuri and Richard M. Wilson, 1965). ("Simple" means there are no repeated edges.) (We outline a proof of this theorem in Ex. 8.11 below.)

8.7 DO: Prove that for every $n$ and $s$ with $s < n/2$ the bound in the R-W Theorem is tight.

8.8 Frankl-Wilson Theorem (1981) (nonuniform version of the R-W Theorem): Let $\calH=(V;A_1,\dots,A_m)$ be an $L$-intersecting simple hypergraph where $|L|=s$. Then $m\le\binom{n}{s}+\binom{n}{s-1}+\dots +\binom{n}{1}+\binom{n}{0}.$

8.9 REVIEW the proof given in class (LB, 1988): Arrange the edges in nonincreasing order: $|A_1|\ge |A_2|\ge \dots\ge |A_m|$. Let $v_i\in\rrr^n$ denote the incidence vector of $A_i$. Define the polynomial $f_i(x)$   $(x\in\rrr^n)$ as follows: $$ f_i(x)=\prod_{\ell_j<|A_i|}(x\cdot v_i-\ell_j).$$ Observe that $f_i(v_i)\neq 0$ and for $i< k$ we have $f_i(v_k)=0$ so these polynomials satisfy the "triangular condition." It follows by Ex. 7.3 that the polynomials $f_i$ are linearly independent; in fact, even their multilinearizations ${\wt{f_i}}$ are linearly independent. Therefore $m \le \dim Q$ where $Q$ denotes the space of multilinear polynomials of degree $\le s$ in $n$ variables. $\dim Q = \sum_{j=0}^s \binom{n}{j}$ by Ex. 7.4. Q.e.d.

8.10 DO: Where did the proof in the previous exercise use the ordering of the sets $A_i$?

8.11 DO: Let $x_1,\dots,x_n$ be variables and for $I\subseteq [n]$ let $X_I=\prod_{i\in I} x_i$. Let $1\le r\le n$. Prove that the polynomials $X_I\cdot(\sum_{i=1}^n x_i-r)$ for all $I\subseteq [n]$ satisfying $|I|< r$ are linearly independent. (Hint: Triangular condition.)

8.12 HW (due Tue, May 10): proof of the R--W Theorem. (Note: the sketch given in class was in error.) [Note, added 5-9 at 6:15pm: a further error was in the posted problem, see below.]    (a) Prove: Under the conditions of the Ray-Chaudhuri -- Wilson Theorem, the polynomials $X_I\cdot(\sum_{i=1}^n x_i-r)$ for $|I|\le s-1$ and the polynomials ${\wt f}_i$ together are linearly independent. ($X_I$ is defined in Ex. 8.11. You may use 8.11 without proof.)   (b) Infer the R-W Theorem.   (This proof is due to Alon-B-Suzuki, 1991.)
[The error in the previous posting was that the term $(\sum_{i=1}^n x_i-r)$ was omitted.]        (10+3 points)

8.13 DO: review the definition of the determinant as a sum of $n!$ terms: if $A\in M_n(\fff)$ (where $\fff$ is a field and $M_n(\fff)$ is the set of $n\times n$ matrices over $\fff$) then $$\det(A)=\sum_{\sigma\in S_n} \sgn(\sigma)\prod_{i=1}^n a_{i,\sigma(i)}.$$ (Here $S_n$ denotes the set of all permutations of $[n]$.) In particular, review the parity of permutations (even, odd); we say that $\sgn(\sigma)=1$ if $\sigma$ is an even permutation and $\sgn(\sigma)=-1$ if $\sigma$ is an odd permutation.

8.14 DEF: The permanent is defined by the same formula as the determinant but without the signs: $$\per(A)=\sum_{\sigma\in S_n} \prod_{i=1}^n a_{i,\sigma(i)}.$$

8.15 DO: Prove: (a) If we multiply a column of the matrix $A$ by $\lambda$ to obtain the matrix $A'$ then $\per(A')=\lambda\per(A)$. (b) $\per(\lambda A)=\lambda^n\per(A).$

8.16 DO: We write $I$ for the $n\times n$ identity matrix and $J$ for the $n\times n$ all-ones matrix (every entry is 1). Prove: $\per(I)=1$ and $\per(J)=n!$.

8.17 DEF: A matrix $A=(a_{ij})\in M_n(\rrr)$ is stochastic if every row is a probability distribution, i.e., (i)   $(\forall i,j)(a_{ij}\ge 0)$ and (ii)   $(\forall i)(\sum_j a_{ij}=1)$ (each row sum is 1). The matrix $A$ is doubly stochastic if $A$ as well as its transpose $A^T$ are stochastic, i.e., in addition to (i) and (ii) we also have (iii)   $(\forall j)(\sum_j a_{ij}=1)$ (each column sum is 1). Examples: $I$ and $(1/n)J$ are doubly stochastic. Note that $\per((1/n)J)=n!/n^n > \eee^{-n}$.

8.18 DO: Prove: If $A$ is stochastic then $\per A \le 1$.

8.19 THM (The Permanent Inequality) (Falikman and Egorychev, 1976): If $A$ is doubly stochastic then $\per(A)\ge n!/n^n$.
This is a major result; for decades it was known as the Van der Waerden Conjecture. For an elementary proof see the monograph by Van Lint and Wilson.

8.20 DO: Let $a_n = \binom{2n}{n}$. Prove: $\lim{a_{n+1}/a_n}=4$. Give a very simple direct proof; do not use Stirling's formula.

8.21 DO: Prove: $\sum_{j=0}^s \binom{n+j-1}{j}=\binom{n+s}{s}$.

6.1 REVIEW: Recall the Erdös--Szekeres Theorem (1934): In any sequence of $k\ell+1$ real numbers, either there is an increasing subsequence of length $k+1$ or there is a non-increasing subsequence of length $\ell+1$. (Paul Erdös and George Szekeres were undergraduates when they found this.) Review proof via Pigeon Hole priniciple.

6.2 DO: Show that the Erdös--Szekeres Theorem is tight: For every $k,\ell\ge 1$ find a sequence of $k\ell$ numbers with no increasing subsequence of length $k+1$ and no non-increasing subsequence of length $\ell+1$.

6.3 DO (Erdös--Szekeres upgraded): Given a sequence $\va=(a_1,\dots,a_n)$ of numbers, let $\omega(\va)$ denote the length of the longest increasing subsequence and $\chi(\va)$ the minumum number of nonincreasing subsequences into which $\va$ can be divided.
(a) Prove: $\omega(\va)\le \chi(\va)$.
(b) Prove: $\omega(\va) = \chi(\va)$.
(c) Derive the Erdös--Szekeres Theorem (Problem 6.1) from part (b).
[The following explanation was updated 4-24 5pm.] Note that part (b) provides a "good characterization" of the quantities $\omega(\va)$ and $\chi(\va)$: if somebody claims that say $\omega(\va)=153$ then they should be able to produce a short and convincing proof of this statement: just display an increasing sequence of length 153 and a partition of the sequence into 153 nondecreasing subsequences. (Why does this prove, simultaneously, that both of these are optimal?)

The length of this proof is $O(n)$ where $n$ is the length of the sequence, far shorter than examining all increasing subsequences. Note that we have made no statement about the length of time it takes to find such proofs.

(d) Find an elegant and efficient algorithm to determine the value $\omega(\va)$ (and thereby of $\chi(\va)$).

(e) For a graph $G$ let $\omega(G)$ denote its clique number (size of largest complete subgraph). Note that $\chi(G)\ge\omega(G)$. Find the smallest graph for which $\chi(G)>\omega(G)$.

(f) Given a sequence $\va$, give a simple construction of a graph $G(\va)$ such that $\omega(\va)=\omega(G(\va))$ and $\chi(\va)=\chi(G(\va))$. The graph you constructed will be called the comparability graph of $\va$.
(g) A graph $G$ is called a perfect graph if $\omega(H)=\chi(H)$ for all induced subgraphs $H$ of $G$. (For the def of "induced subgraph," see instructor's online lecture notes.) Prove that comparability graphs of sequences are perfect.

6.4 REVIEW: generalized Fisher inequality: Let $\lambda\ge 1$. Let $\calH=(V;A_1,\dots,A_m)$ be a hypergraph without multiple edges such that for all $i\neq j$ we have $|A_i\cap A_j|=\lambda$. Then $m\le n$. (The special case with $\lambda=1$ is called the Erdös-DeBruijn theorem.) -- We proved this result in class by showing that the incidence vectors of the edges are linearly independent. Review the proof.

6.5 DO: We actually proved the linear independence of the incidence vectors only under the assumption $(\forall i)(|A_i|>\lambda)$. Prove that linear independence holds even without this assumption -- all we need to assume is $m\ge 2$. Show that the case we did not cover is trivial.

6.6 DEF: The next sequence of linear algebra exercises will prepare for a very elegant alternative proof of linear independence. We say that a $k\times\ell$ matrix has full row rank if its rank is $k$. A square matrix has full rank if it has full row rank, or, equivalently, full column rank. NOTATION:   $M_k(\fff)$ denotes the set of $k\times k$ (square) matrices over the field $\fff$.

6.7 DO: Let $A$ be a $k\times \ell$ matrix and $B$ an $\ell\times r$ matrix. Prove: $\rank(AB)\le\min\{\rank(A),\rank(B)\}$.

6.8 DO: The transpose of a $k\times \ell$ matrix $A=(a_{ij})$ is the $\ell\times k$ matrix $A^T$ whose $(i,j)$ entry is $a_{ji}$. A matrix $A$ is symmetric if $A=A^T$. A symmetric matrix is necessarily a square matrix.
Prove: (a) $(AB)^T=B^TA^T$.   (b) $A^TA$ is symmetric.

6.9 DO: Prove: (a) Prove: $\rank(AA^T)\le \rank(A)$ (over all fields).
(b) Prove: over $\rrr$ we have $\rank(AA^T)= \rank(A)$.
(c) For every prime $p$ show that (b) is false over $\fff_p$.

6.10. DO (linear algebra review): Let $A \in M_k(\fff)$. Prove that the following statements are equivalent:
(a) $A$ has full rank.
(b) The system $Ax=0$ of homogeneous linear equations has no nontrivial solution. (Here $x=(x_1,\dots,x_k)^T$ is a column vector of unknowns.) (In other words, 0 is not an eigenvalue of $A$.)
(c) $A$ is non-singular, i.e., its determinant is nonzero.

6.11 DO: Let $A\in M_k(\rrr)$. The quadratic form associated with $A$ is the function $Q_A : \rrr^k\to\rrr$ defined by $Q_A(x)=x^TAx$. Show: if $A=(a_{ij})$ and $x=(x_1,\dots,x_k)^T$ then $Q_A(x)=\sum_i \sum_j a_{ij}x_i x_j$.

6.12 DO: Prove: for every $A\in M_k(\rrr)$ there is a unique symmetric matrix $B\in M_k(\rrr)$ such that $Q_A=Q_B$.

6.13 HW: We say that the symmetric real matrix $A\in M_k(\rrr)$ is positive semidefinite if $(\forall x\in \rrr^k)(Q_A(x)\ge 0)$. Prove: the $k\times k$ all-ones matrix $J_k$ (every entry is equal to 1) is positive semidefinite.        (5 points)

6.14 HW: We say that the symmetric real matrix $A$ is positive definite if $(\forall x\neq 0)(Q_A(x)> 0)$. Let $D(a_1,\dots,a_k)$ denote the $k\times k$ diagonal matrix $D=(d_{ij})$ where the $i$-th diagonal entry is $d_{ii}=a_i$; all off-diagonal entries are zero: $(\forall i\neq j)(d_{ij}=0$. Prove: the $k\times k$ real diagonal matrix is positive definite if and only if all diagonal entries are positive.        (3 points)

6.15 DO: Let $A, B\in M_k(\rrr)$ be symmetric real matrices. Prove: If $A$ is positive definite and $B$ is positive semidefinite then $A+B$ is positive definite.

6.16 HW: Prove: If $A$ is a positive definite symmetric real matrix then $A$ is nonsingular. (You may use the DO exercises above.)        (3 points)

6.17 HW (alternative proof of the Generalized Fisher Inequality): Let $\lambda\ge 1$ and $\calH=(V;A_1,\dots,A_m)$ be as in the Generalized Fisher Inequality (Problem 6.4). Let $k_i=|A_i|$; assume $(\forall i)(k_i >\lambda)$. Let $M$ be the $m\times n$ incidence matrix of $\calH$ (the rows are the incidence vectors of the edges). We need to prove that the rows are linearly independent; in other words, we need to show that $M$ has full row-rank.
(a) Prove that it suffices to show that the symmetric $m\times m$ matrix $B=MM^T$ is nonsingular.
(b) Compute $B=MM^T$ (state its $(i,j)$ entry $b_{ij}$).
(c) Prove that $B$ is positive definite. Your proof should be just one line, based on exercises above.
(Note that (c) completes the proof because positive definite $\implies$ nonsingular. Note also the elegance of the proof; it involves no calculation.)        (4+5+5 points)

6.18 CH (due Tuesday, May 3): Let $\calH=(V;A_1,\dots,A_m)$ be a hypergraph satisfying the condition $(\forall i\neq j)(|A_i\cap A_j|=1)$ (Erdös-DeBruijn situation). Suppose $(\forall i)(|A_i|\neq 1)$. Suppose futher that $\calH$ is extremal, i.e., $m=n$. Prove: $\calH$ is a possibly degenerate finite projective plane.        (9 points)

6.19 DO: Prove: If $n\ge 1$ then the number of even subsets of an $n$-set is $2^{n-1}$. (An "$n$-set" is a set of $n$ elements. An even subset is a subset with an even number of elements.) Give two proofs: a bijective proof (construct a simple bijection between the set of even subsets and the set of odd subsets); and an algebra proof (use the Binomial Theorem).

6.20 DO: Recall that Eventown is a hypergraph $\calH=(V;A_1,\dots,A_m)$ without repeated edges such that $(\forall i,j)(|A_i\cap A_j|$ is even$)$. (This includes the condition that all the $|A_i|$ are even.) Construct an Eventown hypergraph with $m = 2^{\lfloor n/2\rfloor}$ edges. Hint: "married couples solution": pair up the vertices.

6.21 REWARD PROBLEM ("Eventown Theorem" (Berlekamp)): In Eventown, $m\le 2^{\lfloor n/2\rfloor}$ (the "married couples" solution is optimal).

6.22 CH (due Tue, May 3): Every maximal Eventown hypergraph is maximum.        (6 points)

6.23 HW (due Thu, April 28) Prove that there exist non-isomorphic maximum Eventown hypergraphs (i.e., Eventown hypergraphs that have $m = 2^{\lfloor n/2\rfloor}$ edges but are not isomorphic to the "married couples" solution). You may use the preceding challenge problem without proof; based on that problem, your solution should be very simple (just a few lines).        (7 points)

6.24 REWARD PROBLEM ("Oddtown Theorem" (Berlekamp)). Recall that Oddtown is a hypergraph $\calH=(V;A_1,\dots,A_m)$ such that each $|A_i|$ is odd and each $|A_i\cap A_j|$ $(i\neq j)$ is even. Prove: under these conditions, $m\le n$.

6.25 DO: For every $n\ge 1$, find extremal solutions to Oddtown (Oddtown hypergraphs that satisfy $m=n$).

6.26 DO: Show that for every $n\ge 2$ there are maximal Oddtown hypergraphs with very few ($m\le 2$) edges.

6.27 DO: review complex numbers and complex $n$-th roots of unity. Prove that for $n\ge 2$ the sum of the $n$-th roots of unity is zero.

6.28 HW (due Tue, May 3): For every fixed $k$ find a closed-form expression for the sum $\displaystyle{S(n,k)=\sum_{i=0}^{\infty}\binom{n}{ik}}$. (Note that this is actually a finite sum: if $r>n$ is an integer then $\binom{n}{r}=0$.) Here "closed form for every fixed $k$" means that you may have a sum of which the number of terms depends on $k$ but no sum of which the number of terms depends on $n$. Your solution should involve complex $k$-th roots of unity. Hint: apply the binomial theorem to $(1+x)^n$ and substitute $k$-th roots of unity for $x$.        (8 points)

6.29 CH (due Tue, May 10): Let $A_1,\dots,A_m$ be infinite arithmetic progressions of nonnegative integers; let $d_i$ denote the increment of $A_i$ (difference of consecutive members). Suppose the $A_i$ are pairwise disjoint and their union is the set of all nonnegative integers. Prove: if $m\ge 2$ then two of the increments must be equal. Hint: generating functions and complex roots of unity.        (7 points)

5.1 DO:       $\displaystyle{\frac{\binom{n}{k+1}}{\binom{n}{k}}= \frac{n-k}{k+1}}$

5.2 DO:       $\binom{2n}{n}-\binom{2n}{n-1}=\frac{1}{n+1}\binom{2n}{n}$. Note in particular that $n+1$ always divides $\binom{2n}{n}$. The quotient $\frac{1}{n+1}\binom{2n}{n}$ is called the $n$-th Catalan number and was discussed in class as the number of rooted binary trees with $n$ vertices. This Catalan numbers also count several other classes of interesting combinatorial objects, including the proper parenthesizations of a product of $n$ terms and the number of triangulations of a convex $n$-gon.

5.3 REVIEW: The probability that the drunkard, starting from zero, gets back to zero in $2n$ steps for the first time, is $$\frac{\binom{2n-2}{n-1}}{n\cdot 2^{2n-1}}.$$ Proof: via the Reflection principle for simple random walks on the integers.
(Note: At the end of class I gave this formula with two errors:
(1) instead of $\binom{2n-2}{n-1}$ I wrote $\binom{2n}{n}$;
(2) instead of $2^{2n-1}$ in the denominator I wrote $2^{2n}$.
The first of these was a copying error and does not affect the asymptotics. The second missed a factor of 2 corresponding to the arbitrary choice of the drunkard's first step, so only $2n-1$ steps remain.)

5.4 DO:       $\displaystyle{\frac{\binom{2n}{n}}{2^{2n}}\sim \frac{1}{\sqrt{\pi n}}}$

5.5 HW: Compute the expected number of steps for the drunkard to arrive back home for the first time.   (At the end of class I erroneously added the word "asymptotically" to this question. The answer you need to compute is not a function of $n$ so this statement makes no sense. What I had in mind was that you need to asymptotically evaluate the expression in problem 5.3 to get the simple answer. Your solution should be just 2 or 3 lines.)        (7 points)

5.6 HW (due Tue, Apr 26): Suppose our drunkard has two homes, one at zero and the other at $n$. The drunkard starts at $x$ where $0\le x\le n$. Prove: the expected number of steps for the drunkard to reach one of his homes is $x(n-x)$.        (15 points)

5.7 DO (due Tue, Apr 26): By Newton's binomial theorem, the coefficient of $x^n$ in the power series expansion of $(1-x)^{-k}$ is $(-1)^n\binom{-k}{n}$. Give a closed-form expression of this coefficient using an ordinary binomial coefficient (of the form $\binom{r}{s}$ where $r\ge s \ge 0$).

5.8 DO (due Tue, Apr 26): Let $f(x)=\sum_{n=0}^{\infty} a_n x^n$ be the generating function of the sequence $a_0,a_1,\dots$. Suppose $f(x)$ has the closed-form expression $\displaystyle{f(x) = \frac{p(x)}{(1-x)^k}}$ where $p$ is a polynomial. Assume $p(1)\neq 0$. Prove: $a_n \sim cn^k$ for some constant $c$. (In this asymptotic equality, $k$ is fixed and $n\to\infty$.) Express $c$ as a function of $k$ and the polynomial $p$. Your expression should be very simple, fewer than ten symbols.

5.9 DO (due Tue, Apr 26): By Newton's binomial theorem, the coefficient of $x^n$ in the power series expansion of $\displaystyle{\frac{1}{\sqrt{1-x}}}$ is $e_n=(-1)^n\binom{-1/2}{n}$.     (a) Give a closed-form expression of this coefficient using an ordinary binomial coefficient.     (b) Asymptotically evaluate $e_n$ in the form $e_n \sim a n^b c^n$ where $a,b,c$ are constants. Determine $a,b,c$.

5.10 DO (due Tue, Apr 26): Consider the sequence $\{c_n\}$ defined by the recurrence $c_0=0$, $c_1=1$, $c_n=5c_{n-1}-6c_{n-2}$.    (a) Find a closed-form expression of the generating function $g(n) = \sum_{n=0}^{\infty} c_n x^n$.    (b) Find an explicit closed-form expression for $c_n$, similar to Binet's formula for the Fibonacci numbers.

5.11 DO: Prove: If $a_n,b_n \to\infty$ and $a_n = \Theta(b_n)$ then $\ln a_n \sim \ln b_n$.

5.12 DO: (due Tue, Apr 26) (integer partitions): Let $p(n)$ denote the number of ways $n$ can be written as the sum of positive integers in nonincreasing order: $n=x_1+\dots+x_k$ where $k$ is also variable and $x_1\ge x_2\ge\dots\ge x_k\ge 1$. For instance, $n=5$ can be written as $5=4+1=3+2=3+1+1=2+2+1=2+1+1+1+1=1+1+1+1+1+1$ so $p(5)=7$. In other words, if $k_i$ is the number of times the number $i$ occurs in this sum, then we have $n=\sum_{i=1}^n ik_i$; we need to find the number of solution to this equation in $k_i\ge 0$. This is the number of Young tableaux mentioned in class. The following remarkable asymptotic formula holds (Hardy-Ramanujan formula, 1918): $$ p(n) \sim \frac{1}{4n\sqrt{3}}\eee^{\pi\sqrt{2n/3}} .$$ (a) Derive from the Hardy-Ramanujan formula that   $\ln p(n) \sim \pi\sqrt{2n/3}$.
The rest of this exercise is review from class. Using generating functions, we give a one-page elementary proof of the surprisingly accurate upper bound $$ p(n) < \eee^{\pi\sqrt{2n/3}} .$$ It is remarkable that such a simple proof produces the exact exponent.
Below we always assume $0 < x < 1$.
(b) Let $G(x)=\sum_{n=0}^{\infty} p(n)x^n$ be the generating function of the sequence $\{p(n)\}$. Prove: $\displaystyle{G(x) = \prod_{k=1}^{\infty}\frac{1}{1-x^k}}$.
(c) Infer from this product expansion that $\displaystyle{p(n) < \frac{1}{x^n}\prod_{k=1}^{\infty}\frac{1}{1-x^k}}.$
(d) Next, take the logarithm of each side and use the power-series expansion of $-\ln(1-y)$ to infer that $$ \ln p(n) = -n\ln x +\sum_{j=1}^{\infty}\frac{1}{j}\sum_{k=1}^n x^{jk} < -n\ln x + \sum_{j=1}^{\infty}\frac{1}{j}\frac{x^j}{1-x^j}. $$ (e) Prove: $1-x^j > (1-x)jx^{j-1}$
(f) Combine the previous two items to obtain $$\ln p(n) < -n\ln x + \frac{x}{1-x}\sum_{j=1}^{\infty}\frac{1}{j^2}= -n\ln x + \frac{\pi^2}{6}\frac{x}{1-x}$$ using the fact that $\sum_{j=1}^{\infty} 1/j^2=\pi^2/6$.
(g) Now set $u = x/(1-x)$, so $x = u/(1+u)$ $(0< u< \infty)$ and use the inequality $\ln(1+z)\le z$ (true for all $z > -1$) to obtain $\displaystyle{p(n) < n \ln(1+1/u) +(\pi^2/6)u < (n/u) + (\pi^2/6)u}$. Finally set $u=\sqrt{6n}/\pi$ (by calculus, this quantity maximizes the right-hand side in the preceding inequality) and conclude $\ln p(n) < \pi\sqrt{2n/3}$, as advertised.
This beautiful proof, outlined in class, is from the highly recommended Matoušek - Nešetříl text (click "Course home > Texts" on the banner), Section 10.7 ("Integer partitions") in the first edition. That section also includes a proof of the indentity $\sum_{j=1}^{\infty} 1/j^2=\pi^2/6$.

ADDITIONAL MATERIAL FROM April 19 class plus more challenge problems

5.13 NOTATION: $\aut(\calH)$ denotes the automorphism group of the hypergraph $\calH=(V,\calE)$, i.e., all permutations of of $V$ that map edges to edges. $\aut(\calH)$ is a subgroup of the symmertic group $\sym(V)$ consisting of all permutations of the set $V$.

5.14 DO: Prove: the number of automorphisms of the Fano plane is 168 (the number of hours in a week).

5.15 DEFINITION: A permutation group $G\le\sym(V)$ is transitive of for every $(u,v\in V)(\exists \sigma\in G)(\sigma(u)=v)$, i.e., all elements of $V$ are equivalent under the action of $G$. We say that a hypergraph $\calH$ is vertex-transitive if $\aut(\calH)$ is a transitive group.

5.16 DO: Prove: if $\calP$ is a Galois plane then $\aut(\calP)$ is transitive.

5.17 DO: The $\set_d$ hypergraph is vertex-transitive.

5.18 DO: Observe: if a hypergraph is vertex-transitive then it is regular. Prove that the converse does not hold even for graphs. Find the smallest graph that is regular but not vertex-transitive.

5.19 DO: The Platonic solids, as graphs, are vertex-transitive, edge-transitive, and in fact flag-transitive.

5.20 CH (due Tue, May 3): (Mario Szegedy, our former CS PhD student): Recall that $\alpha(\calH)\chi(\calH)\ge n$. Prove that for vertex-transitive hypergraphs this bound is nearly tight, namely, if $\calH$ is vertex transitive then $\alpha(\calH)\chi(\calH) < n (1+\ln n)$.        (9 points)

5.21 DO (due Tue, April 26): The Petersen graph is a connected vertex-transitive graph that is not Hamiltonian.

5.22 CONJECTURE. Fact: only four connected graphs are known that are vertex-transitive and non-Hamiltonian. Your instructor conjectures that there are infinitely many; in fact, that there exists a constant $c > 0$ and infinitely many connected vertex-transitive graphs that have no cycle, and not even a path, longer than $(1-c)n$. (Note: The latter conjecture strongly disputes L. Lovász's conjecture that every connected vertex-transitive graph has a Hamilton path. No counterexample to this conjecture is known.)

5.23 CH (longest cycle, due Tue, May 3): (L.B., 1979) Prove: in a connected, vertex-transitive graph the longest cycle has length $ > \sqrt{n}$.    You may use a previous challenge problem.        (5 points)

Attention. All challenge problems assigned prior to this problem set expire on Tuesday, April 19.

Reminder. HW #3.9 is also due Tuesday, April 12.

4.1 DO: Study the card game "SET" from web sources.

4.2 DEF: We define the $d$-dimensional $\calset_d$ hypergraph as follows. The vertex set is $\fff_3^d=\{(x_1,\ldots,x_d)\mid x_i\in\mathbb{F}_3\}$ so there are $n=3^d$ vertices. (In the actual cardgame we have $d=4$ so there are 81 cards.) The set of edges is $\set_d= \{\{\ul{x},\ul{y},\ul{z}\}\mid\ul{x}+\ul{y}+\ul{z}=\ul{0},\text{ where $\ul{x},$ $\ul{y},$ $\ul{z}$ are distinct elements of } \fff_3^d\}$ .

4.3 HW: $\calset_d$ is a 3-uniform hypergraph. Show that it is regular and compute the degree of the vertices.        (4 points)

4.4 DEF (independent set of vertices): Let $\calH=(V;A_1,\ldots,A_m)$ be a hypergraph. We say that the subset $W\subseteq V$ is independent if $(\forall i)(A_i\not\subseteq W)$ (no edge is contained in $W$). The independence number of $\calH$ is $\alpha(\calH)=$ the size of largest independent set.

4.5 DO (Fekete's Lemma): We say that a sequence $\{a_n\}$ of positive numbers is supermultiplicative if $(\forall k,\ell \ge 1)(a_{k+\ell}\geq a_k a_{\ell})$. Prove: If $\{a_n\}$ is a super multiplicative sequence of positive numbers then $\exists\lim_{n\to\infty}\sqrt[n]{a_n}=\sup_n\{\sqrt[n]{a_n}\}.$ Note that in particular this means that for every $k$, the limit is $\ge a_k$.

4.6 HW: Prove that the sequence $\alpha_d:=\alpha(\calset_d)$ is supermultiplicative.        (6 points)

4.7 DO: Let $L = \lim\sqrt[d]{\alpha_d}$. This limit exists by Fekete's Lemma. Observe that $2^d\leq\alpha_d\leq 3^d$ and therefore $2\leq L\leq 3$.

4.8 HW: Prove: $L > 2$. You may use web sources about the actual SET game ($\calset_4$). Give the best lower bound on $L$ you can get.        (5 points)

4.9 Meshulam's Theorem.     $\displaystyle{\alpha_d \le \frac{2\cdot 3^d}{d}}$.
This is the best upper bound known for $\alpha_d$ for large $d$. The proof uses the character theory of finite abelian groups.

4.10 OPEN QUESTION:     Is $L<3$ ?

4.11 DEF (Chromatic number). A legal coloring of a hypergraph $\calH=(V; A_1,\dots,A_m)$ is a function $f : V\to C$ where $C$ is a set of "colors," such that no edge is monochromatic (i.e., for each $i$, the function $f$ resticted to $A_i$ takes at least two values). We say that $\calH$ is $k$-colorable if a set of $|C|=k$ colors suffice for a legal coloring. The chromatic number $\chi(\calH)$ is the smallest $k$ for which $\calH$ is $k$-colorable. (Note that is $|A_|\le 1$ for some edge then no legal coloring exists; in this case we set $\chi(\calH)=\infty$.)

4.12 HW: (a) Let $\calH$ be a hypergraph with $n$ vertices. Prove:     $\alpha(\calH)\chi(\calH)\ge n$. (b) Prove: $\chi(\calset_d)\to\infty$. State an explicit lower bound. Use Meshulam's Theorem.        (5+4 points)

4.13 DO: (a) Let $\calH$ be a $k$-uniform hypergraph with $n$ vertices where $k\ge 2$. Prove:      $\displaystyle{\chi(\calH)\le \left\lceil\frac{n}{k-1}\right\rceil}$.
(b) Prove that this bound is tight for all $k\ge 2$ and $n\ge 1$. (For each $k\ge 2$ and $n\ge 1$ you need to find a $k$-uniform hypergraph on $n$ vertices that has chromatic number equal to the stated bound.)

4.14 DO: Prove: the chromatic number of the Fano plane is 3.

4.15 DO MAYBE: The Fano plane is the Galois plane of order 2. Find the chomatic number of the Galois planes of order 3 and 4.

4.16 DO (Union bound): Prove: if $A_1,\dots,A_m$ are events in a finite probability space then $P(\bigcup A_i)\le \sum P(A_i)$.

4.17 HW: (a) (Erdös) Let $\calH$ be a $k$-uniform hypergraph ($k\ge 2$) with $m$ edges. Prove: if $m\le 2^{k-1}$ then $\chi(\calH)\le 2$ ($\calH$ is 2-colorable). (Hint: use the union bound. For this hint to make sense, you first need to set up a probability space. Give a clear definition of your probability space.

State the size of your sample space. Give a clear definition of the events to which you apply the union bound.) (b) Prove: If $\calP$ is a projective plane of order $n\ge 5$ then $\chi(\calP)=2$.        (15+5 points)

4.18 STUDY the notion of independence of events from the online lecture notes.

4.19 DO: Find a small probability space and 3 events $A,B,C$ such that $P(A\cap B\cap C)=P(A)P(B)P(C)$ but $A, B, C$ are not independent.

4.20 DO: $A$ and $A$ are independent if and only if BLANK. Fill in the blank with a very simple statement about the event $A$.

4.21 DO: (a) Prove: If $A_1,\ldots, A_t$ are independent events then $A_1,\ldots, A_{t-1}$, $\bar{A_t}=\Omega\setminus A_t$ are also independent.
(b) Notation: $A^1=A$ and $A^{-1}=\bar{A}$. With this notation, prove: If $A_1,\dots, A_t$ are independent events then $A_1^{\epsilon_1},\dots,A_t^{\epsilon_t}$ are also independent, for all choices of $\epsilon_i\in\{1,-1\}$.

4.22 DO: Trivial events are those with probability 0 or 1. Prove: trivial events are independent of any collection of events, i.e., if $A_1,\dots,A_t$ are independent events and $B$ is a trivial event then $A_1,\dots,A_t, B$ are independent.

4.23 HW (due Tuesday, April 19): Prove: If there exist $t$ nontrivial independent events over the probability space $(\Omega,P)$ then $n\ge 2^t$ where $n=|\Omega|$.        (6 points)

4.24 DO: For every $t\ge 2$ find a probability space and $t$ events that are $(t-1)$-wise independent but not $t$-wise indepenent. Make your sample space as small as psoosible; prove the minimality of your sample space.

4.25 CH (due by Tuesday, April 26). Prove: If there exist $t$ nontrivial pairwise independent events over the probability space $(\Omega,P)$ then $n\ge t+1$ where $n=|\Omega|$.        (15 points)

4.26 CH (due by Tuesday, April 26). Show that the previous bound if tight infinitely often: For infinitely many values of $n$ find $n-1$ pairwise independent nontrivial events in the a uniform probability space with a sample space of size $n$.        (12 points)

4.27 DO: If $A,B,C$ are independent events then $A,B\cup C$ are independent.

4.28 DO (creating complex independent events from simpler ones): If the collection $\{A_i \mid i\in I\}$ of events is independent and we partition $I$ as $I=J_1\cup\dots\cup J_s$ (the $J_j$ are disjoint) and $B_j$ is a Boolean combination of the set $\{A_i \mid i\in J_j\}$ of events then $B_1,\dots,B_s$ are independent.

4.29 DEF (independence of random variables): We say that the random variables $X_1,X_2,\ldots,X_t$ over the probability space $(\Omega,P)$ are independent if $(\forall x_1,\ldots,x_t\in\rrr)(P(X_1=x_1,\ldots,X_t=x_t)= \prod_{i=1}^t P(X_i=x_i)$.

4.30 DO: If $X_1,\ldots,X_t$ are independent random variables then all their subsets are independent.

4.31 DO: When is the random variable $X$ independent of itself?

4.32 DO: Prove: the events $A_1,\ldots, A_t$ are independent $\iff$ their indicator variables $\vth_{A_1},\ldots,\vth_{A_t}$ are independent.

4.33 DO (Markov's Inequality): Prove (in one line): If $X$ is a nonnegative random variable then for all $a>0$ we have $$P(X\ge a)\le \frac{E(X)}{a}.$$

4.34 DEF (variance): $\var(X)=E((X-E(X))^2) = E(X^2)-E(X)^2$ by the linearity of expectation.

4.35 Corollary (Cauchy-Schwarz inequality): $E(X^2)\geq E(X)^2$

4.36 DO: Compare this with other forms of the Cauchy-Schwartz inequality.

4.37 DEF (Covariance) For random variables $X,Y$ we write $\cov(X,Y)=E(XY)-E(X)E(Y)$. Note: $\var(X)=\cov(X,X)$.

4.38 DO (Multiplicativity of expectation): Prove: (a) If $X,Y$ are independent random variables then $E(XY)=E(X)E(Y)$.
(b) If $X_1,\ldots, X_t$ are independent random variables then $E(\prod X_i)=\prod E(X_i)$.

4.39 HW (uncorrelated vs. independent): We say that the random variables $X,Y$ are uncorrelated if $E(XY)=E(X)E(Y)$, or equivalently, if $\cov(X,Y)=0$. By the previous exercise, if $X,Y$ are independent then they are uncorrelated. Show that the converse is false: construct a small probability space (meaning that the sample space is small) and two random vaiables that are uncorrelated by not independent.        (6 points)

4.40 REVIEW FROM CLASS (Variance of sum): Let $Y=X_1+\ldots+X_t$. Then $\var(Y)=\sum_i\sum_j\cov(X_i,X_j)=\sum_i\var(X_i)+ \sum_{i\neq j}\cov(X_i,X_j)=\sum_i\var(X_i)+2\sum_{i< j}\cov(X_i,X_j).$

4.41 DO: Corollary (Variance of sum of pairwise independent random variables) Let $Y=X_1+\ldots+X_t$ where the $X_i$ are pairwise independent. Then $\var(Y)=\sum_i \var(X_i)$.

4.42 DEF Random graphs -- the Erdös-Rényi Model ${\mathbf{G}}_{n,p}$: We fix $V$, $|V|=n$. For every pair of vertices, we make them adjacent with probability $p$, flippling independent biased coins for each of the $\binom{n}{2}$ pairs.

4.43 DO: Prove: in the ${\mathbf{G}}_{n,p}$ model, the expected number of edges is $p\binom{n}{2}$. (Hint: indicator variables, linearity of expectation)

4.44 DO: Let $T_n$ be the number of triangles in the uniform Erdös--Rényi model ${\mathbf G}_{n,1/2}$. (a) Find exact formula for $\var(T_n)$. Your answer should be a rather simple closed-form expression.
(b) Find the asymptotic value of $\var(T_n)$. Your answer should be of the form $\var(T_n)\sim a\cdot n^b,$; find the value of the constants $a,b$. (Hint: indicator variables, Ex. 4.40.)

Attention. All challenge problems assigned so far expire on Tuesday, April 19.

3.1 HW: Let $\calP=(P,L,I)$ be a projective plane ($P$ is the set of points, $L$ the set of lines, and $I\subset P\times L$ is the incidence relation among them). A polarity of $\calP$ is a bijection $f : P\to L$ such that for all pairs of points, $p,q\in P$, we have $(p,f(q))\in I$ if and only if $(q,f(p))\in I$. Prove: every Galois plane has a polarity.        (8 points)

3.2 DO: Prove: if $X$ is a random variable then $\min X \le E(X)\le \max X$.

3.3 DO: Prove the linearity of expectation.

3.4 REMEMBER: If $A$ is an event and $\vth_A$ is its indicator variable then $E(\vth_A) = P(A)$.

3.5 DO: Use the linearity of expectation to prove that the expected number of Heads in $n$ coin flips is $n/2$. Give a clear definition of the variables you introduce. (Hint: indicator variables.)

3.6 HW: Pick a random permutation $\sigma$ of the set $[n]=\{1,\dots,n\}$. (So the sample space has size $n!$.) Let $X$ denote the length of the $\sigma$-cycle through element 1. Prove: for all $k$ $(1\le k\le n$) we have $P(X=k)=1/n$.        (7 points)

3.7 HW: Let $Y_n$ denote the number of cycles in a random permutation of $n$ elements. Prove: $E(Y_n)\sim \ln n$.      (Recall that two sequences, $a_n$ and $b_n$, are called asymptotically equal if $\lim_{n\to\infty} a_n/b_n =1$.)        (12 points)

3.8 DO: Solve all probems of Quiz-1, inclduing the bonus problems.

3.9 HW (due Tuesday, April 12): Quiz-1 bonus problem 5(b).        (7 points)

2.1 DO: Prove: for every $n\ge 1$ there exists a Latin square of order $n$ (i.e., an $n\times n$ Latin square).

2.2 HW: Prove: for every odd $n\ge 3$ there exists a pair of orthogonal Latin squares of order $n$.        (5 points)

2.3 DO: Prove: if there exists a pair of orthogonal Latin squares of order $k$ and a pair of orthogonal Latin squares of order $\ell$ then there exists a pair of orthogonal Latin squares of order $k\ell$.

2.4 DO: Prove: if $n\ge 3$ and $n \not\equiv 2 \pmod{4}$ then there exists a pair of orthogonal Latin squares of order $n$.

2.5 STORY: Euler's "36 officers problem" (1782): no pair of orthogonal Latin squares of order 6 exists. Confirmed by Gaston Tarry, 1901. Yet for all other orders $n\equiv 2\pmod{4}$,  $n\ge 3$, there does exist a pair of orthogonal Latin squares of order $n$ (Bose--Shrikhande--Parker 1959).

2.6 DO: (a) There are at most $n-1$ pairwise orthogonal Latin squares of order $n$. (b) Exactly $n-1$ exist if and only if there exists a projective plane of order $n$.

2.7 DO: Prove the dual of a projective plane is a projective plane.

2.8 DO: Prove: the degenerate projective planes are exactly those seen in class (all but one of the points on one line)

2.9 DEF: collineation: permutation of the points of a projective plane that preserves collinearity (if 3 points are on a line, their images will also be on a line)

2.10 CH (Fundamental theorem of projective geometry): We say that 4 points in a projective plane are in general position if no 3 of them are on a line. Consider the projective geometry $PG(2,\fff)$ over a field $\fff$. Prove: If the points $p_1,\dots,p_4$ are in general position and the points $q_1,\dots,q_4$ are also in general position then there is a collineation $f$ such that $f(p_i)=q_i$.        (7 points)

2.11 HW: Let $\calH$ be a regular $k$-uniform hypergraph with $n$ vertices. A subset $R$ of the vertices is colored "red." Let $0\le \alpha\le 1$. Assume every edge contains at most $\alpha k$ red vertices. Prove: there are at most $\alpha n$ red vertices.        (6 points)

2.12 DO: Let us put down $n$ points in a circle. An arc of length $k$ means $k$ consecutive points along the circle. Prove: if $k\le n/2$ then at most $k$ arcs of length $k$ can be pairwise intersecting.

2.13 DO: Use the previous two exercises to prove the Erdös--Ko--Rado theorem.

2.14 DO: Let us call a hypergraph simple if it has no multiple edges. Prove: Every maximal intersecting simple hypergraph is maximum. In other words, if an intersecting simple hypergraph has fewer than $2^{n-1}$ edges then you can add an edge so the hypergraph remains simple and intersecting. (Maximum: has maximum number of edges under the given constraint. Maximal: cannot be extended -- if we add any edge, the constraint will be violated.)

2.15 Bruck--Ryser Theorem (1949) (stated without proof): If a projective plane of order $n$ exists and $n\equiv 1$ or $2 \pmod{4}$ then $n$ can be written as $n=a^2+b^2$. -- This result ruels out, for instance, projective planes of order 6 and 14 but does not rule out the existence of projective planes of order 10 or 12. -- The proof of the theorem is elementary linear algebra.

2.16 Theorem: There is no projective plane of order 10. (Clement W.H. Lam, L. H. Thiel, S. Swiercz, 1989, using results in coding theory and thousands of hours on a CRAY-1 supercomputer).

Unless otherwise stated, our hypergraphs have $n$ vertices and $m$ edges.

1.1 HW: Prove: if an intersecting hypergraph has no multiple edges (all edges are distinct) then $m\le 2^{n-1}$. (Your solution should be no more than three lines.) (A hypergraph is intersecting if every pair of edges shares at least one vertex.)     (4 points)

1.2 HW: Consider the following statement: "Every $k$-uniform intersecting hypergraph has at most $\binom{n-1}{k-1}$ edges." Construct a 2-parameter family of counterexamples to this statement, i.e., construct a set $B$ of "bad pairs" $(n,k)$ (where $1\le k \le n$) with the following properties:

• If $(n,k)$ is a bad pair then the statement above is false; give a very simple counterexample for each bad pair $(n,k)$.
• Bad pairs exist for all $n\ge 3$.
• As $n\to\infty$, the number of values of $k$ such that $(n,k)$ is bad should also go to infinity.

1.3 CH If a non-empty regular $k$-uniform hypergraph is intersecting then $k > \sqrt{n}$.     (10 points)

1.4 DO: Prove: a finite projective plane is

• regular
• uniform
• if it is $r$-regular and $k$-uniform the $r=k$
• letting $n:=k-1$ (so the projective plane is $(n+1)$-uniform and $(n+1)$-regular), the number of points (vertices) is $n^2+n+1$ and the number of lines (hyperedges) is the same. (Note that in this problem, $n$ does NOT mean the number of vertices.) The number $n$ is called the order of the plane. So, e.g., the Fano plane has order 2.

1.5 HW: For what values of the prime number $p$ is the set (ring) $\fff_p[i]=\{a+bi\mid a,b\in \fff_p\}$ of "complex numbers modulo $p$" a field? Here $\fff_p$ is the field of order $p$, i.e., the integers modulo $p$, and $i$ is a symbol and we interpret $i^2$ to be $-1$. You only need to check when this ring has zero-divisors. (A zero-divisor is non-zero element $z$ such that there is a non-zero element $w$ such that $zw=0$.) This is an exercise in experimental mathematics. First prove that $z=a+bi$ is a zero-divisor if an only if $a^2+b^2$ is divisible by $p$ while at least one of $a,b$ is not divisible by $p$. Next, prove that such a $z$ exists if and only if there is a integer $x$ such that $x^2\equiv -1 \pmod p$. Finally, experiment with small primes to see, modulo which primes does the congruence $x^2\equiv -1 \pmod p$ have a solution. List all primes $p<40$ in two columns according to whether there is a integer $x$ such that $x^2\equiv -1 \pmod p$ or not. Discover the very simple pattern that will allow you to decide, with no calculation, about any 50-digit prime, which column it belongs to. State this observed very simple pattern. Do not prove.     (12 points)