You may also use any result from the LinAlg book, except where the exercise is essentially identical with the result or a special case of the result from the book.

Material covered:   Lovász's 2nd proof of the uniform Bollobás Theorem: polynomial spaces (1977). Consequences: Bollobás skew version. Bollobás subspace vs. subspace version (wedge product method). (Lovász, 1977). Bollobás threshold version (Füredi, 1984). Bollobás subset vs. subspace version (polynomial method, Lovász 1977). Subspace in general position (generic subspace) with respect to a set of subspaces. Cover-critical graphs, Erdös--Gallai defect $\delta=2\tau - n$, Erdös--Gallai conjecture (classification of cover-critical graphs by defect), proved by Lovász (1978), using Bollobás sets vs. subspaces version. Geometric graphs (vertices: points in a vector space), min-rank cover.

Material covered:   The Capset problem: main lemma proved. Wedge product. Points in general position. Lovász's proof of the uniform Bollobás Theorem (1977).

Material covered:   The Capset problem: exponentially small upper bound on the density of an independent set in $\AG(n,3)$. Main Lemma stated (proof next time), otherwise proof completed.

16.20 NOTATION   Recall that $\fff[x_1,\dots,x_n]$ denotes the set of polynomials in $n$ variables, $x_1,\dots,x_n$, over the field $\fff$. This is an infinite-dimensional vector space over $\fff$.

16.25 Bonus ($n$-dim interpolation) (12+4 points, due March 7)   (a)   Let $\fff$ be a field and $D\subseteq \fff^n$ a finite subset. Let $f:D\to \fff$ be a function. Prove: there exists a polynomial $g\in\fff[x_1,\dots,x_n]$ such that for every $(\alpha_1,\dots,\alpha_n)\in D$ we have $g(\alpha_1,\dots,\alpha_n)=f(\alpha_1,\dots,\alpha_n)$.
  (b)   Prove: if $\fff=\fff_q$ (finite field of order $q$) then $g$ can be chosen so that the individual degree of $g$ in each variable is at most $q-1$.

16.33 DEF   Let $f:\Omega\to\fff$ be a function. The support of $f$ is the set $\{a\in\Omega\mid f(a)\neq 0\}$. We say that $f$ vanishes on the set $\Psi\subseteq \Omega$ if the restriction of $f$ to $\Psi$ is zero: $f|_{\Psi}=0$, i.e., $(\forall b\in\Psi)(f(b)=0)$.

16.36 DO   $f\in \fff^{\Omega}$ vanishes on the subset $\Psi\subseteq\Omega$ if and only if $\supp(f)\cap \Psi = \emptyset$.

16.40 ORD (9 points)   Let $U\le \fff[x_1,\dots,x_n]$ be a finite-dimensional subspace of the space of $n$-variate polynomials over the field $\fff$. Let $B\subseteq \fff^n$ be a finite set of vectors. Consider the set $U_B :=\{f\in U\mid (\forall b\in B)(f(b)=0\})$ (so $U_B$ is the set of polynomials in $U$ that vanish on $B$). Observe that this set is a subspace of $U$. Prove:   $\dim(U_B)\ge \dim(U) - |B|$.

16.43 NOTATION   Let $r\in\nnn_0$. Let $Q_{\fff}^r[x_1,\dots,x_n]$ denote the set of $n$-variate polynomials $f$ over $\fff$ in which each individual degree is $\deg_i(f)\le r$ (where $\deg_i(f)$ denotes the degree of $f$ in the variable $x_i$).

16.45 ORD (9 points)   Let $U\le \fff[x_1,\dots,x_n]$ be a finite-dimensional space of polynomials over the field $\fff$. If $\fff$ is finite, assume additionally that $U\le Q_{\fff}^{q-1}[x_1,\dots,x_n]$, where $q=|\fff|$. Prove that there exists a polynomial $f\in U$ such that $|\supp(f)|\ge \dim(U)$. You may use 16.60.
Note.   The second sentence (bound on individual degrees if $\fff$ is finite) and the last sentence (using 16.60) were added Feb 26 at 22:15.

16.53 DO   Note that $Q_{\fff}^r[x_1,\dots,x_n]$ (see Notation 16.43) is a vector space over $\fff$. Prove that its dimension is $(r+1)^n$.
Note.   Updated Feb 26, 15:15. Previously the incorrect value $q^{r+1}$ was stated.

16.55 DEF   The evaluation map $f\mapsto {\wt f}$ assigns to each polynomial $f\in\fff[x_1,\dots,x_n]$ a function ${\wt f}: \fff^n\to\fff$, by substituting scalars for the variables. Note that this is a vector space homomorphism (preserves linear combinations).

16.58 FACT   Let $q$ be a prime power. The elements of the finite field $\fff_q$ satisfy the equation $x^q=x$. So for the polynomial $f=x^q-x$, we have ${\wt f}=0$ (identically zero function).

16.60 Bonus (7 points)   Prove: the evaluation map $f\mapsto {\wt f}$ is invertible on $Q_{\fff_q}^{q-1}[x_1,\dots,x_n]$, so it gives a bijection between $Q_{\fff_q}^{q-1}[x_1,\dots,x_n]$ and $\fff_q^n$. In other words, for every function $g:\fff_q^n\to\fff_q$, there exists exactly one polynomial $f\in Q_{\fff_q}^{q-1}[x_1,\dots,x_n]$ such that ${\wt f}=g$.

16.65 ORD (11 points)   Let $q$ be a prime power. Consider the space $\fff_q[x_1,\dots,x_n]$. Let $P_d =\{f\in Q_{\fff_q}^{q-1} \mid \deg(f)\le d\}$. Observe that $P_d \le \fff_q[x_1,\dots,x_n]$ (subspace). Let $m_d = \dim(P_d)$. Let $0\le d < (q-1)n$. Prove:   $m_d + m_{(q-1)n-d-1} = q^n$.

16.70 Bonus (10 points)   Consider the space $\fff_3[x_1,\dots,x_n]$ of $n$-variate polynomials over $\fff_3$. Prove:   $m_{2n/3} < \eee^{-n/18}\cdot 3^n$.
Use the Bernstein--Hoeffding (Chernoff) bounds (PROB Theorem 7.12.7 on p.25). ($m_d$ is defined in the preceding exercise; take $q=3$ there.)

16.72 DEF   Let $A, B$ be finite sets, $A\subseteq B$, where $B\neq\emptyset$. We say that the density of $A$ in $B$ is $|A|/|B|$.

16.75 Capset Theorem (Croot--Lev--Pach--Ellenberg--Gijswijt, 2016)   Let $\alpha_n$ denote the independence number of the STS defined by the affine geometry $\AG(n,3)$. Then $\alpha_n < 3\cdot m_{2n/3}$ where $m_d$ is defined in 16.65, taking $q=3$.

16.77 Corollary   By 16.70 it follows that $\alpha_n/3^n < 3\cdot \eee^{-n/18}$, so the density of any indepedent set in $\AG(n,3)$ is exponentially small in terms of $n$ and therefore polynomially small in terms of $3^n$, the size of the space, i.e., it is less than $3^{-\epsilon n}$ for some constant $\epsilon > 0$.

Material covered:   Frankl--Wilson Theorem (non-uniform R-W theorem) proved by polynomial space method, multilinearization. Ray-Chaudhuri--Wilson Theorem proved by same method $+$ Blockhuis trick. Frankl--Wilson Theorem (modular R-W theorem) stated. Capset Theorem (Croot--Lev--Pach--Ellenberg--Gijswijt) stated.

15.10 STUDY   LinComb (Babai--Frankl book) Chapter 5.10 (nonuniform R-W Theorem) and Chapter 5.11 (R-W Theorem).

Material covered:   Bollobás's Theorem: uniform and non-uniform versions, connection to Sperner's Theorem. Proof of non-uniform version via Lubell's permutation method. Laplace expansion of determinant by a set of rows, related symmetric bilinear form. Wedge product.

14.10 STUDY   LinComb (Babai--Frankl book), Chapter 5.1 (Helly-type theorems for finite sets) and Chapter 6 (Tensor product methods).

Material covered:   Averaging argument. Erdös--Ko--Rado Theorem. Proof by Katona's circle method. Ray-Chaudhuri--Wilson Theorem (stated). Frankl--Wilson Theorem (non-uniform version of R--W) stated. 2-distance sets. Upper bound by the polynomial method (Larman--Rogers--Seidel).

13.20 STUDY LinComb (Babai--Frankl book), Chapter 1.2 ("Point sets in $\rrr^n$ with only two distances"), see link near the top of this file.

13.30 DEF   Let $(\Omega,P)$ be a finite probability space. Let $\calH=(\Omega,\calF)$ be a hypergraph. We shall say tha $\calH$ is probability-uniform if $P(F)$ is the same value for all $F\in\calF$. (This is not standard terminology.)

13.32 DEF (conditional expectation -- naive version)   Let $(\Omega,P)$ be a finite probability space and $X$ a random variable. For an event $A\subseteq\Omega$ with $P(A) \neq 0$, let us define $E(X\mid A)$, the "expected value of $X$ under condition $A$," by $$E(X\mid A) := \frac{\sum_{a\in A} X(a)P(a)}{P(A)}.$$ (So in this definition, the condition is an event. A more sophisticated concept of conditional expectation arises when the condition is a random variable $Y$, denoted $E(X\mid Y)$. This is not a number but a random variable, which we shall define later.)

13.35 ORD ("averaging argument," 11 points)   Let $(\Omega,P)$ be a finite probability space. Let $\calH=(\Omega,\calF)$ be a non-empty, regular, probability-uniform hypergraph, where the edges have non-zero probability. (Being "non-empty" means $\calF\neq\emptyset$.) Let $X$ be a random variable. Prove: $$ E(X) = \frac{\sum_{F\in\calF} E(X\mid F)}{|\calF|}\,.$$

13.37 DO   Under the assumptions of problem 13.35 we have   $\min_{F\in \calF} E(X\mid F) \le E(X) \le \max_{F\in\calF} E(X\mid F)\,.$

13.39 DEF (cyclic order)   Let $A$ be a set of $n$ elements. Consider the $n!$ linear orders $(a_0,a_1,\dots,a_{n-1})$ of $A$ (where $A=\{a_0,a_1,\dots,a_{n-1}\}$). We say that a cyclic shift of this linear order by $t$ units is the linear order $(a_t, a_{t+1},\dots,a_{t+n-1})$ where the subscripts are added modulo $n$. Being a cyclic shift is an equivalence relation on the set of linear orders; each equivalence class consists of $n$ linear orders. A cyclic order of $A$ is an equivalence class of linear orders under cyclic shifts. So there are $(n-1)!$ cyclic orders.

13.41 DEF (arc in cyclic order)   An arc of length $r$ (or an $r$-arc) in the cyclic order $(a_0,a_1,\dots,a_{n-1})$ of the set $A$ is a set of $r$ elements of $A$ that are consecutive when subcripts are incremented modulo $n$. (Here $r\le n$.)
Examples. Let $r=3$. The following are examples of 3-arcs: $\{a_3,a_4,a_5\}$, $\{a_{n-1},a_0,a_1\}$, $\{a_{n-2}, a_{n-1},a_0\}$.

13.44 ORD (13 points)   Let $r\le n/2$. Let $A_1,\dots,A_m$ be distinct $r$-arcs of a cyclic order of an $n$-set. Assume the $A_i$ are pairwise intersecting. Prove:   $m\le r$. Give a rigorous proof, without phrases like "clearly."
Note: Due to the complexity of this problem, its value was raised from 9 points to 13 points after the deadline.

13.50 NOTATION   For $v=(\alpha_1,\dots,\alpha_n)^T\in\rrr^n$ we write $\|v\|=\sqrt{\sum_{i=1}^n \alpha_i^2}$ to denote the standard Euclidean norm of $v$. The distance of $v$ and $w$ in $\rrr^n$ is $\|v-w\|$.

13.52 DEF   Let $S\subseteq\rrr^k$ and $T\subseteq\rrr^{\ell}$. An isometry from $S$ to $T$ is a bijection $f:S\to T$ that preserves distances, i.e., $(\forall v,w\in S)(\|v-w\|=\|f(v)-f(w)\|)$. We say that $S$ and $T$ are isometric if there exists an isometry $f:S\to T$.

13.54 DO   (a)   The inverse of an isometry is an isometry.   (b)   "Being isometric" is an equivalence relation among subsets of spaces $\rrr^n$ (where $n$ can vary among the subsets in question).

13.57 ORD (15 points)   Let $U$ be a $k$-dimensional affine subspace of $\rrr^n$. Prove: $U$ is isometric to $\rrr^k$.

13.60 DEF (affine independence)   Let $\fff$ be a field and $v_1,\dots,v_m\in\fff^n$. We say that $v_1,\dots,v_m\in\fff^n$ are affine independent if the following holds. Let $\alpha_1,\dots,\alpha_m\in \fff$. Assume $\sum_{i=1}^m\alpha_i =0$ and $\sum_{i=1}^m\alpha_i v_i =0$. Then $\alpha_1=\dots =\alpha_m=0$.

13.63 Bonus (12+5 points)   Prove that an isometry from a set $S\subset \rrr^k$ to a set $T\subset\rrr^{\ell}$   (a)   preserves affine independence (if $S$ is affine independent then so is $T$)   (b)   does not necessarily preserve linear independence: for every $m$, find isometric sets $S,T\in \rrr^m$ such that $|S|=|T|=m$ and $S$ is linearly independent but $T$ is not.

13.70 DEF  Let $s\in\nnn$. An $s$-distance set in $\rrr^n$ is a set $S\subset\rrr^n$ such that there exists a set $L\subset\rrr$ of size $|L|=s$ such that $(\forall v\neq w\in S)(\|v-w\|\in L)$ (the pairwise distances among points in $S$ take at most $s$ different values).

13.72 NOTATION  In the following sequence of exercises we write $m(s,n)$ to denote the maximum size of an $s$-distance set in $rrr^n$.

13.75 ORD (5+11 points)   Prove:   $m(1,n)=n+1$.
In words: you need to show that the maximum number of points in $\rrr^n$ at pairwise equal distances is $n+1$. -- Note that you need to prove two inequalities:   (a)   $m(1,n)\ge n+1$ and   (b)   $m(1,n)\le n+1$. Elegance counts.

13.77 ORD (8 points)   Prove:   $m(2,n) \ge \binom{n+1}{2}$.
In other words, you need to construct a set $\binom{n+1}{2}$ points in $\rrr^n$ with at most two pairwise distances. State the two distances you get.

13.80 Theorem (Larman--Rogers--Seidel, 1977)   $m(2,n)\le (n+1)(n+4)/2$.

13.82 STUDY the proof of this theorem (LinComb, Chapter 1.2).

13.90 DEF (multivariate polynomials)   A monomial in the variables $x_1,\dots, x_{\ell}$ is an expression of the form $f(x_1,\dots,x_{\ell})=\prod_{i=1}^{\ell} x_i^{k_i}$, where $k_i\in\nnn_0$ are non-negative integers. The degree of this monomial is $\deg(f)=k_1+\dots+k_{\ell}$. The exponent $k_i$ is the degree of $f$ in the variables $x_i$, denoted $\deg_i(f)=k_i$. We refer to the $k_i$ as the individual degrees. The monomial of degree zero is $1$.
A polynomial over the field $\fff$ in the variables $x_1,\dots,x_{\ell}$ is a linear combination of a finite number of monomials, with coefficients from $\fff$. The set of polynomials over $\fff$ in the variables $x_1,\dots,x_{\ell}$ is denoted $\fff[x_1,\dots,x_{\ell}]$. This is an infinite-dimensional vector space of which the monomials form a basis. For $d\in \nnn_0$, a polynomial of degree $\le d$ is a linear combination of monomials of degrees $\le d$. The empty linear combination of monomials is the zero polynomial, denoted $0$. By definition, $\deg(0)=-\infty$. The degree of a polynomial $g$ is the smallest $d$ such that $\deg(g)\le d$. The individual degrees of $g$ are defined analogously.
The polynomials of degree $\le d$ in variables $x_1,\dots,x_{\ell}$ is a vector space; we denote it $\fff^{\le d}[x_1,\dots,x_{\ell}]$. A homogeneous polynomial of degree $d$ is a linear combination of monomials of degree $d$. The zero polynomial counts as a homogeneous polynomial of degree $d$ for every $d\ge 0$ (even though its degree is $-\infty$) because it is the empty linear combination of monomials of degree $d$. The homogeneous polynomials of degree $d$ form a vector space; we denote this space $\hom_{\fff}^d(x_1,\dots,x_{\ell})$.

13.92 DO   Show: for $d\ge 0$, the degree of a polynomial $g$ is $d$ if it can be written as a linear combination $g=\sum_i \alpha_i f_i$ where none of the $\alpha_i$ is zero, the sum is not empty, and $d=\max_i \deg(f_i)$.

13.94 DO (there are no zero-divisors)   Let $g,h\in \fff[x_1,\dots,x_{\ell}]$. Prove: if $gh=0$ then $g=0$ or $h=0$.

13.96 DO   Let $g,h\in \fff[x_1,\dots,x_{\ell}]$. Prove:   (a)   $\deg(f+g)\le \max(\deg(f),\deg(g))$   (b)   $\deg(fg)=\deg(f)+\deg(g)$. These statements are true even if $f$ or $g$ or $f+g$ is the zero polynomial.

13.98 ORD (10 points)   Determine the dimension of the space $\fff^{\le d}[x_1,\dots,x_{\ell}]$ (polynomials of degree $\le d$ in $\ell$ variables). Your answer should be a simple closed-form expression (in the sense of PROB DEF 7.1.4) in terms of $\ell$ and $d$. Reason your answer.

13.100 ORD (9 points)   Determine the dimension of the space $\hom_{\fff}^d(x_1,\dots,x_{\ell})$ (homogeneous polynomials of degree $d$). Your answer should be a simple closed-form expression (in the sense of PROB DEF 7.1.4) in terms of $\ell$ and $d$. Reason your answer.

13.102 DEF   A multilinear monomial is a (possibly empty) product of distinct variables. In other words, every individual degree in a multilinear monomial is $\le 1$. A multilinear polynomial is a linear combination of multiplinear monomials.

13.104 ORD (8 points)   Determine the dimension of the space of multilinear polynomials of degree $\le d$ in $\ell$ variables. The answer will not be a closed-form expression but a simple sum of simple closed-form expressions. Reason your answer.

13.108 DEF   A univariate polynomial is a polynomial in 1 variable.

13.110 ORD (7 points)   Find a univariate polynomial $g$ of degree $17$ over $\fff_5$ such that for each $\alpha\in\fff_5$ we have $g(\alpha)=0$.

13.115 DO   Let $\fff$ be a field and $D\subseteq \fff^n$ a finite subset. Prove: there exists a nonzero polynomial $g\in\fff[x_1,\dots,x_n]$ such that for every $(\alpha_1,\dots,\alpha_n)\in D$ we have $g(\alpha_1,\dots,\alpha_n)=0$.
This problem was previously posted as a bonus problem by mistake. Downgraded 2-24 at 19:25.

Material covered:   Symmetric bilinear forms, orthogonality, linear independence. Euclidean spaces, Gram matrix. --- Chains, antichains in the powerset. Sperner's Theorem. The BLYM inequality. --- Additional reading (below): strong concentration inequalities and the Erdös--Rényi model of random $r$-uniform hypergraphs.

12.10 STUDY   LinAlg Chap 11 (Bilinear and quadratic forms) and Chap 19 (Euclidean spaces).

12.15 STUDY   PROB Section 7.12 (Strong concentration inequalities).

12.20 NOTATION (function space)   For sets $A, B$ recall the notation $B^A$ for the set of functions $f:A\to B$ with domain $A$ and codomain $B$.
In particular, the set $\fff^{\Omega}$ denotes the set of functions $f:\Omega\to\fff$.

12.22 DO   The function space $\fff^{\Omega}$ is a vector space of dimension $|\Omega|$ over the field $\fff$.

The following sequence of problems refers to a probability space $(\Omega, P)$ where $|\Omega|=n$. Note that $\rrr^{\Omega}$ is the space of random variables.

12.35 ORD (7 points)   Let $X_1,\dots,X_{\ell}$ be independent random variables and let $c_1,\dots,c_{\ell}\in\rrr$ be scalars. Prove:   the variables $Y_i=X_i+c_i$ $(i=1,\dots,\ell)$ are independent.
Refer to PROB Section 7.11 for the notion of independence of random variables.

12.38 DEF   We call the random variable $X$ centered if $E(X)=0$.

12.41 DO   Let $\cent$ denote the set of centered random variables. Prove:   $\cent$ is a subspace of $\rrr^{\Omega}$ and $\dim(\cent)=n-1$.

12.44 DO   Suppose there are no elementary events of probability zero in our sample space. Prove: the function $\langle X,Y\rangle := E(XY)$ is a positive definite inner product on the space $\rrr^{\Omega}$ of random variables.

12.50 Bonus (12+3 points)   (a)   Let $X_1,\dots,X_k$ be pairwise uncorrelated, not-almost-constant random variables. Prove: $n\ge k+1$, where $n$ is the size of the sample space.
(b)   Derive challenge problem 01.170 from this.

12.60 DEF (the Erdös--Rényi model of random $r$-uniform hypergraphs)   Let $0 < p < 1$. The Erdös--Rényi model of random $r$-uniform hypergraphs defines a probability distribution $\calG_r(n,p)$ on the set $\Omega(V,r)$ of $r$-uniform hypergraphs on a given set $V$ of $n$ vertices, so the size of the sample space is $|\Omega(V,r)|=2^N$ where $N=\binom{n}{r}$.
Under this distribution, for every $r$-uniform hypergraph $\calH = (V,\calF)\in\Omega(V,r)$ we have $P(\calH)=p^m(1-p)^{N-m}$ where $m = |\calF|$.

12.63 DO   (Continued) For $F\in\binom{V}{r}$, let $A_F$ denote the event that $F\in\calE$. Verify that
(a)   For each $F\in \binom{V}{r}$ we have $P(A_F)=p$, and
(b)   these $N$ events are independent.

12.66 DO (expected degree of a pair of points in a random 3-uniform hypergraph)   (Continued) We use the Erdös--Rényi model $\calG_3(n,p)$. We denote the set of vertices by $V_n$, so $|V_n|=n$.
For $x,y\in V$, $x\neq y$, let $\deg(x,y)$ denote the number of edges containing both $x$ and $y$. Prove: for all $x,y\in V_n$, $x\neq y$ we have $E(\deg(x,y))=p(n-2)$.

12.70 ORD (15 points, due Feb 20) (almost all 3-uniform hypergraphs are nearly regular)   (Continued) We continue to use the Erdös--Rényi model $\calG_3(n,p)$, with $V_n$ the set of vertices.
Prove that for any fixed $p$ $(0 < p < 1)$, "almost all" 3-uniform hypergraphs are nearly regular in the following sense.
Let $q_n$ denote the probability that for all $x, y\in V_n$ such that $x\neq y$, $$ |\deg(x,y) - p(n-2)| \le 2.1\sqrt{n\cdot\ln n}\,.$$ Prove that $q_n \to 1$ as $n\to\infty$ (while the value of $p$ is fixed).
Use PROB Theorem 7.12.7. (Do not use more advanced versions of this inequality.)
For a partial credit of 9 points, solve the problem for $p=1/2$.

12.80 DEF   We say that the sets $A$ and $B$ are comparable if $A\subseteq B$ or $B\subseteq A$. Let $\Omega$ be a set. A chain in $\calP(\Omega)$ (the pwerset of $\Omega$) is set of distinct, pairwise comparable sets: $A_1\subset A_2\subset\dots\subset A_k\subseteq\Omega$. An antichain is a set of pairwise incomparable sets. Antichains are also called Sperner families.

12.85 DO   Let $|\Omega|=n$.   (a)   Every maximal chain in $\calP(\Omega)$ is maximum and consists of $n+1$ sets.   (b)   The number of maximal chains in $\calP(\Omega)$ is $n!$.

12.90 DO   Prove:   If $0\le k \le n/2 -1$ then $\binom{n}{k} < \binom{n}{k+1}$. If $n/2 \le k \le n-1$ then $\binom{n}{k} > \binom{n}{k+1}$. In particular, for all $0\le k\le n$ where $k\notin\{\lfloor n/2\rfloor, \lceil n/2 \rceil\}$ we have $\binom{n}{k} < \binom{n}{\lfloor n/2\rfloor} = \binom{n}{\lceil n/2\rceil}.$

12.92 DO   We continue the notation $n=|\Omega|$.
(a)   Every uniform set system is an antichain.
(b)   For every $r$ $(0\le r\le n)$, the set $\binom{\Omega}{r}$ is a maximal antichain in $\calP(\Omega)$. In particular, not every maximal antichain is maximum.
(c)   The largest uniform antichains in $\calP(\Omega)$ are $\binom{\Omega}{\lfloor n/2\rfloor}$ and $\binom{\Omega}{\lceil n/2\rceil}$.
(d)   Not every antichain is uniform.

12.95 Sperner's Theorem   Let $\calF$ be a Sperner family (antichain) in $\calP(\Omega)$ where $|\Omega|=n$. Then $|\calF| \le \binom{n}{\lfloor n/2\rfloor}$.

12.97 Reward (chain cover)   Prove that there exist $m:=\binom{n}{\lfloor n/2\rfloor}$ chains $C_1,\dots,C_m$ in $\calP(\Omega)$ such that $\calP(\Omega)=\bigcup_{i=1}^m C_i$.

12.99 DO   Show that Sperner's Theorem immediately follows from the preceding exercise.

12.100 BLYM Inequality (Bollobás-Lubell-Yamamoto-Meshalkin)   Let $\calF\subset\calP(\Omega)$ be a Sperner family. Then $$ \sum_{A\in\calF}\frac{1}{\binom{n}{|A|}} \le 1\,.$$

12.102 ORD (8 points, due Feb 20)   Deduce Sperner's Theorem from the BLYM Inequality.

12.105 DO   Show that equality holds in the BLYM inequality if $\calF$ is a maximal uniform set system in $\calP(\Omega)$, i.e., $\calF = \binom{\Omega}{r}$ for some $0\le r\le n$.

12.107 Challenge   Prove that if equality holds in the BLYM Inequality then $\calF$ is a maximal uniform set system in $\calP(\Omega)$. (So this is "if and only if.")

12.110 DEF (prefixes of an ordered set)   Let $\Omega$ be a set of $n$ elements. Let $(a_1, a_2, \dots, a_n)$ be a linear ordering of $\Omega$. The prefixes of this linear ordering are the sets $\emptyset \subset \{a_1\} \subset \{a_1,a_2\} \subset \{a_1,a_2,a_3\} \subset\dots\subset \Omega$. The prefixes form a maximal chain in $\calP(\Omega)$.

12.112 Lubell's permutation method   Let $|\Omega|=n$ and let $\pi$ be a linear ordering of $\Omega$. Let $A\subseteq\Omega$. We say that $A$ and $\pi$ are compatible if $A$ is a prefix of $\pi$.
Let $S_n$ denote the set of linear orderings of $\Omega$ (so $|S_n|=n!$). Consider the uniform probability space on the sample space $S_n$.
Let $\calF=\{F_1,\dots,F_m\}$ be a Sperner family in $\calP(\Omega)$. Let $X(\pi)$ denote the number of elements of $\calF$ that are compatible with $\pi$. So $X$ is a random variable on our probability space.

12.114 DO (Lubell's method continued)   (a) $X\le 1$.   (This is where we use that $\calF$ is a Sperner fmily).
(b) $X=\sum_{i=1}^m Y_i$ where $Y_i$ is the indicator variable indicating the event $A_i$ that $F_i$ and $\pi$ are compatible.
(c) $\displaystyle{P(A_i) = \frac{1}{\binom{n}{|F_i|}}}\,.$   The reason is "by symmetry": $F_i$ could land in any $|F_i|$ positions in the random linear ordering with equal probability.
(d) Use the linearity of expectation to combine (a), (b), (c) to obtain the BLYM Inequality.
This completes the (second) proof of Sperner's Theorem.

12.118 Bonus (14 points, due Feb 20)   Let $|\Omega|=n$ and $\calF\subseteq\calP(\Omega)$. Assume every chain contained in $\calF$ has at most $s$ members. Prove that $|\calF|$ is not greater than the sum of the $s$ largest binomial coefficients of the form $\binom{n}{k}$.
Note: Due to the complexity of this problem, its value was raised from 10 points to 14 points after the deadline.

12.122 Bonus (15 points, due Feb 20) (subset sums)   Let $b$ be a real number and $a_1,\dots,a_n$ non-zero real numbers. Let $\calJ=\{I\subseteq [n] \mid \sum_{i\in I} a_i = b\}$. Prove:   $|\calJ|\le \binom{n}{\lfloor n/2\rfloor}$.
For a partial credit of 7 points, assume the $a_i$ are positive.

Material covered:   The SET cards. Estimating the minimum number of edges of a non-2-colorable $r$-uniform hypergraph: the Probabilistic Method; non-constructive proof of existence of certain objects. --- The standard dot product over an arbitrary field, the "perp" ($\perp$) operator, $\dim(U^{\perp})$, isotropic vector, totally isotropic subspace, maximum number of Eventown clubs.

11.10 TERMINOLOGY   A set system is a set of sets. This is the same as a hypergraph except we don't specify the set of vertices. We call the set system $r$-uniform if every set in the system has cardinality $r$.

11.12 DEF   A set system is a sunflower if the intersection of every pair of distinct sets in the system is equal to the intersection of all sets.
In other words, let $\calF=\{F_1,\dots,F_s\}$ be a set system and let $K=\bigcap_{k=1}^s F_k$. We say that $\calF$ is a sunflower if $(\forall i\neq j\in [s])(F_i\cap F_j = K)$. In this case we call $K$ the kernel of the sunflower and the sets $F_i\setminus K$ the petals. So here the number of petals is $s$.
Note that the petals are all distinct; one of them can be empty. Note that we permit the kernel to be empty.

11.15 ORD (10 points)   Let $r\ge 1$ and $s\ge 3$. Assume $m > r!(s-1)^r$. Let $\calH$ be an $r$-uniform hypergraph with $m$ edges. Prove: $\calH$ contains a sunflower with $s$ petals.

11.20 DEF   Let $\calF\subseteq\calP(V)$ be a set of subsets of the set $V$.
(a)   We say that $\calF$ is an ideal if $\calF$ is downward closed: if $E\subseteq F\in\calF$ then $E\in\calF$.
(b)   We say that $\calF$ is a filter if $\calF$ is upward closed: if $E\supseteq F\in\calF$ then $E\in\calF$.

11.25 Bonus (Daniel Kleitman's theorem) (22 points, due Feb 20) (DO NOT LOOK IT UP)   Prove: an ideal and a filter cannot be positively correlated (viewed as events in the uniform space on $\Omega:=\calP(V)$). In other words, if $\calE\subseteq\calP(V)$ is an ideal and $\calF\subseteq\calP(V)$ is a filter then $|\calE\cap\calF| \le 2^{-n}\cdot|\calE|\cdot|\calF|\,.$
Hint. Induction on $n$.

In the next sequence of exercises, $\fff$ is an arbitrary field. We think of the vectors in $\fff^n$ as column vectors.

11.30 DEF   For $x=(x_1,\dots,x_n)^T$ and $y=(y_1,\dots,y_n)^T \in \fff^n$, we write $\langle x,y\rangle$ to denote the standard dot product $\langle x,y\rangle = \sum_{i=1}^n x_iy_i = x^Ty$.

11.35 DEF   We say that the vectors $x,y\in\fff^n$ are perpendicular if $\langle x,y\rangle = 0$. Notation: $x\perp y$.

11.37 DO   Observe that being perpendicular is a symmetric relation:  $x\perp y \Rightarrow y\perp x$.

11.39 DEF   We say that the vector $x\in\fff^n$ is perpendiculat to the set $S\subseteq\fff^n$ if $(\forall y\in S)(x\perp y)$. Notation: $x\perp S$.
We say that the sets $S,T\subseteq \fff^n$ are perpendicular if $(\forall x\in S)(\forall y\in T)(x\perp y)$.

11.42 DO   Prove: for $S\subseteq \fff^n$ we have $S\subseteq (S^{\perp})^{\perp}$.

11.45 NOTATION   For $S\subseteq\fff^n$ we write $\span(S)$ to denote the span of $S$, i.e., the set of all linear combinations of finite subsets of $S$.

11.48 ORD (4 points)   Prove: if $S\perp T$ then $\span(S)\perp\span(T)$.

11.51 NOTATION   For $x\in\fff^n$ we write $x^{\perp} = \{y\in\fff^n\mid x\perp y\}$. For $S\subseteq\fff^n$ we write $S^{\perp} = \{y\in\fff^n\mid y\perp S\}$.

11.54 DO   If $S\subseteq\fff^n$ then $S^{\perp}=\bigcap_{x\in S} x^{\perp}$.

11.57 ORD (4 points)   Determine $\emptyset^{\perp}$. Reason your answer.

11.60 DO   If $S_i\subseteq\fff^n$ then $(\bigcup_i S_i)^{\perp}=\bigcap_i S_i^{\perp}$.

11.63 DO   If $S\subseteq\fff^n$ then $S^{\perp}\le \fff^n$ ($S^{\perp}$ is a subspace).

11.66 ORD (12 points)   If $U\le\fff^n$ then $\dim(U)+\dim(U^{\perp}) = n$.

11.69 ORD (7 points)   If $U\le\fff^n$ then $U = (U^{\perp})^{\perp}\,.$

11.72 DEF   We say that the vector $x\in\fff^n$ is isotropic if $x\neq 0$ and $x\perp x$. We say that the set $S\subseteq \fff^n$ is totally isotropic if $S\perp S$.
WARNING   This definition was updated Sat Feb 11 at 23:08. The condition $x\neq 0$ was added to the definition of an isotropic vector, so we don't consider 0 isotropic.

11.75 ORD (6 points)   If $U$ is a totally isotropic subspace of $\fff^n$ then  $\dim(U) \le \lfloor n/2\rfloor$.

11.78 FACT   If $q$ is a prime power and $q\equiv 1\pmod{4}$ then   $(\exists x\in\fff_q)(x^2+1=0)$.

11.81 ORD (8 points)   For every $n\ge 1$, show that there exists a totally isotropic subspace of dimension $\lfloor n/2\rfloor$ in $\fff^n$, assuming $\fff$ is one of the following fields:   $\fff_2$,   $\fff_q$ where $q\equiv 1\pmod{4}$,   $\ccc$.

11.83 DO   Let $\calH=([n],\calE)$ be a hypergraph. Let $I(\calE)$ denote the set of incidence vectors of $\calE$ over $\fff_2$. Prove:   $\calE$ is an Eventown system (Def 1.70) if and only if the set $I(\calE)$ is a totally isotropic set.

11.86 ORD (6 points: Eventown Theorem)   Let $\calE$ be a maximal Eventown system. Prove:   $I(\calE)$ is a totally isotropic subspace of $\fff_2^n$. Infer that $|\calE|\le 2^{\lfloor n/2\rfloor}$.

11.90 Bonus (16 points, due Feb 20)   Prove: every maximal Eventown system is maximum.
(This used to be a Challenge problem, 03.56; that classification has now expired.)

Material covered:   Number of Aces and Spades in poker hand are uncorrelared: the "by symmetry" argument. The Bell numbers: log-asymptotics. Recurrence, exponential generating function: differential equation, explicit formula, Dobinski's formula, toward asymptotics.

10.40 DEF   A partition of a set $\Omega$ is a division of $\Omega$ into disjoint non-empty subsets. Formally, a partition $\Pi=\{\Omega_1,\dots\Omega_k\}$ is a set of subsets such that
   (i)     $\Omega_i \neq\emptyset$
   (ii)    $\Omega_i\cap \Omega_j=\emptyset$ for all $i\neq j$
   (iii)   $\bigcup_{i=1}^k \Omega_i = \Omega$.

10.42 Examples   The set $[3]$ has 5 partitions:   (1) $\{\{1,2,3\}\}$   (2) $\{\{1,2\},\{3\}\}$   (3) $\{\{1,3\},\{2\}\}$   (4) $\{\{2,3\},\{1\}\}$   (5) $\{\{1\},\{2\},\{3\}\}$

10.45 DEF   The Bell number $B_n$ is the number of of partitions of $[n]$.
The first few values: $B_0=B_1=1$,   $B_2=2$,   $B_3=5$,   $B_4=15$, $B_5=52$,  $B_6=203$,  $B_7=877$,  $B_8=4140$

10.48 ORD (7+7 points, due Feb 13)   Prove:   (a)   $B_n\le n!$   (b) for all $1\le k\le n$,   $B_n \ge k^{n-k}\,.$

10.50 Bonus (8 points, due Feb 13)   Prove:   $\ln B_n \sim n \ln n\,.$

10.55 ORD (8 points, due Feb 13)   For $n\ge 1$, prove the recurrence
$$ B_n =\sum_{k=0}^{n-1} \binom{n-1}{k} B_k\,.$$

10.60 DEF   The exponential generating function of the sequence $a_0, a_1,\dots$ is $$ F(x) =\sum_{n=0}^{\infty} \frac{a_n}{n!} x^n \,.$$

10.63 DO   Let $B(x)$ denote the exponential generating function of the Bell numbers. Prove that $B(x)$ converges for $|x| < 1$.

10.65 Bonus (9 points, due Feb 13)   Use the recurrence to prove that $B(x)$ satisfies the differential equation   $B'(x) = \eee^x B(x)\,.$

10.68 ORD (10 points, due Feb 13)   Use the differential equation to prove the following epxplicit formula: $$ B(x) = \eee^{\eee^x-1} \,.$$

10.71 Bonus (9 points, due Feb 13)   Use the explicit formula for the exponential generating function to derive Dobiński's formula (1877): $$ B_n = \frac{1}{\eee}\sum_{k=0}^{\infty} \frac{k^n}{k!} \,.$$

Material covered:   Additional "gluing" rules for the construction of STSs. Subhypergraphs. SubSTS. STS as a groupoid. Generators of an STS. De Bruijn--Erdös Theorem, combinatorial proof. Generalization: Fisher--Bose inequality. Linear algebra proof.

09.10 DEF (subhypergraph)   Let $\calH_1=(V_1,\calE_1)$ and $\calH_2=(V_2,\calE_2)$ be hypergraphs. We say that $\calH_2$ is a subhypergraph of $\calH_1$ if $V_2\subseteq V_1$ and $\calE_2\subseteq\calE_1$. Notation: $\calH_2\subseteq \calH_1$.
Note that all edges of $\calH_2$ must be subsets of $V_2$.

09.13 DEF (induced subhypergraph)   Assume $\calH_2\subseteq \calH_1$. We say that $\calH_2$ is an induced subhypergraph of $\calH_1$ if $\calE_2 = \calE_1\cap \calP(V_2)$. Notation: $\calH_2=\calH_1[V_2]$. We say that $\calH_1[V_2]$ is the subhypergraph of $\calH_1$ induced by $V_2$.
The notation $\calH_1[V_2]$ expresses the fact that given $\calH_1$ and the subset $V_2\subseteq V_1$, the subhypergraph of $\calH_1$ induced by $V_2$ is determined: we do not delete any edges of $\calH_1$ that we are not forced to delete because they are not subsets of $V_2$.

09.15 DO   (a) If $\calH$ has $n$ vertices then it has $2^n$ induced subhypergraphs.   (b) In contrast, $\calH$ can have more than $2^{2^n}$ subhypergraphs.

09.17 DO   Let $V_2\subseteq V_1$ and let $\calH_2=(V_2,\calE_2)=\calH_1[V_2]$ the subhypergraph of $\calH_1$ induced by $V_2$. The set $V_2$ is an independent set in $\calH_1$ if and only if $\calE_2=\emptyset$.

09.20 DEF (subSTS)   Let $\calS=(V,\calE)$ be a STS. A subSTS of $\calS$ is a subhypergraph that is an STS.

09.23 ORD (5 points)   $\calS=(V,\calE)$ be a STS. Prove: if $\calS_2$ is a subSTS of $\calS_1$ then $\calS_2$ is an induced subhypergraph of $\calS_1$.

09.30 ORD (9 points)   Let $\calS_1$ and $\calS_2$ be be STSs with $n_1$ and $n_2$ vertices, respectively. If $\calS_2$ is a proper subSTS of $\calS_1$ then $n_2\le (n_1-1)/2$.

09.33 DEF (binary operation, groupoid) Let $S$ be a set. A function $f: S\times S\to S$ is called a binary operation. Instead of $f(x,y)$ we usually write $x\circ y$. We say that the pair $(S,\circ)$ is groupoid.
We usually refer to the operation $\circ$ as "multiplication." Other common notations for binary operations are $+$, $\times$, $\wedge$, $\vee$. These usually refer to associative operations, but a groupoid is not assumed to be associative.

Note.   In class I mistakenly stated that groupoids are defined to satisfy the cancellation law. In fact the definition of a groupoid puts no restriction on the binary operation.

Warning.   Our definition follows Hausmann and Ore (1937). A decade earlier Brandt introduced the term "groupoid" in a different meaning; those groupoids are usually referred to as "Brandt groupoids." There was considerable controversy over overloading this term.

09.36 ORD (4 points)   Count the groupoids on a given set $S$ of $n$ elements. Your answer should be a very simple expression. No proof required.

09.39 DEF (quasigroup)   A groupoid $Q=(S,\circ)$ is called a quasigroup if it satisfies the axiom
  $(\forall a,b\in S)(\exists! x,y\in S)(a\circ x=b\text{ and } y\circ a=b)$.
(All left and right linear equations are uniquely solvable.)

09.42 DO (quasigroups vs Latin squares)   A finite groupoid is a quasigroup if and only if its multiplication table is a Latin Square.

09.45 DEF (cancellation laws)   Let $R=(S,\circ)$ be a set with a binary operation. We say that $R$ satisfies the left cancellation law if $(\forall a,x,y\in S)(a\circ x=a\circ y \Rightarrow x=y)$. The right cancellation law is defined analogously.

09.48 DO   Every quasigroup satisfies the cancellation laws.

09.51 ORD (6+5 points)   (a) A finite groupoid is a quasigroup if and only if it satisfies the cancellation law.   (b) Find an infinite groupoid that satisfies the cancellation laws but is not a quasigroup.

09.54 DEF (idempotent)   Let $(S,\circ)$ be a groupoid. We say that $x\in S$ is an idempotent if $x\circ x =x$.

09.57 DO (STS vs quasigroups)   Let $\calS=(V,\calE)$ be a STS. Let us define a binary operation on $S$ as follows:
   for $x\in V$ we write $x\circ x= x$
   for $x\neq y\in V$ we write $x\circ y= z$ if $\{x,y,z\}\in\calE$. Let us denote the structure $(V,\circ)$ by $\calS^{\circ}$.
   (a) Prove that $\calS^{\circ}$ is a quasigroup.
   (b) Every element of $\calS^{\circ}$ is idempotent.
   (c) The operation is commutative:   $(\forall x,y\in V)(x\circ y = y\circ x)$.
   (d) If $x\circ y=z$ then $y\circ z = x$.

09.60 DO   Every quasigroup that satisfies the identities (b), (c), and (d) arises from a unique STS. So we have a bijection between STSs and quasigroups satisfying (b), (c), (d).

09.63 DEF (direct product)   Let $R_1=(S_1,\circ_1)$ and $R_2=(S_2,\circ_2)$ be groupoids. The direct product $R_1\times R_2$ is defined as the groupoid $(S_1\times S_2,\circ)$ where $\circ$ is defined componentwise: for $x_1,y_1\in S_1$ and $x_2,y_2\in S_2$ we write   $(x_1,x_2)\circ (y_1,y_2) = (x_1\circ_1 y_1, x_2\circ_2 y_2)$.

09.66 DO   Any identity satisfied by $R_1$ and $R_2$ is satisfied by $R_1\times R_2\,.$

09.69 DO   Use the preceding exercise to define the direct product of STSs.

09.72 DO   Let $\calS_d$ denote the STS defined by the points and lines of the affine geometry $\AG(d,3)$. Verify that $\calS_d \times \calS_e = \calS_{d+e}$.

09.75 DO   If there exist STSs $\calS_1$ and $\calS_2$ of respective orders $n_1$ and $n_2$ then there is a STS of order $n_1n_2$ containing $\calS_1$ and $\calS_2$ as subSTSs.   (Use direct product.)

09.78 DEF   Let $R=(S,\circ)$ be a groupoid. A subgroupoid is a subset $T\subseteq S$ that is closed under multiplication: if $x,y\in T$ then $x\circ y\in T$. So a subgroupoid is a groupoid under the restriction of $\circ$ to the set $T$. With some abuse of notation and terminology, we denote by $T$ both the subset and the groupoid defined on this subset.

09.81 DO   The intersection of any number of subgroupoids is a sugroupoid.

09.84 DEF (generated subgroupoid)   Let $R=(S,\circ)$ be a groupoid and $H\subseteq S$. Let $\langle H\rangle$ denote the smallest subgroupoid containing $H$, i.e.,
   (a)   $H\subseteq \langle H\rangle$ and
   (b)   if $T$ is a subgroupoid of $R$ and $H\subseteq T$ then $\langle H\rangle \subseteq T$.
We say that $\langle H\rangle$ is the subgroupoid generated by $H$.

09.87 DO   Prove that $\langle H\rangle$ aways exists. Indeed, $\langle H\rangle$ is the intersection of all subgroupoids that contain $H$.

09.90 DEF (straight-line program)   Let $R=(S,\circ)$ be a groupoid, $H\subseteq S$, and $x\in S$. A straight-line program reaching $x$ from $H$ is a sequence $u_1,\dots,u_m = x$ of elements of $S$ such that for all $i$, either $u_i\in H$ or $u_i=u_j\circ u_k$ for some $j,k < i$.

09.93 DO (characterization of generated subgroupoid) The elements of $\langle H\rangle$ are precisely the elements of $S$ reachable by straight-line programs from $H$.

09.96 DEF (set of generators)   Let $R=(S,\circ)$ be a groupoid and $H\subseteq S$. We say that $H$ generates $R$ (or $H$ is a set of generators of $R$) if $\langle H\rangle = S$.

09.100 Bonus (8 points)   Let $\calS$ be a STS with $n$ elements. Prove: $\calS$ can be generated by at most $\log_2(n+1)$ elements (i.e., there exists a set $H$ of generators where $|H|\le \log_2(n+1)$).

09.104 Challenge   Prove: there exist arbitrarily large STSs with just 3 generators.

09.110 Theorem (N. G. de Bruijn, Paul Erdös)   Let $\calH=(V,\calE)$ be a hypergraph with $n$ vertices and $m$ edges. Assume that for all $E\neq F\in\calE$ we have $|E\cap F|=1$. Then $m\le n$.

09.113 DO   Prove the De Bruijn--Erdös Theorem in the cases when   (a)   $(\exists x\in V)(\deg(x) = m)$ or   (b)   $(V\in\calE)$.

09.115 DO   (proof of De Bruijn--Erdös continued) If $x\in V$ and $E\in \calE$ and $x\notin E$ then $\deg(x) \le |E|$.

09.117 DO   (proof of De Bruijn--Erdös continued) Assume $(\forall x\in V)(\deg(x) < m)$ and $V\notin\calE$. Assume for a contradiction that $m > n$. Then for all non-incident pairs $(x,E)$ $(x\in V, E\in \calE)$ we have $m -\deg(x) > n - |E|$. Therefore $$ \frac{\deg(x)}{m-\deg(x)} < \frac{|E|}{n-|E|}.$$ Add up these inequalities for all non-incident pairs $(x,E)$. Verify that we get $$\sum_{x\in V} \deg(x) < \sum_{E\in\calE} |E|.$$ This contradicts the Handshake Theorem which asserts that the two sides of this equation are equal.

09.120 Bonus (14 points, due Feb 20)   Let $\calH$ be a hypergraph satisfying the conditions of the De Bruijn--Erdös Theorem. Assume no vertex is contained in every edge. Prove: if $m=n$ then every pair of vertices is contained in an edge:   $(\forall x,y\in V)(\exists E\in\calE)(x,y\in E)$.

09.125 Theorem (Fisher--Bose inequality)   Let $\lambda\ge 1$ be an integer. Let $\calH=(V,\calE)$ be a hypergraph with $n$ vertices and $m$ edges. Assume that for all $E\neq F\in\calE$ we have $|E\cap F|=\lambda$. Then $m\le n$.

09.128 DO   Use linear algebra to prove the Fisher--Bose inequality. Let $M$ be the incidence matrix of $\calH$. Determine the matrix $A:=MM^T$. Use previous exercises to show that $A$ is non-singular. Conclude that $m\le n$.

09.130 historical comment. In 1940, statistician Ronald A. Fisher proved the Fisher--Bose inequality for the case of regular uniform hypergraphs, using a second moment argument. In 1949, statistician Raj Chandra Bose dropped the regularity assumption but retained uniformity. More importantly, Bose's 1949 paper inaugurated the linear algebra method of proving combinatorial inequalities, revolutionizing the field of extremal combinatorics. In 1953, statistician K. N. Majumdar got rid of the uniformity condition by calculating an explicit formula for the determinant of the matrix $\lambda J+D$ where $D$ is a positive diagonal matrix (all diagonal entries are positive). The elegant proof of non-singularity of that matrix via positive definiteness was found later.

Material covered:   System of Distinct Representatives (SDR), Hall conditions. $r$-regular $r$-uniform hypergraph has SDR; in fact, it has $\ge r!$ SDRs (stated, elementary). Every Latin rectangle can be completed to a Latin Square. Estimating $L(n)$, the number of Latin squares of order $n$. $(1/2)n^2 \ln n\lesssim \ln L(n) < n^2\ln n$. Permanent. Doubly stochastic matrix, the Permanent Inequality (Egorychev--Falikman). Consequence: $r$-regular $r$-uniform hypergraph has more than $(r/\eee)^n$ SDRs. Corollary: $\ln L(n) \sim n^2\ln n$. Using Latin squares to glue together triples of STSs to get larger STS's; size growth: $n\mapsto 3n$, $n\mapsto 3n-2$, $n\mapsto 3n-6$. After a small starter set, these and some other similar operations cover all admissible orders (orders $n\equiv 1\text{ or }3\pmod{6}$). Subhypergraph, induced subhypergraph. SubSTS has order $\le (n-1)/2$. An STS of order $n$ can be generated by at most $\log_2(n+1)$ elements.

08.10 DO   Let $X,Y,Z$ be independent random variables. Let $f:\rrr\times\rrr\to\rrr$ be an arbitrary real function. Prove: $X$ and $f(Y,Z)$ are independent.
Examples:   $f(Y,Z)=YZ$, or $f(Y,Z)=(Y^2+1)^{\cos Z}$.

08.12 ORD (8+8+8 points)   Let $X,Y,Z$ be random variables. For each of the following questions, give a clear YES/NO answer. If your answer is YES, prove. If your answer is NO, give a counterexample on the smallest possible sample space. Clearly state the size of your sample space and prove its minimality.
(a)   Assume $X,Y,Z$ are pairwise independent. Does it follow that $X$ and $Y+Z$ are independent?
(b)   Assume $X,Y$ are uncorrelated and $X,Z$ are uncorrelated. Does it follow that $X$ and $Y+Z$ are uncorrelated?
(c)   Assume $X,Y,Z$ are pairwise independent. Does it follow that $X$ and $YZ$ are uncorrelated?

08.15 Bonus (15 points, due Feb 20) (strongly negatively correlated events)   Let $A_1,\dots, A_m$ be balanced events $(P(A_i)=1/2)$ such that $(\forall i\neq j)(P(A_i\cap A_j)\le 1/5)$. Prove:   $m\le 6$.

08.17 Challenge (4-wise independent events)   Let $A_1,\dots,A_m$ be 4-wise independent (every four are independent) nontrivial events on a sample space of size $n$. Prove:   $n = \Omega(m^2)$.

8.20 DO   Prove: if there exists a STS $\calS$ with $n$ vertices then there is a STS containing $\calS$ with   (a) $3n$   (b) $3n-2$   (c) $3n-6$ vertices.

08.22 DO   Prove: if there exists a STS with $n$ vertices that contains the Fano plane as a subSTS then there exists a STS with $3n-14$ vertices that contains the Fano plane as a subSTS.

08.24 ORD (8 points, due Feb 13)   Prove: if there exists a STS $\calS_1$ with $k$ vertices and a STS $\calS_2$ with $\ell$ vertices then there exists a STS with $k\ell$ vertices that inlcudes $\calS_1$ and $\calS_2$ as subSTS's.

08.26 Bonus (13 points)   Prove: if there exists a STS $\calS$ with $n$ points then there exists a STS with $2n+1$ points that includes $\calS$ as a subSTS.

08.28 Bonus (18 points, due Feb 20)   Let $\calH=(V,\calE)$ be a hypergraph with $n$ vertices and $m$ edges such that for any $E,F\in \calE$ we have $E\cap F\neq \emptyset$ and $E\cup F\neq V$. Prove: $m\le 2^{n-2}$.
You may use any of the exercises in Classes 9-11 without proof.

The following sequences of exercises are in preparation for the construction and counting of Latin squares.

08.30 DEF   Let $\calF=(F_1,\dots,F_m)$ be a list of not necessarily distinct sets. A system of distinct representatives (SDR) of $\calF$ is a list $(x_1,\dots,x_m)$ of distinct elements such that $x_i\in F_i$.

08.33 DEF   (continued) Let $I\subseteq [m]$. The Hall condition corresponding to $I$ is the condition that $|\bigcup_{i\in I} F_i| \ge |I|$. A Hall violator is a subset $I\subseteq [m]$ that violates the corresponding Hall condition.

08.36 DO   (continued) Prove: If there exists a Hall violator for $\calF$ then $\calF$ has no SDR. In other words, the Hall conditions are necessary for the existence of a SDR.

08.39 THEOREM ("Marriage Theorem") (Dénes König (1931), Philip Hall (1935)) If none of the Hall conditions is violated then $\calF$ has a SDR.
In other words, the conjunction ("AND") of the $2^m$ Hall conditions is necessary and sufficient for the existence of a SDR.

08.42 Historical remarks.   This is one of the central results of combinatorial optimization. It can be equivalently restated in terms of bipartite graphs, and also in terms of $(0,1)$ matrices. König's result is stronger than Hall's and asserts that for bipartite graphs, $\tau = \nu$, anticipating combinatorial duality theory; and the concepts of "good characterization" and the complexity class NP$\cap$coNP, developed in the 1960s by Jack Edmonds. König's method anticipates primal/dual algorithmic techniques. The result (and the method) was immediately (1931) extended to weighted bipartite graphs (the "assignment problem") by Jenö Egerváry, König's colleague at the Budapest University of Technology. These two papers appeared in Hungarian in the same issue of the "Matematikai és Fizikai Lapok" ("Mathematical and Physical Letters"). In 1955, Harold W. Kuhn published an exposition of the result in English in which he named the algorithm the Hungarian method in honor of König and Egerváry; this term is being used to this day. --- A result stronger than König's that predates König's publication is Menger's Theorem (Karl Menger 1927) about the connectivity of graphs. --- In 1984, Joseph Kung derived the König--Egerváry theorem from Jacobi's determinant identity (1841). In 2006 it was discovered that Carl Jacobi (1804-1851), one of the great mathematicians of the early 19th century, himself had discovered the König--Egerváry theorem (in the context of determinants); his paper, written in Latin, was published posthumously in 1890.

08.45 DO   König's Duality Theorem (1931) states that "$\tau = \nu$ for bipartite graphs." Derive the Marriage Theorem from this result.

08.48 THEOREM (König 1916)   Let $r\ge 1$. Every $r$-regular $r$-uniform hypergraph has a SDR.

08.50 DEF   Let $1\le k\le n$. A $k\times n$ Latin rectangle is a $k\times n$ matrix $(r(i,j))$ such that (i) every row is a permutation of $[n]$ and (ii) every column consists of distinct numbers.
Example: this is a $3\times 4$ Latin rectangle:
$$\begin{pmatrix} 3 & 1 & 2 & 4\\ 4 & 2 & 1 & 3\\ 1 & 3 & 4 & 2\\ \end{pmatrix}$$

08.53 DO   Use König's 1916 theorem above to prove that every Latin rectangle can be completed to a Latin square.

08.54 DO Prove the following strengthening of König's 1916 theorem above.
Let $r\ge 1$. Let $\calH=(V,\calE)$ be a hypergraph. Assume every vertex has degree $\le r$ and every edge $E\in\calE$ has size $|E|\ge r$. Prove: $\calE$ has a SDR. Use the Marriage Theorem.

08.57 Challenge   Let $r\ge 1$. Prove: an $r$-regular $r$-uniform hypergraph has at least $r!$ SDRs. (Do not use the Permanent Inequality.)

08.60 DEF   Let $a_n, b_n$ be sequences of positive real numbers. We say that $a_n\gtrsim b_n$ if $\liminf a_n/b_n \ge 1$. In words: "greater than or asymptotically equal."

08.62 DO   Compare this definition with the one given in ASY, Def. 6.1. STUDY ASY, Sections 5 and 6.

08.63 DEF (isomorphism of Latin squares).   Let $L_1$ and $L_2$ be two Latin squares of order $n$. We say that $L_1$ and $L_2$ are isomorphic (denoted $L_1\cong L_2$) if $L_2$ can be obtained from $L_1$ by any combination of the following four ways:
   (a)  permuting the rows
   (b)  permutig the columns
   (c)  permuting the labels
(so far this gives potentially $(n!)^3$ isomorphic copies)
   (d)  and you can permute the 3 roles: row index, column index, label
(so this gives an additional factor of $3!=6$).
So the maximum number of isomorphic copies of $L_1$ we can get is $6(n!)^3.$ (Note that these $6(n!)^3$ copies are not necessarily distinct.)

To understand (d), we need to represent a Latin square as a set of triples $(i,j,z_{i,j})$, where $z_{i,j}$ is the entry in position $(i,j)$. So this gives a description of the Latin square as an $n^2 \times 3$ matrix, and we are allowed to permute the columns of that matrix.

08.64 DO   Prove, that, given a Latin square, an application of any of the rules 08.63(a)--(d) again produces a Latin square.

08.65 ORD (8+7 points)   (a) Let $L(n)$ denote the number of Latin squares of order $n$. Use Challenge problem 8.57 to show that $\ln L(n) \gtrsim (1/2) n^2 \ln n$. (Note that this is half of the true magnitude, see 08.129.)   (b) Let ${\wt L}(n)$ denote the number of non-isomorphic Latin squares of order $n$. Prove:   $\ln({\wt L}(n)) \sim \ln(L(n))$.

08.68 Historical comment.   For several decades, the best lower bound known for $\ln(L(n))$ was the oone given in Ex. 08.65. This was only improved using the immediate precursor of the Permanent Inequality (8.120 below) by Tøger Bang (around 1977).

08.71 ORD (5 points)   Let $L(k,n)$ denote the number of $k\times n$ Latin rectangles. Prove:   $L(2,n) \sim (n!)^2/\eee$.
Hint.   07.29.

08.80 DEF   The permanent of the $n\times n$ matrix $A=(a_{ij})$ is defined as the sum $$ \per(A) = \sum_{\sigma\in S_n} \prod_{i=1}^n a_{i,\sigma(i)} $$ where the summation extends over all permutations of $[n]$. This definition is identical with the definition of the determinant except the signs are missing.

08.83 Comment   (Computational intractability of the permanent) While the determinant can be efficiently computed using Guassian elimination, this algorithm does not work for the permanent. In fact no known algorithm works, and no efficient algorithm is expected to work. Computing the permanent of a $(0,1)$-matrix is $\#\PPP$-complete (Valiant, 1978), meaning it is as hard as counting the solutions to any NP-puzzle, e.g., counting the 3-colorings of a graph or counting the satisfying assignments to a Boolean formula. This seems a great deal harder than solving NP-complete decision problems such as the existence of a 3-coloring of a graph or the existence of a satisfying assignment to a Boolean formula.
This apparent extreme computational difficulty is a partial explanation of the difficulty of proving theoretical results about the permanent.

08.86 DO   (a) If $A$ is a permutation matrix (each row and each column has one entry of 1, the rest is zero) then $\per(A)=1$. In particular, $\per(I)=1$, where $I$ is the identity matrix.   (b) $\per(J)=n!$ .

08.89 DO (permanent counts SDR's)   Let $\calH$ be a hypergraph with $n$ vertices and $n$ edges. Let $M$ be the incidence matrix of $\calH$; so $M$ is an $n\times n$ $(0,1)$-matrix. Prove: the number of SDRs of $\calH$ is $\per M$.

08.92 DO   Prove that counting SDRs of hypergraphs is $\#P$-hard.   This should be an immediate consequence to (in fact, equivalent to) Valiant's result (08.83) if we permit the hypergraph to have repeated edges. The result remains valid under our convention that we do not permit repeated edges; this causes only a slight technical difficulty, which is the main subject of this exercise. Give a very simple reduction of computing an $n\times n$ $(0,1)$-permanent to counting the SDRs of a hypergraph with $2n$ vertices and $2n$ edges, no repeated edges permitted.

08.100 DEF   Let $A=(a_{ij})\in M_n(\rrr)$. We say that $A$ is a stochastic matrix if every row of $A$ is a probability distribution, i.e., $(\forall i,j)(a_{ij}\ge 0)$ and $(\forall i)(\sum_{j=1}^n =1)$ (every row sum is 1). We say that $A$ is doubly stochastic if both $A$ and $A^T$ are stochastic. In other words, $A$ is doubly stochastic if its entries are non-negative and the sum of each row is 1 and the sum of each column is 1.
Examples: $(1/n)J$, $I$, all permutation matrices.

08.103 DEF   A convex combination of vectors over the reals is a linear combination where the coefficients form a probability distribution: $\sum_{i=1}^k a_iv_i$ where $a_i\ge 0$ and $\sum_{i=1}^k a_i=1$. --- Note that a linear combination is convex if and only if it is affine and has non-negative coefficients.

08.106 DO   Prove: convex combinations of doubly stochastic matrices are doubly stochastic.

08.109 Reward problem (Garrett Birkhoff, 1946)   Prove: A matrix is doubly stochastic if and only if it is a convex combination of permutation matrices.   (A "Reward problem" is similar to a challenge problem, but do not hand in your solution. Your reward is the elegance of the solution. You may use the Marriage Theorem.)

08.112 ORD (9+12 points)   Let $A$ be a stochastic matrix.   (a) Prove: $\per(A)\le 1$.   (b) Prove:  $\per(A)=1$ if and only if $A$ is a permutation matrix.

08.115 DO   Let $c\in\rrr$. Prove:   $\per(cA)=c^n\per(A)$. In particular, $\displaystyle{\per\left(\frac{1}{n}J\right)=\frac{n!}{n^n} > \eee^{-n}}$.

08.120 THE PERMANENT INEQUALITY (G. P. Egorychev, D. I. Falikman, 1981)   Let $A$ be a doubly stochastic matrix. Then $\displaystyle{\per(A)\ge \frac{n!}{n^n}}$. Moreover, equality holds here if and only if $\displaystyle{A = \frac{1}{n}J}$ (where $J$ is the all-ones matrix).

08.123 HISTORY   For over half a century, this problem was known as B. L. van der Waerden's Conjecture (published in 1926). The slightly weaker result, $\per(A) > \eee^{-n}$, sufficient for most applications, was obtained by Norwegian mathematician Tøger Bang around 1977. Based on an early version of Bang's paper, Shmuel Friedland published a proof of the $\per(A) > \eee^{-n}$ inequality that is more widely accessible ("A Lower Bound for the Permanent of a Doubly Stochastic Matrix", Annals of Mathematics, Vol. 110, No. 1 (Jul., 1979), pp. 167-176).

An elementary proof of the Permanent Inequality can be found in the book by Van Lint and Wilson (listed on the course home page).

08.126 ORD (9 points) Let $\calH$ be an $r$-regular and $r$-uniform hypergraph with $n$ vertices $(r\ge 1)$. Prove:   $\calH$ has more than $(r/\eee)^n$ SDRs.   Use the Permanent Inequality to prove this result. (You may use any of the DO exercises stated above without proof.)

08.129 Bonus (8 points) Let $L(n)$ denote the number of $n\times n$ Latin squares. Prove:   $\ln L(n) \sim n^2\,\ln n$.

07.10 STUDY   LinAlg Chapter 5 (affine and convex combinations).

07.13 REVIEW   LinAlg Section 6.2 (permutations).

07.15 STUDY   the card game "SET"   https://en.wikipedia.org/wiki/Set_(card_game)
invented in 1974 by population geneticist Marsha Jean Falco who was coding information about the heredity of epilepsy among German shepherds on file cards in Cambridge, U.K.$\dots$. She released the game 17 years later, in 1991.

07.18 DEF   Let $A,B,C\subseteq\zzz$. We say that $C$ is the direct sum of $A$ and $B$, denoted $C=A\oplus B$, if $(\forall c\in C)(\exists!a\in A\text{ and }b\in B)(a+b=c)$. (Every element $c\in C$ is uniquely representable as a sum $c=a+b$ where $a\in A$ and $b\in B$.)
Example: $\{2,3,4,5,6,8\} = \{1,2,5\}\oplus\{1,3\}$.

07.20 ORD (7 points, due Feb 6)   Find $A,B\subseteq\nnn_0$ such that $A\oplus B=\nnn_0$ and $|A|=100$.
(Recall: $\nnn_0$ denotes the set of non-negative integers.)

07.22 Bonus (14 points, due Feb 13)   Find two infinite sets $A,B\subseteq\nnn_0$ such that $A\oplus B=\nnn_0$.

07.27 ORD (5 points)   $S_n$ denotes the set of permutations of $[n]$ (the symmetric group of degree $n$). Let $\even(n)$ denote the set of even permutations in $S_n$ and $\odd(n)$ the set of odd permutations. Let $J_n$ denote the $n\times n$ all-ones matrix (every entry is 1). Prove: for $n\ge 2$ we have $|\even(n)|=|\odd(n)|$. Use the fact that $\det(J_n)=0$. Solutions that do not use this fact will not be accepted. Your solution should be no more than a couple of lines.

07.29 ORD (10 points, due Feb 6) Let $D_n$ denote the number of fixed-point-free permutations in $S_n$. Prove:   $D_n \sim n!/\eee$. Use Inclusion--Exclusion.

07.31 Bonus (9+4 points, due Feb 6)   Let $\even^*(n)$ denote the set of fixed-point-free even permutations and $\odd^*(n)$ the set of fixed-point-free odd permutations in $S_n$. (a) Determine the value $|\even^*(n)|-|\odd^*(n)|$. Your answer should be a very simple closed-form expression.   (b) For what values of $n$ is $|\even^*(n)| > |\odd^*(n)|$ ?

07.35 ORD (6+2 points, due Feb 6)   (a) Given $k\in\nnn$, determine the smallest value of $n\in\nnn$ such that the following is true:
$[n]$ has $k$ subsets, $A_1,\dots,A_k$, such that all the $2^k$ intersections $B_I :=\bigcap_{i\in I} A_i$ $(I\subseteq [k])$ are distinct.   (b) Prove that your value $n$ is minimal.
Note that $B_{\emptyset}=[n]$ (the empty intersection of subsets of a set is the whole set).

07.40 ORD (6 points)   Let $n\in \nnn$. Find $n+1$ distinct subsets $A_0,\dots,A_n\subseteq [n]$ such that for every $i\in [n]$, the sets $A_0\setminus \{i\},\dots,A_n\setminus\{i\}$ are not all distinct.

07.43 Bonus (J. A. Bondy's theorem) (18 points, due Feb 13)   Let $n\in \nnn$. Let $A_1,\dots,A_n\subseteq [n]$ be $n$ distinct subsets. Prove: there exists $i\in [n]$ such that the sets $A_1\setminus \{i\},\dots,A_n\setminus\{i\}$ are all distinct.

07.50 DEF   Let $W$ be a vector space over the field $\fff$ and let $u\in W$. The translation (or shift) of $W$ by $u$, denoted $T_u$, is the function (transformation) $T_u:W\to W$ where $T_u(w)=w+u$ for all $w\in W$. Let $S\subseteq W$ and $w\in W$. The translate of $S$ by $u$ is the set $S+u :=\{T_u(s)\mid s\in S\} =\{s+u\mid s\in S\}$.

07.53 ORD (5+4+4 points)   (a) Let $W$ be a vector space over the field $\fff$. Prove: a non-empty subset $S\subseteq W$ is an affine subspace (closed under affine combinations) if and only if there exists a linear subspace $U\le W$ (closed under linear combinations) and a vector $u\in W$ such that $S=U+u$.   (b) Prove: if such $U$ and $u$ exist, the subspace $U$ is unique.   (c) The vector $u$ is unique modulo $U$, i.e., $U+u = U+v$ if and only if $u-v\in U$.

07.55 ORD (4 points)   An affine subspace $U\le_{\aff}W$ is a linear subspace if and only if $0\in U$.

07.58 ORD (4 points)   Let $W$ be a $d$-dimensional affine space over $\fff_q$. Prove:   $|W|=q^d$.

07.65 DEF   A Steiner Triple System (STS) is a 3-uniform hypergraph $\calS=(V,\calF)$ with $n\ge 1$ vertices such that $(\forall u\neq v \in V)(\exists! F\in\calF)(u,v\in F)$ (every pair of distinct vertices belongs to a unique edge (triple)).

07.67 ORD (5+5+5 points)   Let $\calS=(V,\calF)$ be a STS with $n=|V|$ vertices.   (a) Prove: $\calS$ is regular. Determine its degree as a function of the number of vertices, $n=|V|$.   (b) Determine $m:=|\calF|$, the number of edges, as a function of $n$. (c) Prove:   $n\equiv 1\text{ or }3\pmod{6}$.

07.69 ORD (4 points)   Let $\calS$ be a STS with $n$ vertices. Determine $\tau^*(\calS)$.

07.71 Bonus (10 points, due Feb 6)   Let $\calS$ be a STS with $n$ vertices. Let $M$ be a maximal independent set in $\calS$. Prove:   $|M| > \sqrt{2n} - 1/2$.
Note, in particular, that this is a lower bound on $\alpha(\calS)$.

07.73 ORD (7 points, due Feb 6)   Let $\calS$ be a STS with $n$ vertices. Prove:  $\alpha(\calS)\le (n+1)/2$.
Your proof should not take more than a few lines.

07.75 Bonus (9+9 points, due Feb 13)   (a) Let $\calS$ be a STS with $n > 3$ vertices. Prove:   $\chi(\calS) \ge 3$.   (b) Prove: there are infinitely many STS's with $\chi(\calS)=3$.

07.76 Question Let $C$ denote the limsup, as $n\to\infty$, of $\alpha(\calS)/n$, over all STS's $\calS$. We know from the previous two exercises that $1/3 \le C \le 1/2$. Can we improve either the lower or the upper bound?
"Question" means I do not know the answer. It does not mean it is necessarily difficult -- I did not spend time on it. In this case the answer is probably known. If you figure out the answer (or find it), let me know.

07.77 ORD (7 points, due Feb 6)   Let $\Pi$ be a finite projective plane of order $n$. (So the number of points is $n^2+n+1$.) Prove: if $n\ge 3$ then $\Pi$ has an independent cover (a cover that is at the same time an independent set). Show that there is an independent cover of size $\le 2n$.

07.78 DO   The Fano plane has no independent cover.

07.80 Question   Is $2n$ the smallest size of an independent cover of a projective plane of order $n\ge 3$?

07.82 Bonus (10 points, due Feb 6)   Let $\calS$ be a STS with $n > 3$ vertices. Prove:   $\calS$ has no independent cover.

07.85 ORD (5 points)   Prove: the vectors $x,y,z\in\fff_3^d$ form an affine line if and only if $x+y+z=0$ and $x\neq y$.

07.87 DEF   Let $\calS(d,3)$ denote the STS defined by the affine geometry $\AG(d,3)$. So the set of vertices of $\calS(d,3)$ is $\fff_3^d$ and the edges are the lines (1-dimensional affine subspaces). So $n=3^d$.

07.89 ORD (9 points, due Feb 6)   Let $\alpha_d:=\alpha(\calS(d,3))$. Prove:   $\alpha_d\ge 2^d$. Do not use the next exercise.

07.92 Bonus (8 points, due Feb 6)   Using the notation of the preceding exercise, prove:   $\alpha_{r+s} \ge \alpha_r\cdot\alpha_s$.

07.94 DO (Fekete's Lemma, supermultiplicativity version)   (a) Let $b_1, b_2,\dots$ be an infinite sequence of real numbers, $b_i\ge 1$. Assume for all $i,j\in\nnn$ we have $b_{i+j}\ge b_ib_j$ (the sequence is supermultiplicative). Let $L=\sup_n (b_n)^{1/n}$. Prove: $L=\lim_{n\to\infty} (b_n)^{1/n}$.
Note:   $L=\infty$ is permitted here.
(b) Formulate and prove the submultiplicativity version.

07.97 ORD (5+(2+2)+9 points)   Let $\alpha_d:=\alpha(\calS(d,3))$ (see Def. 07.87). Use the preceding exercises to prove the following.
Let $L=\lim_{d\to\infty} \alpha_d^{1/d}$.   (a) Prove that this limit exists.   (b) Prove:   $2\le L\le 3$.   (c) (due Feb 6)   $L > 2$. Give the best lower bound you can for $L$. You may use lower bounds you find in the literature for $\alpha(\calS(d,3))$ for specific values of $d$. Give the bibliographic reference of your source.

07.100 Challenge$^*$   $L < 3$.

07.110 DEF   A Latin Square (LSq) of order $n$ is an $n\times n$ matrix $M=(m_{ij})$ such that $(\forall i,j)(m_{ij}\in [n])$ and no number is repeated in any row and in any column (so each row and each column is a permutation of $[n]$).

07.115 DEF     Let $K=(k_{ij})$ and $M=(m_{ij})$ be LSq's of order $n$. We say that $K$ and $L$ are orthogonal if $\{(k_{ij},m_{ij}) \mid i,j\in [n]\} = [n]\times [n]$.

07.118 ORD (8 points)   Prove: if $n\ge 3$ is odd then there exists a pair of orthogonal LSq's of order $n$.

07.121 Bonus (12 points, due Feb 6)   Prove: if $n=2^k\ge 4$ ($n$ is a proper power of $2$) then there exists a pair of orthogonal LSq's of order $n$.

07.124 Bonus (8 points)   Prove: if there exists a pair of orthogonal LSq's of order $r$ and a pair of orthogonal LSq's of order $s$ then there exists a pair of orthogonal LSq's of order $rs$.

07.126 DO   Deduce from the preceding exercises that if $n\ge 3$ and $n\not\equiv 2\pmod{4}$ then there exists a pair of orthogonal LSq's of order $n$.

07.129 Theorem (Gaston Terry, 1901)   There is no pair of orthogonal LSq's of order 6. This gives a negative answer to Euler's 36 officers problem.

07.131 Theorem (Bose-Shrikhande-Parker, 1959)   If $n\ge 3$ and $n\neq 6$ then there exists a pair of orthogonal LSq's of order $n$.

07.135 Bonus (12+12 points, due Feb 13)   (a) If there exist $m$ pairwise orthogonal LSq's of order $n$ then $m\le n-1$.   (b) $m=n-1$ occurs if and only if there exists a projective plane of order $n$.

06.10 reading (optional)   "The hitchhiker's guide to the Galaxy" by Douglas Adams.

06.13 DO   Let $0\le a_n\le 1$. We define the value of the infinite product $\prod_{n=1}^{\infty} (1-a_n)$ as $\lim_{n\to\infty}\prod_{k=1}^{\infty} (1-a_k)$.   (a)   Prove: this limit always exists.   (b)   We say that this infinite product is divergent if its value is zero. Prove: this infinite product is divergent if and only if the infinite sum $\sum_{n=1}^{\infty} a_n$ is divergent (infinite).

06.15 DO   There exists a constant $\gamma$ such that $\sum_{k=1}^n (1/k) = \ln n +\gamma + o(1)$. The constant $\gamma \approx 0.5772$ is called the Euler--Mascheroni constant.

06.18 Theorem   $\sum_{p \le n} (1/p) = \ln\ln n + M + o(1)$ where $M\approx 0.2615$ is the Meissel--Mertens constant.

06.20 REVIEW   Euler's phi function (LinAlg Def. 4.1.44 and Exercise 4.1.45).

06.22 Reward   $\liminf_n \frac{\vf(n)}{n} = 0$, where $\vf$ denotes Euler's phi function.

06.24 DEF (Euler's zeta function)   For $s > 1$ let $$ \zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s} $$ This function was later extended by Riemann to all complex values of $s$ (the Riemann zeta function).

06.26 Theorem (Euler)   $\zeta(2) = \pi^2/6$.

06.28 DO/DEF Pick a random natural number $x$ (positive integer). What is the probability that $x\equiv 3\pmod{4}$ ? The plausible answer is $1/4$, but what does this answer mean? What exactly is the question? There is no uniform distribution over $\nnn$. (See also 06.10 for a similar problem.)

The missing definition: let $p_n$ denote the probability that $x\in [n]$ satisfies $n\equiv 3 \pmod{4}$. ($x$ is chosen from $[n]$ uniformly.) Now, $\lim_{n\to\infty} p_n = 1/4$.

06.30 Reward What is the probability that a random pair of natural numbers is relatively prime? Prove: the answer is $1/\zeta(2)=6/\pi^2$ (under the interpretation that we consider the limit, as $n\to\infty$, of the probability that a pair of integers chosen uniformly from $[n]\times [n]$ is relatively prime).

06.32 Challenge   Let $D_n = (\gcd(i,j))_{n\times n}$ be the $n\times n$ matrix of which the entry in position $(i,j)$ is $\gcd(i,j)$. Prove: $\det(D_n)=\prod_{k=1}^n \vf(k)$,

06.40 REVIEW   the definition of $\tau(\calH)$ (covering number, Def. 03.130)) and $\nu(\calH)$ (matching number, Def. 03.155) of the hypergraph $\calH$.
In LaTeX, the Greek letters involved are "\tau" $(\tau)$ and "\nu" $(\nu)$.

06.42 CONVENTION    We shall say that a hypergraph $\calH=(V,\calE)$ is bad if $\emptyset\in \calE$, and good otherwise.   Note: this is not standard terminology.

06.45 DEF   A fractional cover of a hypergraph $\calH=(V,\calE)$ is a function $f:V\to\rrr$ with following properties:

  (i)    $(\forall u\in V)(f(u) \ge 0)$
  (ii)   $(\forall E\in \calE)(\sum_{u\in E} f(u) \ge 1)$

The value of the fractional cover $f$ is $\val(f)=\sum_{u\in V} f(u)$.

06.48 DO   A hypergraph $\calH$ has a fractional cover if and only if $\calH$ is good.

06.50 DEF   The fractional covering number of a good hypergraph $\calH$ is
$$ \tau^*(\calH) = \min\{\val(f)\mid f\text{ is a fractional cover of }\calH\}\,.$$ For a bad hypergraph $\calH$ we set $\tau^*(\calH)=\infty$. (Why?)

We say that a fractional cover is optimum if its value is $\tau^*(\calH)$.

06.53 Bonus (5 points)   Prove that for every good hypergraph $\calH$, the definition of $\tau^*$ is sound, i.e., this minimum exists. (In other words, we should have defined $\tau^*$ as infimum, rather than minimum; with this definition, we need to show that an optimum fractional cover exists.)

06.55 ORD (4+4 points)   Let $\calH$ be a good hypergraph. Prove:   (a)   $\tau^*(\calH)\le \tau(\calH)$    and   (b)   $\nu(\calH) \le \tau^*(H)$.
($\nu(\calH)$ denotes the matching number of $\cal$.)

06.60 DEF   A fractional matching of a hypergraph $\calH=(V,\calE)$ is a function $g:\calE\to\rrr$ with following properties:

  (i)    $(\forall E\in \calE)(g(\calE) \ge 0)$
  (ii)   $(\forall u\in V)(\sum_{E: u\in E} g(E) \le 1)$

The value of the fractional matching $g$ is $\val(g)=\sum_{E\in \calE} g(E)$.

06.62 DO   Every hypergraph has a fractional matching.

06.65 DEF   The fractional matching number of a good hypergraph $\calH$ is
$$ \nu^*(\calH) = \max\{\val(f)\mid f\text{ is a fractional matching of }\calH\}\,.$$ For a bad hypergraph $\calH$ we set $\nu^*(\calH)=\infty$. (Why?)

We say that a fractional matching is optimum if its value is $\nu^*(\calH)$.

06.68 Bonus (4 points)   Prove that for every good hypergraph $\calH$, the definition of $\nu^*$ is sound, i.e., this maximum exists. (In other words, we should have defined $\nu^*$ as supremum, rather than maximum; with this definition, we need to show that an optimum fractional matching exists.)

06.70 ORD (4+8 points)   Prove:   For all hypergraphs $\calH$,   (a)   $\nu(\calH)\le \nu^*(\calH)$    and   (b)   $\nu^*(\calH) \le \tau^*(H)$.
Do not use Linear Programming concepts such as weak or strong duality.
Later we shall see that actually $\nu^*=\tau^*$ as a consequence of the Duality Theorem of Linear Programming.

06.75 ORD (5+5 points)   Let $\calH=(V,\calE)$ be a regular $r$-uniform hypergraph where $r\ge 1$. and $\calE\neq\emptyset$. Prove:   $\tau^*(\calH) = n/r$ and $\nu^*(\calH) = n/r$.
Do not use the fact that $\tau^*=\nu^*$ for every hypergraph. Use only lower-numbered exercises.
Hint.   Construct a fractional matching and a fractional cover, each of which has value $n/r$. Now the proof that both are optimum should be half a line with reference to a previous exercise.

06.80 Bonus (12 points, due Jan 30)   Let $\Pi_n$ denote the degenerate projective plane with $n\ge 3$ points. Determine $\tau^*(\Pi_n)$ and $\nu^*(\Pi_n)$.
Use the description of $\Pi_n$ given in Exercise 05.25.
Do not use the result that these two quantities are always equal; use only the definitions of these quantities.

06.90 DEF   Let $W$ be a real vector space (the domain of scalars if $\rrr$). A linear combination $\sum_{i=1}^m \alpha_i v_i$ of vectors $v_i\in W$ is a convex linear combination if the coefficients $(\alpha_1,\dots,\alpha_m)$ form a probability distribution, i.e.,
   (i)    $(\forall i)(\alpha_i\ge 0)$
   (ii)   $\sum_{i=1}^m \alpha_i = 1$

06.92 DEF   A set $S\subseteq\rrr^n$ is convex if $S$ is closed under convex combinations.

06.94 DO   The intersection of any (finite or infinite) set of convex sets is convex.

06.96 DEF   Let $a\in\rrr^n$, $r\neq 0$, and $\beta\in\rrr$. The set $\{x\in\rrr^n\mid a^Tx \le \beta\}$ is called a half-space. The intersection of a finite set of half-spaces is called a polytope.

06.98 DO   Every polytope is convex.

06.100 DEF   Let $x=(x_1,\dots,x_n)$ and $y=(y_1,\dots,y_n)$ be real vectors. We say that $x\le y$ if $(\forall i)(x_i\le y_i)$.

06.102 DO Let $A$ be a $k\times n$ real matrix and $b\in\rrr^k$. The set $\{x\in\rrr^n \mid Ax\le b\}$ is a polytope.

06.104 DEF   The Linear Programming problem (LP) takes as input a $k\times n$ real matrix $A$, a "constraint vector" $b\in \rrr^k$, and an "objective vector" $c\in\rrr^n$ and asks to compute $$ \sup\{c^Tx \mid x\in\rrr^n, Ax \le b\} \,.$$ The $k$ inequalities represented by $Ax\le b$ are the (linear) constraints and $c^Tx=c_1x_1+\dots+c_nx_n$ is the (linear) objective function.

The supremum above is called the optimum value of the LP.

A vector $z\in\rrr^n$ that satisfies the constraints is called a feasible solution. Note that the feasible solutions forma polytope. So the LP problem asks to optimize a linear objective function over a polytope.
If a feasible solution exists, we say that the LP is feasible.
A feasible solution $z$ is optimum if $c^Tz$ is equal to the optimum value. We also say that $z$ attains the optimum value.

06.106 CONVENTION   The supremum of the empty set is $-\infty$. This convention applies in particular to an infeasible LP.

06.108 DO   If the polytope of feasible solutions is bounded and non-empty then there exists an optimum solution.

06.110 Challenge   Prove: if the optimum value of the LP is finite (i.e., not $\pm\infty$) then there exists an optimum solution.

06.114 DEF   The standard form of the LP additionally assumes that $x\ge 0$ (every coordinate of $x$ is non-negative): $$ \sup\{c^Tx \mid x\ge 0 \text{ and }Ax \le b\} $$

06.118 DO   Solving all linear programs and solving standard-form LPs are computationally equivalent problems. Formalize and prove this statement.

06.125 DEF   Given the standard-form LP   $\sup\{c^Tx \mid x\ge 0 \text{ and }Ax \le b\} $, to which we refer as the primal LP, we define the dual LP as $\inf\{b^Ty \mid y\ge 0 \text{ and }A^Ty \ge c\} $.

06.130 ORD (Weak Duality Theorem, 8 points) Let $x$ be a feasible solution of the primal and $y$ a feasible solution of the dual. Prove:   $c^Tx \le b^Ty$.
Your solution should be just one line.

06.134 DO (Verification of optima)   ("Optima" is the plural of "optimum", from Latin.) Let $x$ be a feasible solution of the primal and $y$ a feasible solution of the dual. Prove:   If $c^Tx = b^Ty$ then $x$ is an optimum solution of the primal and $y$ is an optimum solution of the dual.

06.140 LP Duality Theorem   If the primal optimum is finite (note that this condition includes the feasibility of the primal LP) then the dual is also feasible and their optimum values are equal (so $x$ and $y$ as in the preceding exercise exist).

06.142 DO   If both the primal and the dual are feasible then their optima are equal. Use the Duality Theorem.

06.145 ORD (5+5 points, due Jan 30)   (a) Find a feasible primal LP such that the dual is not feasible. Make your LP as small as possible.   (b) Find and LP such that neither the primal nor the dual are feasible.   (In both problems, your LP has to be in standard form.)

06.150 ORD (10 points, due Jan 30)   Let $\calH$ be a good hypergraph. Prove that $\nu^*(\calH)=\tau^*(\calH)$. Use the LP Duality Theorem.

06.155 DEF   The integer linear programming (ILP) problem is the same as LP except we are only interested in integer solution. The $(0,1)$-ILP problem is also the same but we are only interested in $\{0,1\}$ solutions (the value of each variable is 0 or 1). The corresponding feasibility problems are defined analogously.

4.10 REVIEW   PROB Chap. 7.8 (Random variables, expected value, indicator variables)

In the next sequence of exercises, we fix a probability space $(\Omega, P)$.

4.20 DO   Let $A_1,\dots, A_k \subseteq\Omega$ be events. For $a\in\Omega$ we say that the event $a\in A_i$ is a "success." Let the random variable $X$ count the successes: $X(a)=|\{i\mid a\in A_i\}|$. Then $E(X)=\sum_{i=1}^k P(A_i)$.
Proof. Let $\vt_i$ denote the indicator of $A_i$. $X=\sum_{i=1}^k \vt_i$ and therefore $E(X)=\sum_{i=1}^k E(\vt_i) =\sum_{i=1}^k P(A_i)\,.$

4.23 DO   Let us flip $k$ biased coins; for each coin, the probability that the coin comes up Heads is $p$. Let $X$ denote the number of Heads. Prove:   $E(X) = pn.$

4.26 ORD (6+5 points, due Jan 23)   (a) PROB 7.8.15 (a) (expected number of Aces in Poker hand) Half the credit goes for a clear definition of the events or random variables used in the proof.   (b) What is the size of the sample space for this experiment?

4.30 Bonus (14+4 points, due Jan 23)   Let $X$ denote the number of Aces and $Y$ the number of Spades in a Poker hand. Prove that (a) $X$ and $Y$ are uncorrelated but (b) $X$ and $Y$ are not independent.

4.35 Bonus (18 points, due Jan 30)   Let $0\le k\le n$. Let us pick a random $k$-subset $A$ of $[n]$ uniformly from $\binom{[n]}{k}$. (So the sample space is $\binom{[n]}{k}$, and the distribution uniform.) Let $A=\{X_1,\dots,X_k\}$ where $X_1 < X_2 <\dots < X_k$. Note that each $X_i$ is a random variable. Determine the expected value of each $X_i$.
The answer should be a very simple expression in terms of $n,k$, and $i$. Elegance matters, there should be virtually no calculation involved.

4.40 STUDY (directed graphs) STUDY the concept of directed graphs, also called digraphs (DMmini Chap 6.4 "Digraph terminology", items 6.4.1--6.4.7). View the illustration after Exercise 6.4.33.

4.45 DEF (permutations)   Recall that a permutation of a set $\Omega$ is a bijection $\pi: \Omega\to \Omega$. If $\pi: \Omega\to \Omega$ is a permutation, we write $x^{\pi}$ instead of $\pi(x)$ for the value of $\pi$ at $x\in \Omega$. We say that $x\in \Omega$ is a fixed point of $\pi$ if $x^{\pi}=x$. The identity permutation $\iota$ is the permutation that fixes every point: $(\forall x\in\Omega)(x^{\iota}=x)$. The inverse of the permutation $\pi$, denoted $\pi^{-1}$, reverses its action: if $x^{\pi}=y$ then $y^{\pi^{-1}}=x$.
We denote the set of permutations of $\Omega$ by $\sym(\Omega)$ and call this set the symmetric group acting on $\Omega$. Here "group" refers to the operation of composition of functions one can apply to permutation: if $\pi,\sigma\in\sym(\Omega)$ then we define the permutation $\pi\sigma\in\sym(\Omega)$ by setting $x^{\pi\sigma} := (x^{\pi})^{\sigma}$.
$S_n$ denotes $\sym([n])$ and it is also used as a generic notation for the symmetric group acting on any set of size $n$. The order of a permutation is the smallest $k\in\nnn$ such that $\pi^k=\iota$.

4.45 DO Show that (a) the composition operation is associative:   $(\pi\sigma)\tau =\pi(\sigma\tau)$   (b) $\pi\pi^{-1}=\pi^{-1}\pi=\iota$,   if $|\Omega|=n$ then $|\sym(\Omega)|=n!$ (so $|S_n|=n!$).

4.50 DEF (permutation digraphs)   A permutation $\pi$ can be represented by a diagram (directed graph) on vertex set $\Omega$ where the set if edges is $\{(x,x^{\pi}) \mid x\in\Omega\}$. Note that (a) in a permutation digraph, every vertex has indegree 1 and outdegree 1 (b) such a digraph consists of a set of disjoint cycles. The cycle (or trajectory) of $x\in\Omega$ under $\pi$ is the sequence $(x, x^{\pi}, x^{\pi^2},\dots)$. The orbit of $x$ under $\pi$ is the set of vertices in the cycle containing $x$, i.e., $\orb(x,\pi)=\{x^{\pi^k}\mid k\in\zzz\}$. The length of the orbit is the length of this cycle, i.e., the size of the orbit. The length of the orbit of $x$ is called the period of $x$ under $\pi$, denoted $\per(x,\pi)$, so $\per(x,\pi)=|\orb(\pi)|$. In other words, the period of $x$ under $\pi$ is the smallest $k\in\nnn$ such that $x^{\pi^k}=x$ (the smallest number of iterations of $\pi$ that returns $x$ to its original position).

4.53 DO   Let $|\Omega|=n$.  (a) $1\le \per(x,\pi)\le n$ and any number in $[n]$ can be the period of $\pi$.   (b) $\per(x,\pi)=1$ if and only if $x$ is a fixed point of $\pi$. In this case the cycle of $x$ in the permutation digraph is a self-loop.   (c) The permutation digraph consists of a set of disjoint cycles to which we refer as the cycles of $\pi$. Note that the sum of the lengths of the cycles of $\pi$ is $n$.

4.56 DO   Prove: the order of $\pi\in\sym(\Omega)$ is the least common multiple of the lengths of its cycles.

4.60 DO   Review the Prime Number Theorem, the most celebrated asymptotic relation in all of mathematics (DMmini 2.2.11).

4.62 Reward   Let $P(x)$ denote the product of all prime numbers $\le x$. (E.g., $P(10)=2\cdot 3\cdot 5\cdot 7 = 210$.)
Prove that the Prime Number Theorem is equivalent to the statement that $P(x)=\eee^{x+o(1)}$. In other words, $\ln P(x) \sim x$.

4.64 Challenge   Let $r_n$ denote the maximum order of elements in $S_n$. Prove:   $\ln(r_n) \sim \sqrt{n\ln n}$.

4.68 ORD (8 points, due Jan 23)   For $\pi\in S_n$, let $\fix(\pi)$ denote the number of fixed points of $\pi$. Pick $\pi\in S_n$ at random from the uniform distribution. Determine $E(\fix(\pi))$.

4.70 ORD (8 points, due Jan 23)   Let $A$ be a set, $|A|=n$. Pick $\pi\in \sym(A)$ at random from the uniform distribution. Prove: for every $k\in [n]$ and every $x\in A$ we have $P(\per(x,\pi)=k)=1/n$.

4.75 Bonus (9 points, due Jan 23) (number of cycles in random permutation)   For $\pi\in S_n$, let $C(\pi)$ denote the number of cycles of $\pi$ (including the fixed points). Pick $\pi\in S_n$ at random. Prove:   $E(C(\pi))\sim \ln n$.

4.90 DEF (2D hypergrid)   We define the $r\times s$ hypergrid as a hypergraph with $rs$ vertices and $r+s$ edges as follows. Let $V=[r]\times [s]$ be the set of vertices, $\calE_1=\{[r]\times {j}]\mid j\in [s]\}$ the set of "vertical edges," and $\calE_2=\{{i}\times [s]\mid i\in [r]\}$ the set of "horizontal edges." Let $\hypergrid(r,s) = (V, \calE_1 \cup \calE_2)$.

4.93 ORD (10 points, due Jan 30)   Let $r,s\in\nnn$. Determine the matching number and the covering number of $\hypergrid(r,s)$. Your answers should be very simple expressions in terms of $r$ and $s$. For every $r,s$, answer the question whether $\nu(\hypergrid(r,s))=\tau(\hypergrid(r,s))$.

Remember: if for some hypergraph $\calH$ you claim that $\tau(\calH)=k$, you need to do two things: (1) exhibit a cover of size $k$, thereby proving that $\tau(\calH)\le k$, and (2) prove that your cover is optimal, i.e., prove that every cover $C$ has size $|C|\ge k$. Analogous statements hold for $\nu(\calH)$, $\alpha(\calH)$, $\chi(\calH)$, and more generally, for every parameter that is defined as the optimum value (maximum or minimum) of some quantity.

4.96 DEF (3D hypergrid)   We define the $r\times s\times t$ hypergrid as a hypergraph with $rst$ vertices and $rs+rt+st$ edges as follows. Let $V=[r]\times [s]\times [t]$ be the set of vertices, $\calE_1=\{[r]\times \{j,k\}]\mid j\in [s], k\in [t]\}$ the set of edges "in the first direction," $\calE_2=\{\{i\}\times [s]\times \{k\} \mid i\in [r], k\in [t]\}$ the set of edges "in the second direction," and $\calE_3=\{\{i,j\}\times [t]\mid i\in [r], j\in [s]\}$ the set of edges "in the third direction." Let $\hypergrid(r,s,t) = (V, \calE_1 \cup \calE_2\cup \calE_3)$.

4.100 Bonus (15 points, due Jan 30)   Let $r,s,t\in\nnn$. Determine the matching number and the covering number of $\hypergrid(r,s,t)$. Your answers should be very simple expressions in terms of $r,s,$ and $t$. For every $r,s,t$, answer the question whether $\nu(\hypergrid(r,s,t))=\tau(\hypergrid(r,s,t))$.
For a partial credit of 10 points, you may solve the case $r=s=t$.

03.10 DEF (revised)   A hypergraphs $\calH=(V,\calE)$ is a pair, consisting of a set $V$, called the set of vertices, and a set $\calE\subseteq \calP(V)$ (subset of the powerset of $V$), called the set of edges. (So the edges are subsets of $V$).
The difference compared to DEF 02.50 is that we do not permit repeated edges. $\calE$ is set (so it is unordered). If we write $\calE = \{E_1,\dots,E_m\}$ then the $E_i$ should be distinct.
Definitions 02.51--2.53 remain in force unchanged.

03.11 DEF   A graph is a 2-uniform hypergraph.

03.12 NOTATION   Unless otherwise stated, we write $n=|V|$ and $m=|\calE|$.

03.13 DEF (incidence relation)   We say that vertex $x\in V$ and edge $E\in\calE$ are incident if $x\in E$. The incidence relation is the set $I = \{(x,E)\mid x\in V, E\in\calE, x\in E\}$.
This is a relation between the sets $V$ and $\calE$:   $I\subseteq V\times \calE$. This relation is represented by the incindence matrix, see DEF 02.52.
This relation is also represented by a bipartite graph called the incidence graph or the Levy graph of the hypergraph. The two parts of the incidence graph are $V$ and $\calE$ (so both the vertices and the edges of $\calH$ become vertices of the incidence graph; these sets are considered to be disjoint, so the graph has $n+m$ vertices) and $x\in V$ and $E\in\cal E$ are adjacent in the incidence graph if they are incident in the hypergraph.

03.16 DO   Observe:   $0 \le m \le 2^n$. If $\calH$ is $r$-uniform then $0\le m \le \binom{n}{r}$.

03.19 DEF   Let $\calH=(V,\calE)$ and $\calK=(W,F)$ be two hypergraphs. We say that the function $f:V\to W$ is an isomorphism from $\calH$ to $\calK$ if $f$ is an edge-preserving bijction from $V$ to $W$, i.e., a subset $S\subseteq V$ is an edge in $\calH$ if and only if $f(S)$ is an edge in $\calK$.
We say that $\calH$ and $\calK$ are isomorphic (notation: $\calH\cong \calK$) if there exists an $f:\calH\to\calK$ isomorphism.

03.22 DEF   An automorphism of $\calH$ is a self-isomorphism ($\calH\to\calH$ isomorphism). The set of automorphisms of $\calH$ is denoted $\aut(\calH)$. This set of functions is closed under composition and inverses and includes the identity permutation; in sum, it is a group. If $x\in V$ and $\alpha\in\aut(\calH)$ then we write $x^{\alpha}$ (instead of $\alpha(x)$) for the image of $x$ under $\alpha$. (This notation is common in the theory of permutation groups.) The advantage of this notation is that the action of the composition $\alpha\beta$ (execute $\alpha$ first, then $\beta$) is defined as $x^{\alpha\beta}=(x^{\alpha})^{\beta}$, while in the usual functional notation it would be $\beta(\alpha(x))$.

03.25 DEF   The hypergraph $\calH=(V,\calE)$ is vertex-transitive if $(\forall x,y\in V)(\exists \alpha\in\aut(\calH))(x^{\alpha}=y)$. So in such a hypergraph, all vertices "look alike."

03.27 DO   (a) If a hypergraph is vertex-transitive then it is regular.  (b) The converse is false. Construct a regular graph that is not vertex-transitive. Make your graph as small as possible.

03.35 DEF   $K_n^{(r)} = (V,\binom{V}{r})$ is called the complete $r$-uniform hypergraph. So the edges are all $r$-subsets of $V$ and $m=\binom{n}{r}$.

03.38 NOTATION   $\sym(V)$ denotes the set of all permutations of $V$; it is called the symmetric group acting on $V$. It has order $n!$. (The order of a group is the number of its elements.)

03.40 DO   Note that $\aut(K_n^{(r)})=\sym(V)$. Conversely, if the automorphism group of a uniform hypergraph $\calH$ is the symetric group then $\calH$ is a complete uniform hypergraph.

03.45 DEF   $\calH=(V,\calE)$ is an intersecting hypergraph if $(\forall E, F\in\calE)(E\cap F\neq\emptyset)$.

03.48 DO   (a) If $\calH$ is intersecting then $m\le 2^{n-1}$.
(b) This upper bound is tight, i.e., for every $n$ there exists an intersecting hypergraph with $2^{n-1}$ edges.
Proof:   (a) For each $A\subseteq V$, only one among $A$ and its complement $\Abar = V\setminus A$ can belong to $\calE$.   (b) Fix $x\in V$. Let $\calE$ consist of all subsets of $V$ that include $x$.

03.50 DEF (maximal vs. maximum)   Let $\calF$ be a non-empty set of finite sets and let $F\in\calF$. We say that $F$ is a maximal member of $\calF$ if $F$ is not a proper subset of any member of $\calF$. We say that $F$ is a maximum member of $\calF$ if $|F|$ is maximal among the members of $\calF$.
So every maximum set is maximal but not conversely.
Example.   Consider the set of independent sets in a graph $G$. If $G=C_6$ (the 6-cycle), then the maximum independent sets have size 3 (and there are two such sets), but there are also three maximal independent sets of size 2 (pairs of opposite vertices).

03.51 DEF   We define minimal and minimum analogously.

03.53 ORD (7 points)   Let Oddtown have $n$ residents. We know that a maximum Oddtown club system consists of $n$ clubs. What is the size of the smallest maximal club system in Oddtown? In other words, how few clubs in Oddtwon can prevent the forming of any further clubs? (Your answer should depend on $n$. The size of a club system is the number of clubs.)

03.56 Challenge (DO NOT LOOK IT UP)   Every maximal Eventown club system is maximum. In other words, if an Eventown club system has fewer than $2^{\lfloor n/2\rfloor}$ clubs then a club can be added without violating the Eventown rules.

03.59 Bonus (8 points)   Prove: for sufficiently large $n$, there exist non-isomorphic maximum Eventown club systems (so not all maximum Eventown club systems are "married couples" systems).

03.65 ORD (10 points)   Prove: every maximal intersecting hypergraph is maximum.
In other words, if $m < 2^{n-1}$ for an intersecting hypergraph $\calH=(V,\calE)$ then an edge can be added to it (without adding any vertices) so that the resulting larger hypergraph $\calH'=(V,\calE')$ is still intersecting. (Here $\calE \subset\calE'.)

03.68 Bonus (18 points, due Jan 23)   Prove: the number of non-isomorphic maximum intersecting hypergraphs is a doubly exponential function of $n$. More specifically, prove that for all sufficiently large $n$, there are more than $\displaystyle{2^{1.9^n}}$ non-isomorphic intersecting hypergraphs with $2^{n-1}$ edges.

03.71 DEF   $\calH$ is triplewise intersecting if every two or three edges share a vertex. $\calH$ is $k$-wise intersecting if every $\le k$ edges share a vertex.

03.74 DO   If $\calH$ is triplewise intersecting then $m\le 2^{n-1}$ (because $\calH$ is pairwise intersecting). Moreover, this upper bound is tight: the sets containing a fixed element are triplewise intersecting (and $k$-wise intersecting for every $k$).

03.77 Bonus (15 points, due Jan 23)   Prove: If $\calH$ is triplewise intersecting and $m=2^{n-1}$ then all edges of $\calH$ share a vertex.

03.85   A subset $A\subseteq V$ is an independent set in the hypergraph $\calH=(V,\calE)$ if $A$ does not contain any edges, i.e., $(\forall E\in\calE)(E\not\subseteq A)$. The independence number of $\calH$, denoted $\alpha(\calH)$, is the maximum size of an independent set.
Note:   if $\emptyset\in\calE$ then there is no independent set in $\calH$. When speaking of the independence number of a hypergraph, we tacitly asume that $\emptyset\notin\calE$.

03.87 DO   For graphs: $\alpha(C_n)= \lfloor n/2\rfloor$.

03.90 ORD (5 points)   Determine $\alpha(K_n^{(r)})\,.$

03.95 DEF   A coloring of the set $V$ is a function $f:V\to\Sigma$ where $\Sigma$ is any set (we call it the set of colors). A coloring of the vertices of a hypergraph $\calH$ is a legal coloring if no edge is monochromatic (gets the just one color). The chromatic number of $\calH$, denoted $\chi(\calH)$ [Greek letter \chi], is the minimum number of colors needed for a legal coloring.
Note:   if there exists an edge $E\in\calE$ such that $|E|\le 1$ then $\calH$ has no legal coloring. When speaking of the chromatic number of a hypergraph, we tacitly asume that $(\forall E\in\calE)(|E|\ge 2)$.

03.97 DO   For graphs: $\chi(C_n)=2$ is $n$ is even and 3 if $n$ is odd.

03.100 DO   Prove: $\alpha(\calH)\cdot\chi(\calH)\ge n$.

03.102 DO   For all $n$, find a graph $G$ with $n$ vertices such that $\alpha(G)\cdot\chi(G)= \Omega(n^2)$.
So the lower bound given in 03.95 is far from tight.

03.105 Bonus (18 points, due Feb 6) (Mario Szegedy)   If $\calH$ is vertex-transitive then $\alpha(\calH)\cdot\chi(\calH)\le n(1+\ln(n))$.
So, for vertex-transitive hypergraphs, the lower bound given in 03.100 is nearly tight.
Note.   This problem was updated on Feb 18. Previously the right-hand side was given as $\lceil n\cdot\ln(n)\rceil$, which is optimistic.

03.110 Algorithmic aspects.   Both $\alpha$ and $\chi$ are NP-hard to compute, not only exactly, but even approximately up to ridiculously large $(n^{1-\epsilon})$ approximation factors, even for graphs. Specifically, let us take a pair of graphs as input. Assume one of the graphs satisfies $\alpha \le n^{\epsilon}$ and the other satisfies $\alpha \ge n^{1-\epsilon}$. If there is a polynomial-time algorithm that can tell, which graph is which, then P = NP. The exact same inapproxmability result holds for the chromatic number.

03.113 Greedy Independent Set algorithm   This algorithm produces a maximal independent set in a single pass through the input:
  initialize $S=\emptyset$
  for $x\in V$ add $x$ to $S$ unless this is prohibited ($S\cup\{x\}$ contains and edge)
  end(for)
  return $S$.

03.115 DO   Prove that the Greedy Independent Set algorithm indeed returns a maximal independent set.

03.120 Greedy coloring algorithm   This algorithm produces a legal coloring. It may be a very poor one.
Let the set of colors be the positive integers.
  Initially set every vertex "uncolored"
  for $x\in V$ color $x$ by the smallest available color, i.e., the smallest color that will not create a monochromatic edge
  end(for)
  return coloring.

03.122 DO   The nuber of colors used by Greedy Coloring heavily depends on the order in which we visit the vertices. Prove that for very hypergraph there is a numbering of the vertices that makes Greedy Coloring optimal.

03.124 DO   Prove: The Greedy Coloring algorithm produces an optimal coloring of each complete uniform hypergraphs (regardless of the numbering of the vertices).

03.130 DEF   A cover (or transversal, or hitting set) of the hypergraphs $\calH=(V,\calE)$ is a set $C\subseteq V$ such that $(\forall E\in\calE)(E\cap C\neq\emptyset)$. The covering number (or hitting number) of $\calH$, denoted $\tau(\calH)$ [Greek letter \tau] is the minimum size of a cover.
If $\emptyset\in\calE$ then there is no cover. So, when speaking of the covering number of a hypergraph, we tacitly assume that $\emptyset\notin\calE$.

03.133 ORD (5 points)   Prove:   $\alpha(\calH)+\tau(\calH) = n$.

03.140 Greedy Cover algorithm Given a hypergraph $\calH=(V,\calE)$, this algorithm produces a cover.
   Initialize $C$ to be the empty set
   while $\calE\neq\emptyset$, pick a vertex $x\in V$ of maximum degree, add $x$ to $C$
   update $\calH$ by removing all edges incident with $x$ from $\calE$
   end(while)
   return $C$

03.145 THEOREM (László Lovász, 1975) The Greedy Cover Algorithm produces a cover of size $|C|\le (1+\ln \deg_{\max}(\calH))\cdot\tau(\calH)$.
Here $\deg_{\max}(\calH) = \max_{x\in V} \deg_{\calH}(x)$.

This shows that the Greedy Cover algorithm gives a pretty good approximation to the covering number unless some vertices of the hypergraph have very large degree.

03.155 DEF   A matching in the hypergraph $\calH=(V,\calE)$ is a set of disjoint edges, $\calM\subseteq\calE$ such that if $E,F\in\calM$ and $E\neq F$ then $E\cap F=\emptyset$. The matching number of $\calH$, denoted $\nu(\calH)$ [Greek letter \nu], is the maximum size of a matching, i.e., the maximum number of disjoint edges.

03.158 ORD (4 points)   Prove:   $\nu(\calH) \le \tau(\calH)$.

03.162 DO   Design a Greedy Matching algorithm. The algorithm should produce a maximal matching in a single pass through the input.

03.160 ORD (3+3 points)   Determine   (a) $\tau(K_n^{(r)})$ and   (b) $\nu(K_n^{(r)})$.

03.165 ORD (7 points)   Let $\calH$ be an $r$-uniform hypergraph. Let $\calM$ be a maximal matching in $\calH$. Prove:   $\tau(\calH) \le r\cdot |\calM|$.
Note that it follows that $\tau(\calH) \le r\cdot \nu(\calH)$.

03.175 ORD (6 points)   Prove:   $\ln(n!) \sim n\ln n$. Do NOT use Stirling's formula. Use 01.125.

03.180 ORD (7 points, due Jan 23)   Compute the limit $\displaystyle{\lim_{n\to\infty} \eee^{-n}\left(1+\frac{1}{n}\right)^{n^2}}\,.$

03.188 DEF/DO   Let $A=(a_{ij})$ be a symmetric $n\times n$ matrix over $\rrr$. The quadratic form associated with $A$ is the function $Q_A: \rrr^n\to \R$ defined by the formula $$Q_A(\bfx) := \bfx^TA\bfx = \sum_{i=1}^n\sum_{j=1}^n a_{ij}x_ix_j\,,$$ where $\bfx = (x_1,\dots, x_n)^T\in \rrr^n$ is a column vector ($n\times 1$ matrix) and $T$ denotes the transpose. (We re[resent the elements of $\rrr^n$ as column vectors.) The "DO" part of this item is to verify that the two expressions given are indeed equal.

03.190 DEF   (continued) We say that $A$ is positive semidefinite if $(\forall \bfx\in\rrr^n)(Q_A(\bfx) \ge 0)$. We say that $A$ is positive definite if $(\forall \bfx\in\rrr^n)(\bfx\neq\bzo \Rightarrow Q_A(\bfx) > \bzo)$.

03.193 ORD (2+4 points)   Prove: (a) a real diagonal matrix is positive definite if and only if all diagonal entries are positive   (b) the $n\times n$ all-ones matrix $J_n=(1)_{i,j=1}^n$ (all entries are $=1$) is positive semidefinite.

03.195 DO   Let $A$ and $C$ be symmetric $n\times n$ real matrices. Prove: if $A$ is positive definite and $C$ is positive semidefinite then $A+C$ is positive definite.

03.197 ORD (5 points)   Prove: If $A$ is positive definite then $A$ is non-singular. Do not use eigenvalues; use a result from LinAlg, Chapter 4.1.

03.200 ORD (5 points)   Use the preceding sequence of exercises (03.188-03.197) to give a 2-line proof of 2.65.

02.10 REVIEW   all readings assigned in the Class #1 material.

02.13 STUDY   DMmini Chap 4.1, 4.2 (basic number theory)

02.16 STUDY   DMmini Chap 5.1 (binomial coefficients)

02.19 STUDY   DMmini Chap 6.1 (graph theory terminology)

02.21 STUDY   PROB Chap 7.5 (independence of several events)

02.30 ORD (7 points)  Let $G$ be a self-complementary graph with $n$ vertices, i.e., $G\cong \Gbar$. Prove:   $n\equiv 0$ or $1 \pmod 4$.

02.35 DO   Let $|V|=n$. Prove: the number of graphs with vertex set $V$ is $\displaystyle{2^{\binom{n}{2}}}$.

02.38 Bonus (12 points)   Let $g_n$ denote the number of non-isomorphic graphs with $n$ vertices. Prove:   $\log_2 g_n \sim n^2/2$.

02.40 DEF   A maximal independent set in a graph is an independent set that is not a proper subset of any other independent set.

02.42 Bonus (9 points)   For every $k\in\nnn$ construct a graph with $n=3k$ vertices that has $3^k$ maximal independent sets. The description of your graphs should be very simple.

02.50 DEF (see DEF 03.10 for a revision of this definition   A hypergraphs $\calH=(V,\calE)$ consists of a set $V$, called the set of vertices, and a list $\calE=\{E_1,\dots,E_m\}$ of subsets of $V$, called the edges (so $E_i\subseteq V$).

02.51 DEF   Let $\calH=(V,\calE)$ be a hypergraph, $\calE=\{E_1,\dots,E_m\}$. The degree of vertex $x\in V$ is $\deg(x)=|\{i\mid x\in E_i\}|$. The rank of an edge is its cardinality $|E_i|$. We say that the hypergraph is $d$-regular if every vertex has degree $d$. The hypergraph is regular if it is $d$-regular for some $d$. The hypergraph is $r$-uniform if every edge has rank $r$. The hypergraph is uniform if it is $r$-uniform for some $r$. We say that a hypergraph is intersecting if $(\forall i,j)(E_i\cap E_j\neq\emptyset)$.

Note that this definition permits repeated edges.

02.52 DEF   Let $\calH=(V,\calE)$ be a hypergraph, where $V=\{x_1,\dots,x_n\}$ and $\calE = \{E_1,\dots,E_m\}$. The incidence matrix $M=(m_{ij})$ of this hypergraph is an $m\times n$ $(0,1)$-matrix of which the rows are the incidence vectors of the edges (see Def. 1.30). In other words, $$m_{ij} = \begin{cases} 1 & \text{ if } x_j\in E_i\\ 0 & \text{ if } x_j \notin E_i\\ \end{cases} $$

02.53 DO   Let the $m\times m$ matrix $A=(a_{ij})$ be defined as $A=M\cdot M^T$ where $M$ is the incidence matrix of the hypergraph $\calH$ defined in the preceding exercise and $M^T$ denotes the transpose of $M$. Prove:   $a_{ij}=|E_i\cap E_j|$.
Note: This exercise will not help with the next two exercises, but it will help with another problem, assigned earlier.

02.54 Bonus (13 points, deferred to Jan 16)   Let $\calH=(V,\calE)$ be a regular, $r$-uniform intersecting hypergraph with at least one edge and at least two vertices. Prove:   $r > \sqrt{n}$.

02.56 Bonus (7 points)   Let $\calH=(V,\calE)$ be a hypergraph with $n$ vertices and $m$ edges. Let $\calE=\{E_1,\dots,E_m\}$. Assume every edge has rank $|E_i|\ge 6$ and for every $i\neq j$, $|E_i\cap E_j|\le 5$. Prove:   $m\le \binom{n}{6}$.

02.60 Bonus (15 points, deferred to Jan 16)   Let $q$ be a prime power (a number of the form $q=p^t$ for some prime $p$). Let $n,k\in\nnn$. Prove: if $q\mid \binom{n}{k}$ then $q\le n$. (Here $a\mid b$ means $a$ divides $b$, i.e., $(\exists x\in\zzz)(ax=b)$.)

02.65 Bonus (12 points)   Consider the $n\times n$ real matrix $$B=\begin{pmatrix} a_1 & b & b & \cdots & b \\ b & a_2 & b & \cdots & b \\ b & b & a_3 & \cdots & b \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ b & b & b & \cdots & a_n \\ \end{pmatrix}$$ Assume all entries are positive and $(\forall i)(a_i > b)$. Prove that $B$ is non-singular.

02.70 Bonus (12 points, due Jan 16)   Let $f(x)=a_0+a_1x+\dots+a_nx^n$ be a polynomial with real coefficients. We say that $f$ is a prime-exponent polynomial if only prime numbers actually occur as exponents, so if $k$ is not a prime then $a_k=0$. Example: $f(x)=6x^2-2x^7+18x^{23}$.
Assume $g$ is a nonzero polynomial (not all coefficients are zero). Prove: there exists a non-zero polynomial $h$ such that $gh$ is a prime-exponent polynomial.

More to follow, but not for the Jan 9 deadline. Please check back later.

01.10 STUDY   PROB Section 7.1 (Notation: sets, functions, strings, closed-form expressions). Please carefully study this section and refer back to it frequently to avoid misunderstandings.
The LaTeX code for the binomial coefficient $\binom{n}{k}$ is   $\tt \backslash binom\lbrace n\rbrace\lbrace k\rbrace$.

01.12 STUDY   PROB Section 7.2 (Finite probability spaces, events), Sec 7.3 (Conditional probability), Sec 7.4 (independence, positive and negative correlation of pairs of events), Sec 7.8 (random variables, expected value, indicator variables).

01.14 STUDY ASY (asymptotic equality) Sec 1 (Limit), Sec 2 (asymptotic equality), Sec 3 (properties of asymptotic equality)
LaTeX:   $a_n \sim b_n$:   $\tt a\_n \backslash sim~ b\_n$ ;   $a_n \gtrsim b_n$:   $\tt a\_n \backslash gtrsim~ b\_n$ ;   $a_n \lesssim b_n$:   $\tt a\_n \backslash lesssim~ b\_n$ .

01.16 STUDY DMmini Chap 1 (Quantifier notation, with some number theory: divisibility, congruence).
The LaTeX code for the congruence $a\equiv b \pmod m$ is $\tt a \backslash equiv~b \backslash pmod~m$.

01.18 STUDY DMmini Chap 2 (Asymptotic notation), Sections 2.1, 2.3, 2.4, 2.7. (Skip Sec. 2.2 because it is superseded by ASY.)
LaTeX: $\Theta$ is the capital Greek letter Theta, in LaTeX:   $\tt \backslash Theta$.

01.20 STUDY LinAlg Chapters 1--4 (matrices, rank, systems of linear equations)

01.22 STUDY LinAlg Chap 6 (determinants).

01.30 DEFINITION   Let $\Omega$ be a set. A $(0,1)$-function on $\Omega$ is a function $f: \Omega\to \{0,1\}$. In accordance with the notation in PROB, Chap. 7.1, the set of $(0,1)$-functions is denoted $\{0,1\}^{\Omega}$, or $\bbb^{\Omega}$, where $\bbb=\{0,1\}$. We identify $\bbb^{[n]}$ with the set $\bbb^n$ of $(0,1)$-strings (Boolean strings) of length $n$.
Let $A\subseteq\Omega$ be sets. The characteristic function of $A$ in $\Omega$ is the function $\vt_A:\Omega\to\{0,1\}$ defined by
      $\vt_A(x)= \begin{cases} 1 & \text{ if } x\in A\\ 0 & \text{ if } x\in\Omega\setminus A\\ \end{cases} $
Note that the correspondence $A\mapsto \vt_A$ is a natural bijection from $\calP(\Omega)$ to $\bbb^{\Omega}$. In particular, if $|\Omega|=n$ then $|\calP(\Omega)|=|\bbb^{\Omega}|=2^n$.
If $\Omega=[n]$ then we view the functions $f:\Omega\to\rrr$ as vectors $(x_1,\dots,x_n)$ where $x_i=f(i)$.
$(0,1)$-vectors are called incidence vectors. Accordingly, for $A\subseteq [n]$, the incidence vector of $A$ is the $(0,1)$-vector $a=(u_1,\dots,u_n)$ where $u_i=1$ if $i\in A$ and $u_i=0$ if $i\notin A$. We identify this vector with the function $\vt_A$.

01.32 NOTATION   Let $f,g:\Omega\to\rrr$ be functions. Then $fg$ (or $f\cdot g$) denotes their pointwise product: $(fg)(x)=f(x)g(x)$). So $fg$ is also a function: $fg: \Omega\to \rrr$.
If $\Omega$ is a finite set then $\langle f,g\rangle = \sum_{x\in\Omega} f(x)g(x)$ denotes the inner product (dot product) of $f$ and $g$. So $\langle f,g\rangle$ is a real number.

01.35 DO   If $A,B\subseteq\Omega$ then
  (a)    $\vt_A\cdot\vt_B=\vt_{A\cap B}$
  (b)  $\langle \vt_A,\vt_B\rangle= |A\cap B|\,.$

01.40 NOTATION   $M_n(\zzz)$ denotes the set of $n\times n$ integral matrices (matrices with integer entries).

01.43 DO   Let $A=(a_{ij})\in M_n(\zzz)$. Prove: $\det(A)\in \zzz$ (the determinant of an integral matrix is an integer).

01.46 DEF   Let $A=(a_{ij})$ and $B=(b_{ij})\in M_n(\zzz)$ be $n\times n$ integral matrices. Let $m\in\zzz$. We say that $A\equiv B\pmod m$ ($A$ and $B$ are congruent modulo $m$) if for all $i,j\in [n]$ we have $a_{ij}\equiv b_{ij}\pmod m$ (i.e., $m\mid a_{ij}-b_{ij}$).

01.50 DO   Let $A,B\in M_n(\zzz)$. Prove:   If $A\equiv B\pmod m$ then $\det(A)\equiv\det(B)\pmod m$.

01.53 ORD (4 points)   Let $A\in M_n(\zzz)$. Let $I_n$ denote the $n\times n$ identity matrix. Let $m\ge 2$. Prove: If $A\equiv I_n \pmod m$ then $A$ is non-singular.

01.60 DEF   Let $A_1,\dots, A_m \subseteq [n]$. We say that this list of sets is an Oddtown system if it satisfies the "Oddtown rules":
(i)    $(\forall i)(|A_i| \text{ is odd})$;
(ii)   $(\forall i\neq j)(|A_i\cap A_j| \text{ is even})$.

01.63 ORD (10 points).   Prove: If $A_1,\dots, A_m \subseteq [n]$ is an Oddtown system then the incidence vectors $v_i=\vt_{A_i}$ are linearly independent over $\rrr$.

01.65 DO (Oddtown Theorem, Elwyn Berlekamp, 1969).   Under the conditions of the preceding exercise, $m\le n$.
This is an example of a result in extremal combinatorics.

01.70 DEF   Let $A_1,\dots, A_m \subseteq [n]$. We say that this list of sets is an Eventown system if it satisfies the "Eventown rules":
(o)    $(\forall i\neq j)(A_i\neq A_j)$      (the sets are distinct)
(ii$^*$)   $(\forall i, j)(|A_i\cap A_j| \text{ is even})$.

01.72 DEF (floor, ceiling functions)   For $x\in\rrr$ we write $\lfloor x\rfloor$ (the "floor" of $x$) to denote the greatest integer $k$ such that $k\le x$. For instance, $\lfloor \pi\rfloor =3$,   $\lfloor -\pi\rfloor =-4$,   $\lfloor 7\rfloor =7$.
We write $\lceil x\rceil$ (the "ceiling" of $x$) to denote the least integer $\ell$ such that $\ell \ge x$. For instance, $\lceil \pi\rceil =4$,   $\lceil -\pi\rceil =-3$,   $\lceil 7\rceil =7$.

01.74 DO   For all $n$, find an Eventown system of $m=2^{\lfloor n/2\rfloor}$ sets. --- The next result shows that such a system is optimal.

01.76 Challenge (Eventown Theorem, Berlekamp, 1969)   If $A_1,\dots, A_m \subseteq [n]$ then $m\le 2^{\lfloor n/2\rfloor}$.

01.80 ORD (7+4 points)   We write $M_n(\rrr)$ to denote the set of $n\times n$ real matrices. Let $a,b\in\rrr$ and $n\ge 1$. Let $R_n(a,b)=(r_{ij})\in M_n(\rrr)$ denote the $n\times n$ matrix with $r_{ii}=a$ for all $1\le i\le n$ and and $r_{ij}=b$ for all $1\le i,j\le n$ where $i\neq j$. So each diagonal entry of the matrix is $a$ and each off-diagonal entry is $b$: $$R_n(a,b)=\begin{pmatrix} a & b & b & \cdots & b \\ b & a & b & \cdots & b \\ b & b & a & \cdots & b \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ b & b & b & \cdots & a \\ \end{pmatrix}$$ (a) Determine the value of $\det(R_n(a,b))$. Your answer should be a simple closed-form expression in terms of $n,a,b$. Show all your work. If you use elementary matrix operations, state, which ones you are using, in what order. Use the $(i,j,\lambda)$ notation defined in LinAlg, Def. 3.2.1 for column operations and $(i,j,\lambda)^T$ for the corresponding row operations. ("$T$" stands for "transpose.")   (b) For every $n\ge 1$, determine the set of all pairs $(a,b)\in\rrr^2$ such that $R_n(a,b)$ is singular, i.e., $\det(R_n(a,b))=0$. Give a very simple description of this set.

01.82 Bonus (12 points, due Jan 16) We have $n=2k+1$ weights $(k\in\nnn)$ (real numbers), $x_1,\dots,x_n$, such that if we remove any one of the weights, the remaining $2k$ weights can be split into two groups of $k$ weights each such that the two groups have equal total weight. Prove:   $x_1=\dots = x_n$. (You get half the credit if you prove this for rational weights.)
This is a beautiful exercise, DO NOT LOOK IT UP.

01.85 Bonus (14 points, due Jan 16) Let $A=(a_{ij})\in M_n(\rrr)$ be an $n\times n$ real matrix. Let $B=(a_{ij}^2)$. (We take the square of each matrix entry.) Prove: if the rank of $A$ is $r$ then the rank of $B$ is at most $\binom{r+1}{2}$.

01.88 DO   Let $0 \le k \le n/2-1$, where $k, n\in\nnn_0$. Prove:   $\binom{n}{k} < \binom{n}{k+1}$.

01.90 ORD (7 points, deferred to Jan 16)   Asymptotically evaluate the quantity $\displaystyle{r_n:=\binom{n}{\lfloor n/2\rfloor}}$. Your answer should be an asymptotic equality of the form $r_n \sim a\cdot n^b\cdot c^n$. Determine the constants $a,b,c$. Use Stirling's formula. Show your work. Solve the case of even $n$ first, then reduce the case of odd $n$ to the case of even $n$ in one line.

01.93 Bonus (9 points, due Jan 16)   Prove that for all $n\in\nnn$ we have $\displaystyle{\binom{n}{\lfloor n/2\rfloor} < \frac{2^n}{\sqrt{n}}}\,.$ While this inequality is asymptotically weaker than the precedig exercise, this inequality holds for all $n\ge 1$. The proof is completely elementary (high school stuff).

01.96 DEF (Newton's binomial coefficients)   Let $x$ be a real or complex number, and $k\in\nnn_0$. Then $$ \binom{x}{k} := \frac{x(x-1)\dots(x-k+1)}{k!}\,.$$ To emphasize the distinction between these functions and our combinatorially defined binomial coefficients, sometimes we shall refer to the latter as ordinary binomial coefficients, i.e., binomial coefficients of the form $\binom{n}{k}$ where $n,k\in\nnn_0$.

01.98 DO   Observe that Newton's definition, applied to $x\in \nnn_0$, gives the same value as the corresponding ordinary binomial coefficient.

01.100 ORD (5 points)   For $n,k\in\nnn_0$, express $\binom{-n}{k}$ as a very simple closed-form expression. Take our definition of closed-form expressions from PROB 7.1.4 with the understanding that "binomial coefficients" in that definition refer to ordinary binomial coefficients. (Otherwise there would be nothing to do.) Do not use factorials.

01.103 ORD (8 points)   For $k\in\nnn_0$, express $\binom{-1/2}{k}$ as a simple closed-form expression. Do not use factorials.

01.106 DO   Let $n,k\in\nnn_0$. Prove: $\binom{n}{k} \le \frac{n^k}{k!}$.

01.110 Bonus (9 points)   Let $\{a_n\}_{n=0}^{\infty}$ be a sequence of positive integers such that $a_n = o(\sqrt{n})$. (We are using the little-oh notation here, so the assumption means $\lim_{n\to\infty} a_n/\sqrt{n} = 0$.)
Prove: $\displaystyle{\binom{n}{a_n} \sim \frac{n^{a_n}}{a_n!}}$.
(Here we use $\sim$ to denote asymptotic equality, see ASY.)

01.112 DO   Prove: for all real numbers $x\neq 0$ we have $1+x < \eee^x$.

01.115 Bonus (8 points, due Jan 16)   Let $\{b_n\}_{n=0}^{\infty}$ be a sequence of positive integers such that $b_n = \omega(\sqrt{n})$. (Here we use the little-omage notation, so the assumption means $\lim_{n\to\infty} b_n/\sqrt{n}=\infty$.)
Prove: $\displaystyle{\binom{n}{b_n} = o\left(\frac{n^{b_n}}{b_n!}\right)}$.

01.120 ORD (7 points, deferred to Jan 16) Let $a_n, b_n$ be sequences of positive real numbers. Assume $a_n\to\infty$. Assume further that $a_n = \Theta(b_n)$. Prove:   $\ln a_n \sim \ln b_n$.

01.125 ORD (5 points) Prove:   For all $n\ge 1$ we have $n! > (n/\eee)^n$.
You cannot use Stirling's formula (because that formula would only prove it for sufficiently large $n$). Use the power series expansion of the exponential function.

01.127 NOTATION   Let $S(n,k) =\sum_{j=0}^{\infty} \binom{n}{jk}$.
This is not a generally used notation, just for this class.

01.129 ORD (4+4 points)   Prove: for $n\ge 1$ we have $S(n,2)=2^n/2$.
Give tow proofs. (a) A combinatorial proof: give a simple bijection from the even subsets of $[n]$ to the odd subsets of $[n]$. Elegance counts!   (b) An algebra proof: Use the Binomial Theorem.

01.131 Bonus (9 points, due Jan 16)   Prove: for all $n$, $$ \left|S(n,3) - \frac{2^n}{3}\right| < 1\,.$$ Elegance counts!

01.133 Bonus (7+4 points, due Jan 23)   PROB 7.1.12   (about $S(n,4)$).

01.135 ORD (4+3 points)   PROB 7.2.4 (a) (b) (coin flip sequences).

01.138 ORD (4 points)   PROB 7.2.10 (Full house) Briefly reason your answer.

01.140 ORD (5 points)   PROB 7.2.11 (a3) (coin flips)

01.142 ORD (6+4 points, due Jan 16)   PROB 7.2.12 (coin flips: even # heads)

01.145 DO   PROB 7.2.14 (modular equation)

01.147 DO   PROB 7.2.16 (union bound)

01.149 DO   PROB Chap 7.4 all exercises

01.151 DO   PROB 7.5.3--7.5.9 (independence of three events)

01.153 DEF   An event is balanced if it has probability $1/2$.

01.155 ORD (4+3 points, deferred to Jan 16) (a) Construct a probability space and three balanced events that are pairwise but not fully independent. Make your sample space as small as possible.   (b) Prove that your sample space is minimum size.

01.157 DO   PROB 7.5.14--7.5.18 (independence of multiple events)

01.159 ORD (8 points, due Jan 16)   PROB 7.5.19 (lower bound on the size of sample space for $k$ independent nontrivial events)

01.163 Bonus (6 points, due Jan 16)   PROB 7.5.20 ($(n-1)$-wise but not fully independent balanced events) Elegance counts.

01.166 Bonus (12+10 points, due Jan 23)   PROB 7.5.21 (small sample space for pairwise independent events)

01.168 Challenge   PROB 7.5.22 (ii) ($p$ pairwise independent balanced events with $n=p+1$ where $4\mid n$)

01.170 Challenge   PROB 7.5.23 (lower bound for pairwise independent events)

01.175 ORD (4 points)   PROB 7.8.5 ($\min X \le E(X)\le \max X$)

01.178 DO   PROB 7.8.3, 7.8.4, 7.8.6, 7.8.7 (Linearity of Expectation), 7.8.10, 7.8.11 (expected value of indicator variable).

01.180 ORD (8 points, deferred to Jan 16. Half the credit goes for an accurate definition of the random variables you introduce)   PROB 7.8.16 (runs of $k$ heads)

01.190 Bonus (7+3 points, due Jan 16)   Let $0 \le k, \ell \le n$. Let $A$ be a random $k$-subset of $[n]$ and $B$ a random $\ell$-subset of $[n]$, chosen uniformly and independently from $\binom{[n]}{k}$ and from $\binom{[n]}{\ell}$, respectively.   (a) Determine $E(|A\cap B|)$.   (b) What is the size of the sample space for this experiment?