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 Local Lemma. Application to 2-colorability of $r$-uniform hypergraphs where every edge intersects at most $c\cdot 2^r$ edges for some constant $c > 0$.

17.15 STUDY   Review exercises 14.15 and 14.20 below (recently updated). These exercises point to the proofs of the non-uniform and the uniform RW Theorems via spaces of polynomials, discussed in class.

17.20 DEF   Let $A_1,\dots,A_m$ be events and let $G=([m],E)$ be a graph. We write $i\sim j$ to denote that $\{i,j\}\in E$ and we say that $i$ and $j$ are adjacent. We say that $G$ is a dependence graph for $A_1,\dots,A_m$ if for every $i\in [m]$, the event $A_i$ is independent of the set $R_i=\{A_j\mid j\not\sim i\}$ of events.

17.25 THEOREM (Lovász Local Lemma, 1975)   Let $A_1,\dots,A_m$ be events and let $G$ be a dependence graph for these events. Let further $x_1,\dots,x_m\in\rrr$ such that $0 < x_i < 1$. Assume that for all $i$, $$\Pr(A_i) \le x_i \prod_{j:j\sim i} (1-x_j)\,.$$ Then $\Pr\left(\bigcap_{i=1}^m \Abar_i\right) \ge \prod_{i=1}^m (1-x_i)$.

17.31 ORD (12 points)   Let $r\ge 1$ and $v \ge 2r+1$. The Kneser graph $Kn(v,r)$ is defined to have vertex set $V(v,r)= \binom{[v]}{r}$. Two vertices $A,B\in V$ are adjacent if $A\cap B=\emptyset$. Determine $\alpha(Kn(v,r))$. Prove your answer by appropriate reference to a theorem proved in class and in homework. Do not attempt to prove it from scratch.

17.36 BON (22 points)   Let $L=\{\ell_1,\dots,\ell_s\}$ be a set of non-negative integers with greatest common divisor $d$. Let $\calH$ be a $k$-uniform $L$-intersecting hypergraph with $n$ vertices and $m$ edges. Assume $d$ does not divide $k$. Prove:   $m\le n$.

17.41 BON (18 points)   Let $A_1,\dots,A_m$ be events and let $G$ be a dependence graph for these events. Assume that for all $i$,   $\Pr(A_i) \le 1/2$ and $\sum_{j:j\sim i}\Pr(A_j) \le 1/4$. Then $\Pr\left(\bigcap_{i=1}^m \Abar_i\right) > 0$.

17.46 ORD (9 points)   A homogeneous polynomial of degree $d$ is a linear combination of monomials of degree $d$. For instance, the polynomial $4x_1x_2x_3 + 7x_2^3$ is homogeneous of degree 3, and the polynomial $4x_1x_2x_3^2 + 7x_2^3$ is not a homogeneous polynomial. The zero polynomial counts as a homogeneous polynomial of all degrees. Let $\Hom_{\fff}(n,d)$ denote the space of homogeneous polynomials of degree $d$ in $n$ variables over the field $\fff$. Show that the dimension of this space is $\binom{n+d-1}{d}$.

17.51 BON (10 points)   Let $A=(a_{i,j})$ be a $k\times\ell$ matrix of rank $r$ over the field $\fff$. Let $B=(a_{i,j}^d)$ (we raise every entry of $A$ to the $d$-th power). Prove that the rank of $B$ is at most $\binom{r+d-1}{d}$.

17.XX  

17.XX  

17.XX  

17.XX  

More to follow. Please check back later.

Material covered:  Asymptotics of the Birthday paradox. Smallest non-2-colorable $r$-uniform hypergraph via Lovász integrality gap (full proof). Erdős--Ko--Rado Theorem: sketch of proof by Gyula Katona via variation of Lubell's permutation method.

16.13 DEF   Let $f:A\to B$ be a function. A collision is a pair $\{x,y\}$ such that $x,y\in A$, $x\neq y$, and $f(x)=f(y)$. We say that $f$ is injective (or $f$ is an injection) if $f$ has no collisions, i.e., $(\forall x,y\in A)(f(x)=f(y)\Rightarrow x=y)$.

16.15 DO   For $1\le k\le n$ let $p(n,k)$ denote the probability that a random function $f:[k]\to [n]$ is injective. Then
  (a)   $p(n,k) > p(n,k+1)$
  (b)   $p(n,1) = 1$ (assuming $n\ge 2$)
  (c)   $p(n,n) = n!/n^n \sim \eee^{-n} \sqrt{2\pi n}$.

16.18 DO   (continued) $$ p(n,k) = \prod_{i=1}^{k-1} \left(1-\frac{i}{n}\right)\,.$$ The birthday paradox asks to determine the value $k$, as a function of $n$, when $p(n,k+1) < 1/2 \le p(n,k)$.

16.21 Notation   $\exp(x) = \eee^x\,.$

16.23 DO   (Birthday paradox continued)   Prove: $$ p(n,k) < \exp\left(-\frac{1}{n}\binom{k}{2}\right)\,.$$

16.26 DO   Let $0 < a_1,\dots,a_k < 1$. Prove:   $\prod_{i=1}^k (1-a_i) \ge 1 - \sum_{i=1}^k a_i$.

16.29 DO   (Birthday paradox continued)
$$ p(n,k) \ge 1- \frac{1}{n}\binom{k}{2}\,.$$ 16.27 DO   (Birthday paradox continued)
Let $1 \le k_n \le n$. If $k_n=\omega(\sqrt{n})$ (i.e., $k_n/\sqrt{n} \to\infty$) then $p(n,k_n)\to 0$.
In words, we say that the random function $f_n: [k_n]\to [n]$ is almost surely not injective.

16.29 DO   (continued)   If $k_n=o(\sqrt{n})$ (i.e., $k_n/\sqrt{n} \to 0$) then $p(n,k_n)\to 1$ ($f_n$ is almost surely injective).

16.32 BON (2+10 points)   (continued)   If $k_n=\Theta(\sqrt{n})$ then both $p(n,k_n)$ and $1-p(n,k_n)$ are bounded away from zero, i.e., there exists a positive constant $c$ such that for all sufficiently large $n$,   $c\le p(n,k_n) \le 1-c$.
(2 points for the upper bound, 10 points for the lower bound.)

16.40 STUDY   DMmini Chap 3 (convex functions and Jensen's Inequality).

16.42 DEF   For an integer $k\ge 0$ and a real or complex number $x$ define the Newtonian binomial coefficient $$\binom{x}{k} = \frac{\prod_{i=0}^{k-1} (x-i)}{k!}\,$$ We say that $\binom{x}{k}$ is an ordinary binomial coefficient if $x$ is an integer and $k\le x$.

16.45 ORD (6+6 points)   (a)   Express the Newtonian binomial coefficient $\binom{-1/2}{k}$ as a closed-form expression as defined PROB Chap. 7.1. So you are allowed to use ordinary binomial coefficients in the closed-form expression.   (b)   Asymptotically evaluate $\binom{-1/2}{k}$ in the form $a\cdot b^k\cdot k^c$ for some constants $a,b,c$. Determine and explicitly state the values $a,b,c$.

16.48 BON (12 points)   Let us say that a polynomial $f\in\rrr[x]$ is integer-preserving if $(\forall z\in\zzz)(f(z)\in\zzz)$. (Integer input gives integer output.) Prove: $f\in\rrr[x]$ is integer-preserving if and only if $f$ is an integral linear combination of Newtonian binomial coefficients, i.e., $f(x)$ can be written as a sum of the form $\sum_{k=0}^n c_k\binom{x}{k}$ where $c_k\in\zzz$.

16.51 ORD (11 points)   Prove that the Newtonian binomial coefficient $\binom{x}{k}$ is a convex function on the domain $x\in [k-1,\infty)$.
Note that this will imply that for $x_1,x_2\ge k-1$ we have $$\binom{\frac{x_1+x_2}{2}}{k} \le \frac{\binom{x_1}{k}+\binom{x_2}{k}}{2}\,.$$ This fact was used in Lovász's proof of Erdős's result that there exist non-2-colorable $r$-uniform hypergraphs with $O(r^2 2^r)$ edges.

16.61 BON (18 points) (Katona's Lemma)   A $k$-arc on the $n$-cycle $C=(x_0,x_1,\dots,x_{n-1})$, where the $x_i$ are distinct, is a subset of the form $\{x_j,x_{j+1},\dots,x_{j+k-1}\}$ where the subscripts are interpreted in $\zzz_n$ (i.e., modulo $n$, so $x_{n-1}$ is followed by $x_0$).
Prove: if $k\le n/2$ and $A_1,\dots,A_m$ are distinct, pairwise intersecting $k$-arcs of the $n$-cycle $C$ then $m\le k$.
Conceptual clarity of the proof is paramount.
Note. This lemma was used in Katona's proof of the Erdős--Ko--Rado Theorem.

16.65 (Erdős--Ko--Rado Theorem)   We say that a hypergraph is intersecting if each pair of edges shares a vertex. Let $r\ge 1$ and $n\ge 2r$. Let $\calH$ be an $r$-uniform intersecting hypergraph with $n$ vertices and $m$ edges. Assume $n \ge 2r$. Then $m\le \binom{n-1}{r-1}$.

16.XX  

16.XX  

More to follow. Please check back later.

Material covered:  LP Duality Thorem stated. $\nu^*=\tau^*$. Greedy cover algorithm. Fractional vs. integral cover: Lovász's integrality gap (full proof).

15.XX  

More to follow. Please check back later.

Material covered:  Multivariate polynomials, spaces of polynomials. Monomials. Polynomial functions. Non-uniform RW Theorem proved using spaces of polynomials (full proof). RW Theorem proved using spaces of polynomials (full proof).

14.15 STUDY   Babai--Frankl book "Linear Algebra Methods in Combinatorics" (click Texts on the banner), Theorem 5.34 (non-uniform RW Theorem), proof by spaces of polynomials.

14.20 STUDY   Babai--Frankl book, Theorem 5.35 (RW Theorem), proof by spaces of polynomials.

14.XX  

14.XX  

14.XX  

More to follow. Please check back later.

Material covered:   Inclusion--Exclusion formula: two proofs: using the Binomial Theorem and using linearity of expectation. -- Ray-Chaudhuri--Wilson Theorem (stated). Higher incidence matrices: inclusion matrix. Nonuninform RW theorem (Frankl--Wilson) (stated). Alternative approach: spaces of polynomials.

13.15 Inclusion--Exclusion formula   Let $(\Omega,\Pr)$ be a finite probability space and let $A_1,\dots,A_n\subseteq\Omega$ be events. Let $B = \overline{\bigcup_{i=1}^n A_i}$ (the complement of the union of of the $A_i$). Then $$\Pr(B) = \sum_{I\subseteq [n]} (-1)^{|I|}\Pr\left(\bigcap_{i\in I} A_i\right)\,.$$ Check the slides for the two proofs discussed.

13.18 DO   Note that this sum has $2^n$ terms. What is the term corresponding to $I=\emptyset$?

13.21 DO (Inclusion--Exclusion continued)   For $0\le j\le n$ let $$ S_j = \sum_{I\subseteq [n], |I|=j} \Pr\left(\bigcap_{i\in I} A_i\right)\,.$$ Then $$ \Pr(B) = \sum_{j=0}^n (-1)^j S_j\,.$$

13.24 BON (15 points) (Bonferroni's inequalities)   For $0\le k\le n$ let $T_k = \sum_{j=0}^k (-1)^j S_j\,.$   (a)   If $k$ is even then $P(B) \le T_k$.   (b)   If $k$ is odd then $P(B) \ge T_k$.  

13.27 ORD (10 points)   Let $1\le k\le n$. Consider the set $[k]^{[n]}$ of functions $f:[n]\to [k]$ with the uniform distribution. Let $R(n,k)$ denote the probability that a random function $f\in [k]^{[n]}$ is surjective. Express $R(n,k)$ as a simple formula using Inclusion-Exclusion. You have to clearly define the set of events to which you apply Inclusion-Exclusion. Your formula will not be closed-form, but for every fixed $k$ it should be a closed-form expression. Explicitly describe $R(n,5)$.

13.29 ORD (12 points, due May 15)   Consider the symmetric group $S_n$ with the uniform distribution. Let $Q(n)$ denote the probability that a random permutation $\sigma\in S_n$ is fixed-point-free (has no fixed point)? Give a simple formula using Inclusion--Exclusion. You have to clearly define the set of events to which you apply Inclusion-Exclusion. Prove: $\lim_{n\to\infty} Q(n) = 1/\eee$.

13.XX

13.33 DEF   Let $x_1,\dots,x_n$ be variables. An expression of the form $m(\bfx)=\prod_{i=1}^n x_i^{k_i}$ is called a monomial, where $k_i\in\nnn_0$. The degree of $m(\bfx)$ is $\sum_{i=1}^n k_i$. A polynomial over the field $\fff$ is a (formal) linear combination of monomials with coefficients from $\fff$. The degree of a polynomial is the largest degree of the monomials appearing with nonzero coefficient in this linear combination. If all coefficients are zero, we have the zero polynomial which has degree $-\infty$. The set of polymnomial in $n$ variables over $\fff$ is denoted $\fff[x_1,\dots,x_n]$. This set is an algebra, i.e., it is both a vector space and a ring, with the additional "mixed associativity" identity: if $f,g$ are polynomials and $a\in\fff$ is a scalar then $a(fg)=(af)g = f\cdot(ag)$. Viewed as a vector space, by definition, the monomials form a basis of $\fff[x_1,\dots,x_n]$. (This basis is an infinite set.)

13.35 DO   (a)   $\deg(f)=0$ if and only if $f$ is a nonzero constant polynomial.   (b)   Let $f,g\in\fff[x_1,\dots,x_n]$. Then $\deg(fg)=\deg(f)+\deg(g)$ and $\deg(f+g)\le \max(\deg(f),\deg(g))$.

13.38 DO/ORD (10 points)   We shall write $\fff^{\le d}[x_1,\dots,x_n]$ for the set of polynomials of degree $\le d$.   (a)   $\fff^{\le d}[x_1,\dots,x_n]$ is a subspace of $\fff[x_1,\dots,x_n]$.   (b)   Determine the dimension of this subspace. Your answer should be a simple closed-form expression in terms of $n$ and $d$.
(You find the definition of "closed-form expression" in PROB Chap. 7.1.)

13.41 DO   Let $\fff$ be a field and $\Omega$ a set. Consider the set $\fff^{\Omega}$ of functions $f:\Omega\to\fff$.   (a)   This is a vector space over $\fff$.   (b)   If $\Omega$ is finite then the dimension of this space is $|\Omega|$.

13.43 ORD (9 points) (continued)   Let $f_1,\dots,f_m\in \fff^{\Omega}$ and let $a_1,\dots,a_m\in\Omega$. Consider the $m\times m$ matrix $A=(f_i(a_j))$. Prove: if $A$ is non-singular (i.e., $\rank(A)=m$) then the functions $f_i$ are linearly independent.

13.45 DO (continued)   Let $f_1,\dots,f_m\in \fff^{\Omega}$ and let $a_1,\dots,a_m\in\Omega$. Prove: if $(\forall i)(f_i(a_i)\neq 0)$ and $(\forall i < j)(f_i(a_j)=0)$ then the functions $f_i$ are linearly independent.

13.47 DEF   Recall that we write $\nnn_0$ to denote the set of non-negative integers. Let $L\subseteq \nnn_0$. Let $\calE=(E_1,\dots,E_m)$ be a multiset of sets, and let $\calH=(V,\calE)$ be a multi-hypergraph. We say that $\calH$ is $L$-intersecting if $(\forall i\neq j\in [m])(|A_i\cap A_j|\in L)$.

13.49 THEOREM (Dijen K. Ray-Chaudhuri--Richard M. Wilson, 1964)   Let $|L|=s$ and let $\calH$ be a $k$-uniform $L$-intersecting hypergraph with $n$ vertices and $m$ edges. Assume $s\le k$. Then $m \le \binom{n}{s}$.

13.51 DO   Show that this inequality is tight for all $n$ and $s$ in the sense that, given $n$ and $s\le n$, there exist $k$ ($s\le k\le n$) and a set $L\subseteq\nnn_0$ of size $s$ such that there exists a $k$-uniform $L$-intersecting hypergraph with $n$ vertices and $m=\binom{n}{s}$ edges.
Update [May 21 at 19:00]. The original posting mistakenly required $k$ also to be given. This is obviously false if $s < n/2$ and $k > n-s$. A less straightforward class of counterexamples appears in the next exercise.

13.52 DO Let $|L|=2$ and let $\calH$ be a $3$-uniform $L$-intersecting hypergraph with $n\ge 6$ vertices and $m$ edges. Then $m \le \binom{n-1}{2}$.
Therefore the RW inequality is not tight for $s=2$, $k=3$, and any $n\ge 6$.

13.53 THEOREM (Nonuniform RW theorem) (Peter Frankl--Richard M. Wilson, 1980)   Let $|L|=s$ and let $\calH$ be an $L$-intersecting hypergraph with $n$ vertices and $m$ edges. Then $m \le \sum_{j=0}^s \binom{n}{j}$.

13.55 DO   Show that this inequality is tight for all $n$ and $s$ in the sense that, given $n,s$ there exists a set $L\subseteq\nnn_0$ of size $s$ and there exists an $L$-intersecting hypergraph with $n$ vertices and $m= \sum_{j=0}^s \binom{n}{j}$ edges.

13.XX  

13.59 DEF   Let $\Pi=(\calP,\calL,I)$ be a finite projective plane. Let $f:\calP\to\calL$ be a bijection.
  (a)   $f$ is a polarity of $\Pi$ if $$(\forall p\in \calP)(\forall \ell\in\calL) (p\incid \ell \Leftrightarrow f^{-1}(\ell)\incid f(p))\,.$$ Polarities are also called dual self-isomorphisms.
  (b)   The point $p\in\calP$ is called a fixed point of the polarity $f$ if $p\incid f(p)$.

13.62 DO   Let $\Pi=(\calP,\calL,I)$ be a finite projective plane of order $n$. Let $N=n^2+n+1$ and let $\calP=\{p_1,\dots,p_N\}$ and $\calL=\{\ell_1,\dots,\ell_N\}$. Let $M$ be the incidence matrix of $\Pi$ defined by these numberings of $\calP$ and $\calL$. Consider the bijection $p_i\mapsto\ell_i$. Prove:
  (a)   This bijection is a polarity if and only if $M$ is a symmetric matrix.
  (b)   This bijection is fixed-point-free if and only if all diagonal elements of $M$ are zero.

13.65 Theorem (Reinhold Baer)   No finite projective plane has a fixed-point-free polarity.

13.68 BON (25 points, due May 15)   Prove Baer's theorem. DO NOT LOOK IT UP.   Hint.   Eigenvalues.

13.71 DEF   A friendship graph is a graph in which every pair of distinct vertices has exactly one common neighbor.

13.74 DEF   The   flower graph $\calF_k$ consist of $k\ge 0$ triangles attached at a common vertex. So this graph has $n=2k+1$ vertices and $3k$ edges; one of the vertices is adjacent to all other vertices.

13.77 DO   The flower graphs are friendship graphs.

13.81 Friendship Theorem (Alfréd Rényi, Pál Turán, Vera T. Sós)   The only friendship graphs are the flower graphs.

13.84 BON (14 points, due May 15)   Use Baer's theorem to prove the Friendship Theorem. DO NOT LOOK IT UP.

13.XX  

13.XX  

13.XX  

More to follow. Please check back later.

Material covered:   Systems of Distint Representatives: Philip Hall's conditions (1935), good characterization, Dénes Kőnig's 1931 theorem: $\tau=\nu$ for bipartite graphs. Dénes Kőnig's 1916 theorem: Every non-empty regular bipartite graph has a perfect matching ($\nu = n/2$). Consequence: Every Latin Rectangle can be extended to a Latin Square. Marshall Hall's (1940s) lower bound on the number of matchings, consequent lower bound on the number of Latin Squares. Permanent. $(0,1)$-permanent counts perfect matchings. Doubly stochastic matrices. The Permanent Inequality. --- Positive (semi)definite matrices. An elegant proof of the Fisher-Bose Theorem.

12.15 BON (15 points, due May 15) (Miklós Abért)   Let $\fff$ be a field and $A_1,\dots,A_m, B_1,\dots,B_m$ be $n\times n$ matrices over $\fff$. Assume $$(\forall i,j\in [m])(A_i \text{ and } B_j \text{ commute } \Leftrightarrow \quad i\neq j)$$ Prove:   $m\le n^2$.
Hint.   Prove that $A_1,\dots,A_m$ are linearly independent in $\fff^{n^2}$.

12.19 STUDY   LinAlg Chap. 2.4 (Permutation matrices)

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

12.25 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$.

12.141 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.

12.28 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.

12.31 THEOREM ("Marriage Theorem," 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.

12.34 THEOREM (Dénes Kőnig's Duality Theorem (1931) Let $G$ be a bipartite graph. Then $\tau(G)= \nu(G)$.

12.37 BON (10 points)   Derive the Marriage Theorem from Kőnig's Duality Theorem.

12.40 Historical remarks.  Kőnig's Duality Theorem is one of the central results of combinatorial optimization, anticipating combinatorial duality theory; the method used by Kőnig's 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) himself had discovered the Kőnig--Egerváry theorem (in the context of determinants); his paper was published posthumously in Latin in 1890.

12.45 THEOREM (Dénes Kőnig, 1916)   Let $r\ge 1$. Every $r$-regular $r$-uniform multi-hypergraph has a SDR.

12.48 DO   Derive Kőnig's 1916 theorem (12.45) from Hall's Marriage Theorem (12.31).

12.51 DEF   Let $1\le k\le n$. Let $\Sigma$ be a set of $n$ symbols. A $k\times n$ Latin rectangle is a $k\times n$ matrix in which every row contains exactly one of each elements of $\Sigma$, and every colun contains at most one of each elements of $\Sigma$ (so all entries of the matrix are elements of $\Sigma$ and no element is repeated in any row and any column).

12.54 ORD (9 points)   Prove: every Latin rectangle can be extended to a Latin square. Use Kőnig's 1916 theorem.

12.57 BON (11 points) Prove the following stronger version of Kőnig's 1916 theorem.
Let $r\ge 1$. Let $\calH=(V,\calE)$ be a multi-hypergraph. Assume every vertex has degree $\le r$ and every edge $E\in\calE$ has rank $|E|\ge r$. Prove: $\calE$ has a SDR. Use the Marriage Theorem.
Update [May 3, 13:10]   "multi" added.

12.54 CH (Marshall Hall, Jr)   Let $r\ge 1$. Prove: an $r$-regular $r$-uniform hypergraph has at least $r!$ SDRs. (Do not use the Permanent Inequality below.)

12.57 NOTATION   Let $L(n)$ denote the number of $n\times n$ Latin Squares.

12.59 DO   $L(n)\le (n!)^n < n^{n^2}$.
Consequently, $\ln L(n) < n^2 \ln n$.

12.61 DO   Use the preceding problem to show that $L(n) \ge \prod_{j=1}^n j!$.

12.64 ORD (10 points) Prove:   $\ln(\prod_{j=1}^n j!)\sim (1/2)n^2\ln n$.

Comment.   In the light of the preceding two exercises it follows that $$ (1/2) n^2 \ln n \lesssim \ln L(n) < n^2 \ln n\,.$$ This gap of a factor of 2 was closed by the Permanent Inequality (below), showing that the trivial upper bound is asymptotically tight.

12.78 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.

12.81 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.

12.84 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!$, where $J$ is the all-ones matrix.

12.86 DO (permanent counts SDR's)   Let $\calH$ be a multi-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$.

12.95 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^{\tr}$ 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.

12.98 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.

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

12.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.)

12.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.

12.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}}$.

12.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).

12.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, using only linear algebra, can be found in the book by Van Lint and Wilson (listed on the course home page - click "Texts" on the banner).

12.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.)

12.129 BON (8 points)(log-asymptotics of the number of Latin squares) Let $L(n)$ denote the number of $n\times n$ Latin squares. Prove:   $\ln L(n) \sim n^2\,\ln n$.

12.XX  

12.XX  

More to follow. Please check back later.

Material covered:   Linear algebra "AH-HA" solution to the hypergraph truncation problem. (Check the SLIDES, they have been revised after class.) Finite probability spaces: Markov's and Chebyshev's inequalities. Chromatic number of almost-non-intersecting 3-uniform hypergraphs can be large: 21st century explicit construction (stated), 1960s probabilistic proof of existence (Erdős) given in detail (see the SLIDES; observe how Markov's inequality is used in the proof).

11.10 STUDY   PROB Chap 7.10 (Variance, covariance, Chebyshev's Markov's and Chebyshev's inequalities), Chapters 7.11, 7.12 (independence of random variables).

11.XX  

11.XX  

11.XX  

11.XX  

11.XX  

11.XX  

More to follow. Please check back later.

Material covered:   Permutations. The symmetric group $\sym(\Omega)$. Order, degree. $S_n$. Subgroup. Permutation groups acting on the set $\Omega$: subgroups of $\sym(\Omega)$. Orbit partition of the permutation domain. Transitive permutation group. Stabilizer subgroup. Orbit-stabilizer lemma. Cycle decomposition of a permutation. Order of a permutation. Automorphism group of a hypergraph. Automorphism group of finite projective planes. --- Independence of events. Atoms. Independence of random variables. Pairs of positively/negatively correlated/uncorrelated random variables. Covariance, variance.

10.15 DEF   A permutation of a set $\Omega$ is a bijection $\sigma:\Omega\to \Omega$. We say that $\sigma$ acts on $\Omega$. We call $\Omega$ the permutation domain on which $\sigma$ acts. If $x\in \Omega$ then we say that $\sigma$ takes (or maps) $x$ to $x^{\sigma}$ and we write $\sigma:x\mapsto x^{\sigma}$. We say that $x$ is a fixed point of $\sigma$ if $x^{\sigma}=x$. The support of $\sigma$, denoted $\supp(\sigma)$, consists of those elements of $\Omega$ that are not fixed by $\sigma$: $$ \supp(\sigma) = \{x\in\Omega\mid x^{\sigma} \neq x\}\,.$$ We say that two permutations are disjoint if their supports are disjoint.

10.18 DEF   If $\sigma$ and $\tau$ are permutations acting on $\Omega$ then we define the composition $\sigma\tau$ by $x^{\sigma\tau}=(x^{\sigma})^{\tau}$. The set of permutations acting on $\Omega$ is the symmetric group $\sym(\Omega)$. This is a group under composition. We denote its identity element by $\id_\Omega$, so $(\forall x\in \Omega)(x^{\id_\Omega}=x)$. If $x^{\sigma}=y$ then the inverse $\sigma^{-1}$ takes $y$ to $x$. If $|\Omega|=n$, then the order (number of elements) of $\sym(\Omega)$ is $n!$ and we say that its degree is $n$ (the number of elements on which it acts). The symmetric group of degree $n$ is also generically denoted $S_n$ if we do not want to specify the permutation domain, or think of the permutation domain being the set $[n]$.

10.18 DO   (a)   Show that disjoint permutations commute: if $\supp(\sigma)\cap \supp(\tau)=\emptyset$ then $\sigma\tau = \tau\sigma$.   (b)   Find two non-disjoint permutations that commute.

10.20 DEF (cyclic permutations)   For $k$ distinct elements $a_0,\dots,a_{k-1}$ of the permutation domain, we write $\sigma=(a_0,\dots,a_{k-1})$ to denote the permutation that takes each $a_i$ to $a_{i+1}$ where indices are added modulo $k$, and $\sigma$ fixes all other elements of $\Omega$, so the support of $\sigma$ is $\{a_0,\dots,a_{k-1}$. We call this permutation a $k$-cycle. Note that this notation is not unique: $(a_0,\dots,a_{k-1}) = (a_1,\dots,a_{k-1},a_0)$. Fixed points are cycles of length $1$.

10.22 DO (cycle decomposition of permutations)   Show that   (a)   every permutation is a composition of disjoint cycles of length $\ge 2$ and   (b)   this decomposition is uniquely up to the order of the cycles. (By definition, the identity is the composition of the empty set of cycles.)
Example. Let $\Omega=\{a,b,c,d,e,f\}$. Consider the permutation $\sigma$ defined by the table $$\begin{array}{|c|c|c|c|c|c|c|c|} x && a & b & c & d & e & f \\ \hline x^{\sigma} && d & a & f & b & e & c \\ \end{array}$$ In cycle decomposition:   $\sigma = (adb)(cf)$   (and we may also write   $\sigma = (e)(dba)(cf)$).

10.23 DEF   Let $x\in\Omega$ and $\sigma\in\sym(\Omega)$. The period of $x$ under $\sigma$, denoted $\per(\sigma,x)$, is the length of the $\sigma$-cycle containing $x$, i.e., $\per(\sigma,x) = |\{x^{\sigma^k} \mid k\in\zzz\}|$. Note: If $x$ is a fixed point of $\sigma$ then $\per(\sigma,x)=1$.

10.24 ORD (8 points)   Let $\Omega=[n]$ and consider the uniform distribution on $S_n$. Let $1\le k\le n$. Prove: for a random permutation $\sigma\in S_n$ we have $\Pr(\per(\sigma,1)=k) = 1/n\,.$

10.27 BON (12 points) (expected number of cycles in a random permutation)   For $\sigma\in S_n$, let $X_n(\sigma)$ denote the number of cycles in the cycle decomposition of the permutation $\sigma$, counting each fixed point as a separate cycle of length 1. (So for the permutation defined by the table in 10.21 we have $X_6(\sigma)=3$.)
So $X_n$ is a random variable over $S_n$ with the uniform distribution. Prove:   $E(X_n)\sim \ln n$.

10.38 DEF   A permutation group $G$ acting on the set $\Omega$ is a subgroup of $\sym(\Omega)$, i.e., a subset of $\sym(\Omega)$ that includes the identity and is closed under composition and inverses. If $|\Omega|=n$ then we say that $G$ is a permutation group of degree $n$. The order of $G$ is $|G|$. The "subgroup" relation is denoted by "$\le$", so $H\le G$ indicates that $H$ is a subgroup of $G$.

10.41 DEF/DO   Let $G\le \sym(\Omega)$ be a permutation group. For $x,y\in\Omega$ we write $x\sim_G y$ if $(\exists \sigma\in G)(x^{\sigma}=y)$. This is an equivalence relation on $\Omega$. Its equivalence classes are called the orbits of $G$. Prove: The orbit of $x\in\Omega$ (the equivalence class of $x$) is the set $$ x^G := \{x^{\sigma} \mid \sigma\in G\}\,.$$

10.44 DEF   We say that the permutation group $G\le \sym(\Omega)$ is transitive if it has just one orbit, i.e., $$ (\forall x,y\in\Omega)(\exists \sigma\in G)(x^{\sigma}=y)\,.$$

10.48 DEF   For $x\in\Omega$, the stabilizer of $x$ in $G$ is the subgroup $$ G_x := \{\sigma\in G \mid x^{\sigma} = x\}\,$$

10.51 ORD (8 points) (Orbit-Stabilizer Lemma)   Prove:   $|x^G|\cdot |G_x| = |G|.$

10.55 BON (10 points)   Let $G$ be a permutation group. Let $X$ denote the number of fixed points of a random $\sigma\in G$. Prove:   $E(X)$ is equal to the number of orbits of $G$.

10.65 DEF   Let $\calH=(V,\calE)$ be a hypergraph. An automorphism of $\calH$ is a self-isomorphism, i.e., a permutation $\sigma\in\sym(V)$ such that $E\subseteq V$ is an edge if and only if $E^{\sigma}$ is an edge.
Here $E^{\sigma} :=\{x^{\sigma} \mid x\in E\}\,$.

10.68 DO/DEF   Show that the automorphisms form a subgroup of $\sym(V)$. It is called the automorphism group of $\calH$, denoted $\aut(\calH)$. So $\aut(\calH)\le \sym(V)$. We say that $\calH$ is vertex-transitive if $\aut(\calH)$ is transitive.

10.71 DO   Prove: $(\forall x\in\rrr)(x\neq 0 \Rightarrow 1+x < \eee^x)\,.$

10.76 DO   Let $\calH$ be a hypergraph with $n$ vertices. We have shown that $\alpha(\calH)\cdot\chi(\calH) \ge n\,.$ Show that

10.78 BON (18 points, due May 7)   Let $\calH$ be a vertex-transitive hypergraph with $n$ vertices. Prove:   $\alpha(\calH)\cdot\chi(\calH) \le n(1+\ln n)\,.$
Hint.   Use the probabilistic method. Give a clear definition of the probability space you are using.

10.83 DO   Let $\fff$ be a field. Consider the projective plane $PG(2,\fff)$ where both the points and the lines are described by "homogeneous coordinates" $(a:b:c)$, i.e., equivalence classes of vectors in $\fff_q^3\setminus\{0\}$ under scaling: $(a,b,c)\sim (ka,kb,kc)$ for $k\in\fff_q^\times = \fff_q\setminus\{0\}$, and a point is incident with a line if the corresponding vectors are perpendicular.
Show that every invertible $3\times 3$ matrix over $\fff$ defines an automorphism of $PG(2,\fff)$.

10.85 BON (13 points)   Let us say that a set of points in a projective plane are in general position if no three of them are on a line. Let $a_1,...,a_4$ be four points in general position and let $b_1,...,b_4$ be another four points in general position in $PG(2,\fff)$. Prove that $PG(2,\fff)$ has an automorphism$\sigma$ such that $a_i^{\sigma}=b_i$ $(i\in [4])$.

10.88 ORD (12 points)   Prove that the Fano plane has 168 automorphisms.

10.92 DEF   Let $\calS=(V,\calE)$ be a STS. A subset $A\subseteq V$ is a set of generators if no proper subSTS contains $A$.

10.96 BON (12 points)   Let $\calS$ be a STS with $n\ge 3$ points. Prove: $\calS$ has set of generators of size $\le \log_2(n+1)$.

10.92 BON (10 points)   Let $\calS$ be a STS with $n$ points. Prove:   $|\aut(\calS)|\le n^{\log_2(n+1)}$.

10.105 ORD (9 points)   PROB 7.11.4 (uncorrelated but not independent random variables). You do not need to prove that your sample space is smallest possible.

10.109 BON (15 points, due May 7)   PROB 7.10.15 (b) (Aces vs Spades)

10.115 BON (16 points, due May 7) (strongly negatively correlated events)   Let $A_1,\dots,A_m$ be balanced events ($\Pr(A_i)= 1/2$). Assume $(\forall i\neq j)(\Pr(A_i\cap A_j)\le 1/5)$. Prove:   $m\le 6$.
Hint.   Random variables.

10.XX  

10.XX  

More to follow. Please check back later.

Material covered:   The complete $r$-uniform hypergraph. Structures in hypergraphs: independent set, legal coloring, cover (hitting set), matching. Fractional cover, fractional matching. Corresponding parameters: independence number $\alpha(\calH)$, chromatic number $\chi(\calH)$, covering (hitting) number $\tau(\calH)$, matching number $\nu(\calH)$, fractional covering number $\tau^*(\calH)$, fractional matching number $\nu^*(\calH)$. Linear programming, LP duality.

09.XX  

09.20 REVIEW   independent sets, independence number (DEF 02.155).
If an edge is empty ($\emptyset\in\calE$) then there is no independent set. When speaking of the independence number, we tacitly assume $\emptyset\notin\calE$.

09.23 DO   Let $r\ge 2$. Observe:   $\alpha(K_n^{(r)})=r-1$.

09.27 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 (every edge gets at least two colors). 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 assume that $(\forall E\in\calE)(|E|\ge 2)$.

09.29 DO   Prove:   $\chi(\calK_n^{(r)} = \lceil\frac{n}{r-1}\rceil\,.$

09.31 ORD (6 points)     Let $\calH$ be a hypergraph with $n$ vertices. Prove:   $\alpha(\calH)\cdot\chi(\calH) \ge n$.

09.35 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 inapproximability result holds for the chromatic number.

09.38 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$.

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

09.44 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.

09.47 DO   The number 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.

09.49 DO   Prove: For complete uniform hypergraphs, the Greedy Coloring algorithm produces an optimal coloring.

09.52 ORD (10 points)   Let $r\ge 2$ and let $\calH=(V,\calE)$ be an $r$-uniform hypergraph with $m$ edges. Prove: if $m\le 2^{r-1}$ then $\calH$ is 2-colorable, i.e., $\chi(\calH)\le 2$.
Hint.   Consider a random red/blue coloring, deciding the color of each vertex by an independent flip of a fair coin. Prove that with positive probability, this is a legal coloring.

09.55 ORD (4 points)   Let $\calP$ be a finite projective plane of order $n$. Prove:   If $n\ge 5$ then $\calP$ is 2-colorable.

09.XX  

09.65 DEF   A cover (also called a transversal, or a 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.
When speaking of the covering number of a hypergraph, we tacitly assume that $\emptyset\notin\calE$.

09.68 DO   Prove:   $\alpha(\calH)+\tau(\calH) = n$.

09.71 Greedy Cover algorithm Given a hypergraph $\calH=(V,\calE)$ with no empty edge, 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$

09.74 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)$.

Note that $|C|\ge \tau(\calH)$. So Lovász's theorem 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.

09.77 DO   Prove: for fixed $r\ge 1$, the Greedy Cover algorithm is optimal within a factor of $O(\log n)$, i.e., it produces a cover of size not great than $O(\log n)$ times the optimum. ($n$ is the number of vertices.)
(The constant hidden in the big-Oh notation depnds on $r$.)

09.85 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.

09.88 DO   Prove:   $\nu(\calH) \le \tau(\calH)$.

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

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

09.98 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)$.

09.101 ORD (3 points)   Let $\calP$ be a possibly degenerate projective plane. Determine $\nu(\calP)$. Reason your answer in terms of the axioms.

09.104 BON (11 points)   Let $\calP$ be a projective plane of order $n$. Determine $\tau(\calP)$.

09.XX  

09.110 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.

09.113 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)$.

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

09.119 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\}\,.$$

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

09.122 BON (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.)

09.125 DO   Let $\calH$ be a good hypergraph. Prove:   (a)   $\tau^*(\calH)\le \tau(\calH)$    and   (b)   $\nu(\calH) \le \tau^*(H)$.

09.128 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(E) \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)$.

09.131 DO   Every hypergraph has a fractional matching.

09.133 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\}\,.$$

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

09.135 DO   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.)

09.137 DO   Prove:   For good hypergraphs $\calH$,   $\nu(\calH)\le \nu^*(\calH)$.

09.139 ORD (10 points)   Prove:   For good hypergraphs $\calH$ we have   $\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.

09.142 ORD (4+4+4 points)   Let $\calH=(V,\calE)$ be a regular $r$-uniform hypergraph where $r\ge 1$. Assume $\calE\neq\emptyset$. Prove:   (a)   $\tau^*(\calH) \le n/r$   (b)   $\nu^*(\calH) \ge n/r$   (c)   $\tau^*(\calH) = \nu^*(\calH) = n/r$.
Prove (a) and (b) by constructing a fractional cover and a fractional matching, respectively, each of which has value $n/r$. Now the proof of (c) should be half a line with reference to a previous exercise. Do not use the fact that $\tau^*=\nu^*$ holds for every hypergraph. Use only lower-numbered exercises.
Update [Apr 21 at 4:05am] Three critical typos have been corrected. The inequality in (a) went the wrong way, and (b) stated an equality instead of an inequality, and in the instructions, "matching" and "cover" were interchanged.

09.XX  

09.XX  

09.XX  

More to follow. Please check back later.

Material covered:   The complete $r$-uniform hypergraph. Chains, antichains in the powerset $\calP(\Omega)$. Sperner's Theorem. Proof by Lubell's permutation method. The BLYM inequality. Linear orders, prefixes. Chain cover, min size of chain covers $=$ max size of antichains (stated). --- For what $n$ does a finite projective plane of order $n$ exist? Projective planes over any field. Galois planes. Homogeneous coordinates. Galois planes are self-dual. Bruck--Ryser Theorem stated. Number of pairwise orthogonal Latin squares of order $n$, connection to existence of projective planes of order $n$. Non-existence of finite projective planes of order 10 (story).

08.10 STUDY   Asymptotic notation: little-oh ($o$), big-Oh ($O$), big-Omega ($\Omega$), big-Theta ($\Theta$) notation: DMmini Chapters 2.3, 2.4

08.15 DEF ($r$-uniform cliques)   Let $V$ be a set and $r\ge 0$. The $r$-uniform clique or complete $r$-uniform hypergraph on $V$ is $\calK_V^{(r)}=(V,\binom{V}{r})$. We also write $\calK_n^{(r)}$ for $\calK_V^{(r)}$ if $|V|=n$ and we do not wish to specify the set $V$.   $\calK_n^{(r)}$ has $n$ vertices and $\binom{n}{r}$ edges.

08.18 DEF   Two sets, $A,B$ are comparable if $A\subseteq B$ or $B\subseteq A$. Otherwise they are incomparable. We write $A\| B$ to denote that $A,B$ are incomparable.

08.20 DEF   Recall that $\calP(\Omega)$ denotes the powerset of the set $\Omega$ (the set of all subsets of $\Omega$). A subset $\calA\subseteq\calP(\Omega)$ is a chain if the members of the chain are pairwise comparable, and an antichain if they are pairwise incomparable. Antichains are also called Sperner families.

08.23 DO   Every maximal chain in $\calP(\Omega)$ is maximum. It has $n+1$ elements, where $n=|\Omega|$.

08.25 DO   Show that for every $n\ge 2$, not every maximal antichain is maximum.

08.27 DEF   A linear order on a set $A$ is transitive trichotomic relation on $A$. A linear ordering of a set $A$ of $n$ elements is a list $(a_1,\dots,a_n)$ where $A=\{a_1,\dots,a_n\}$. (So $a_1,\dots,a_n$ are all distinct.) A numbering of a set $A$ of $n$ elements is a bijection $[n]\to A$.

08.29 DO   Find simple bijections between the numberings and the linear orderings of a set $A$ of $n$ elements, and the linear orders of $A$. Observe that there are $n!$ numberings, and therefore $n!$ linear orderings and $n!$ linear orders.

08.31 ORD (12 points, due Apr 30)   Let $C_n$ denote the number of chains in $\calP(A)$ where $|A|=n$. Prove:   $C_n \le 4n^n$.

08.34 DEF   Let $(a_1,\dots,a_n)$ be a linear ordering of the set $A=\{a_1,\dots,a_n\}$. A subset $B\subseteq A$ is a prefix of this linear ordering if for every $i,j\in [n]$, if $i < j$ and $a_j\in B$ then $a_i\in B$. So a linear ordering of a set of $n$ elements has $n+1$ prefixes.
Example. Let $A=\{a,b,c,d,e\}$. The six prefixes of the linear ordering $(d,a,c,e,b)$ are $\emptyset$, $\{d\}$, $\{a,d\}$, $\{a,c,d\}$, $\{a,c,d,e\}$, and $A$ itself.

08.36 BLYM inequality   (named after Bollobás, Lubell, Yamamoto, and Meshalkin).   Let $|\Omega|=n$ and let $\calF\subseteq\calP(\Omega)$ be a Sperner family (antichain). Then $$ \sum_{E\in\calF} \frac{1}{\binom{n}{|E|}} \le 1\,.$$

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

08.41 DO   Derive Sperner's Theorem from the BLYM inequality.

08.43 DO   Prove:   $\binom{n}{\lfloor n/2\rfloor}\sim \sqrt{\frac{2}{\pi}}\cdot\frac{1}{\sqrt{n}}\cdot 2^n\,.$

08.46 Lubell's permutation method   Let $|\Omega|=n$ and let $\sigma$ be a linear ordering of $\Omega$. Let $A\subseteq\Omega$. We say that $A$ and $\sigma$ are compatible if $A$ is a prefix of $\sigma$. 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(\sigma)$ denote the number of elements of $\calF$ that are compatible with $\sigma$. So $X$ is a random variable on our probability space.

08.49 DO (Lubell's method continued)   (a) $X\le 1$.   (This is where we use that $\calF$ is a Sperner family).
(b) $X=\sum_{i=1}^m Y_i$ where $Y_i$ is the indicator variable indicating the event $A_i$ that $F_i$ and $\sigma$ 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 our (first) proof of Sperner's Theorem.

08.52 BON (18 points, due Apr 30)   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}$.

08.55 BON (16 points) (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 8 points, assume the $a_i$ are positive.

08.58 DEF (chain cover)   Let $|\Omega|=n$. Let Let $\calC=\{C_1,\dots,C_m\}$ be a set of chains in $\calP(\Omega)$. We say that $\calC$ is a chain cover of $\calP(\Omega)$ if $\calP(\Omega)=\bigcup_{i=1}^m C_i$.

08.61 DO   Let $\calA$ be an antichain in $\calP(\Omega)$ and let $\calC$ be a chain cover of $\calP(\Omega)$. Show that $|\calA|\le |\calC|$ and therefore $\max |\calA| \le \min |\calC|$.

08.64 Reward (chain cover)   Prove that there exists a chain cover of size $\binom{n}{\lfloor n/2\rfloor}$ in $\calP(\Omega)$.

08.67 DO (second proof of Sperner's Theorem)   (a)   Show that Sperner's Theorem immediately follows from the preceding exercise.   (b)   Show that $\max |\calA| = \min |\calC|$ (equality holds in the last inequality in 08.61). This is a special case of Dilworth's Theorem which generalizes this result to partially ordered sets.

08.69 DO   Let $|\Omega|=n$. Show that for every $k$ ($0\le k\le n$) there exists a maximal Sperner family of size $\binom{n}{k}$.

08.72 CH   Show: the only maximum Sperner families in $\calP(\Omega)$ are the $r$-uniform cliques with $r=\lfloor n/2\rfloor$ or $r=\lceil n/2\rceil$.

08.75 ORD (6 points) Find $n+1$ Sperner families in $\calP(\Omega)$ for which equality holds in the BLYM inequality. No proof required.

08.78 CH   Show: there are only $n+1$ Sperner families for which equality holds in the BLYM inequality.

08.XX  

08.XX  

08.XX  

08.XX  

08.XX  

More to follow. Please check back later.

Material covered:   Bell numbers: toward asymptotics. Generating function, exponential generating function. Random variables, expected value, linearity of expected value, indicator variables = Bernoulli trials, indicator of event, expected number of successes in a sequence of Bernoulli trials. Orthogonal Latin squares.

07.15 STUDY   PROB Chapter 7.9 Random variables, expected value, indicator variables, Bernoulli trials

07.25 ORD (3 points)   PROB 7.9.5 ($\min X \le E(X) \le \max X$)

07.28 DO   PROB 7.9.6, 7.9.7 (linearity of expectation)

07.31 DO   PROB 7.9.11 ($E(\vartheta_A) = \Pr(A)$)

07.33 DO   PROB 7.9.11 (linear combinations of indicator variables)

07.35 DO   PROB 7.9.13 (expected value of sum of Bernoulli trials, i.e., expected number of heads in a sequence of biased coin flips)

07.38 ORD (8+5 points)   (a)   What is the expected number of Aces in a poker hand? Clarity of the definition of the random variables used in your solution is critical.   (b)   What is the sample space for this experiment? State the size of the sample space.

07.47 ORD (12 points, due Apr 30)   PROB 7.9.16 (runs of $k$ heads)

07.44 ORD (14 points, due Apr 22)   PROB 7.9.18 (Club of 2000)

07.41 ORD (8+6 points, due Apr 30)   PROB 7.9.22 (marbles in cups)

07.51 DEF (superposition of matrices)   Let $\Sigma_1$ and $\Sigma_2$ be sets of symbols and let $L_k = (\sigma^{(k)}_{ij})$ be an $n\times n$ matrix filled with symbols from $\Sigma_k$ $(k=1,2)$. The superposition of $L_1$ and $L_2$, which we denote $L_1 \diamondsuit L_2$ (not a standard notation), is the $n\times n$ matrix filled with entries from $\Sigma_1\times\Sigma_2$ where the $(i,j)$-entry of $L_1 \diamondsuit L_2$ is $(\sigma^{(1)}_{ij},\sigma^{(2)}_{ij})$ (the combination of the $(i,j)$-entry of $L_1$ and the $(i,j)$-entry of $L_2$.

07.53 DEF (orthogonal Latin Squares)   Let $\Sigma_1$ and $\Sigma_2$ be sets of $n$ symbols each and let $L_k$ be an $n\times n$ Latin square filled with symbols from $\Sigma_k$ $(k=1,2)$. Let $L_k=(\sigma^{(k)}_{ij})$. We say that $L_1$ and $L_2$ are orthogonal if $\{(\sigma^{(1)}_{ij},\sigma^{(2)}_{ij})\mid i,j\in [n]\} = \Sigma_1 \times \Sigma_2\,.$ In other words, $L_1$ and $L_2$ are orthogonal if each pair $(\sigma_1,\sigma_2)$ of symbols $(\sigma_i\in\Sigma_i)$ occurs in exactly one cell of the superposition $L_1\diamondsuit L_2$.

07.55 DEF   An $n\times n$ cyclic Latin square $C$ is a Latin square of which the first row is $(a_0,\dots,a_{n-1})$, and each subsequent row is the cyclic right shift of the preceding row. So if the rows and columns are indexed $0,1,\dots,n-1$ and $C = (c_{ij})$ then $$ c_{ij} = a_{i+j \bmod n} \,.$$

07.58 EXAMPLE   The following two $3\times 3$ Latin squares are orthogonal: $\begin{pmatrix} a & b & c \\ c & a & b\\ b & c & a \end{pmatrix}$   and   $\begin{pmatrix} A & B & C \\ B & C & A\\ C & A & B \end{pmatrix}\,.$

07.61 ORD (8 points)   Let $n\ge 3$ be odd. Show that there exist two orthogonal $n\times n$ Latin squares.

07.64 BON (10 points)   Let $q=p^k\ge 4$ where $p$ is a prime number. Show that there exist $q-1$ pairwise orthogonal $q\times q$ Latin squares.
For a partial credit of 6 points, solve this problem for $k=1$.
Hint.   Use the field $\fff_q$.

07.67 BON (14 points, due Apr 22)   Let $n$ be even. Show that the cyclic $n\times n$ Latin square has no orthogonal mate. (No Latin square is orthogonal to it.)

07.71 REWARD   Let $n\ge 3$. Prove:   (a)   the number of pairwise orthogonal $n\times n$ Latin squares is at most $n-1$.   (b)   $n-1$ pairwise orthogonal $n\times n$ Latin squares exist if and only if there exists a finite projective plane of order $n$.
(Recall: "Reward problems" are not meant to be handed in. Enjoy!)

07.XX  

Material covered:   Independent sets in hypergraphs. Supermultiplicative sequences, Fekete's Lemma. The $\SET_d$ game and the Cap set problem. (See Class 5 definitions and exercises.) Finite probability spaces. Examples: binary sequences (coin flips), poker hands, shuffling cards. Independence, positive and negative correlation of pairs of events. Conditional probability. Independence of multiple events. Pairwise independence. Independence vs size of sample space. Additional exercises: Determinants, Fibonacci numbers, Stirling numbers, Bell numbers.

06.15 BON (16 points)   Let $\lambda\in\nnn$ and let $\calH=(V,\calE)$ be a hypergraph with $n$ vertices and $m$ edges such that

•     $(\forall E, F\in\calE)(E\neq F \Rightarrow |E\cap F|=\lambda)$

06.20 STUDY   determinants (LinAlg Chapter 6)

06.23 BON (9+9 points)   (a)   Compute the determinant given in LinAlg 6.7.4. Your answer should be a simple closed-form expression in terms of $\alpha,\beta$, and $n$. You find the definition of "closed-form expression" in PROB Def 7.1.4. Elegance counts.   (b)   Show that for uniform hypergraphs $\calH$, the linear independence result stated in 6.15 follows immediately from (a) (in no more than two or three lines).

06.26 BON (8+8 points)   Let $A$ be an $m\times n$ integral matrix (all entries are integers). Such a matrix can be interpreted as a matrix over any field. (The number $k\in\nnn$ is interpreted as $1+\dots+1$ ($k$ terms) where $1\in\fff$ is the identity element of $\fff$, and $-k$ is interpreted as the additive inverse of $k$.)
Let $\fff$ be a field. Prove:   (a)   Prove: $\rank_{\fff}(A) \le \rank_{\qqq}(A)$   (b)   There is a finite set $P$ of prime numbers (depending on $A$) such that if the characteristic of $\fff$ does not belong to $P$ then $\rank_{\fff}(A) = \rank_{\qqq}(A)$. Clarity of the definition of your set $P$ is paramount.

06.38 DO   PROB 7.1.6(b) (Vandermonde identity)
Update [04-17: downgraded to "DO" exercis]

06.41 DO   PROB 7.1.6(c) (a sum of binomial coefficients)
Update (Apr 11 at 5am). Dowgraded from ORD to DO.

06.47 REVIEW   the concept of vector spaces and the basic concepts related to it, with examples (LinAlg Chapter 15).

06.50 STUDY   Fibonacci numbers (PROB 7.1.7). Do not miss the initial values.

06.54 ORD (6+6 points)   Recall that a Fibonacci-type sequence is a sequence that satisfies the Fibonacci recurrence.   (a)   Observe that the real Fibonacci-type sequences form a vector space under the termwise operations. (No proof required.) Show that the two Fibonacci-type geometric progressions (01.45) starting with $a_0=1$ form a basis of this space.   (b)   Express the Fibonacci sequence as a linear combination of these two geometric progressions. Show your work.

06.58 DO   Let   $A= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \,.$   Prove: for all $k\in\nnn$, $$A^k= \begin{pmatrix} F_{k+1} & F_k \\ F_k & F_{k-1} \end{pmatrix} \,.$$

06.61 ORD (8 points, due Apr 30)   PROB 7.1.10 (counting binary sequences with no consecutive zeros)

06.65 ORD (8 points, due Apr 30)   PROB 7.1.11 (binomials adding up to Fibonacci)

06.67 DEF (generating function)   The generating function of the sequence $a_0, a_1,\dots$ is the power series $$ f(x) = \sum_{k=0}^{\infty} a_kx^k \,.$$

06.69 ORD (9+6 points, due Apr 30)   Let $\fib(x) = \sum_{k=0}^{\infty} F_k x^k$ denote the generating function of the Fibonacci numbers.   (a)   Determine the convergence radius $r$ of this power series.
(We say that the convergence radius of a power series $\sum_{k=0}^{\infty} a_k x^k$ is $r$ if the series converges for $|x| < r$ and diverges for $|x| > r$. Here $r$ is either a non-negative real number or $\infty$.) (Use any general results from calculus.)
  (b)   Prove:   $\fib(x) = \frac{x}{1-x-x^2}$ for all $|x| < r$.

06.72 CH   PROB 7.1.8 (gcd of Fibonacci numbers)

06.76 STUDY   PROB Chapters 7.1--7.7.

06.79 ORD (5 points)   PROB 7.3.8 (number of trivial events)

06.82 DO   PROB 7.3.10 (probability of full house in poker hand)

06.84 ORD (6 points, due Apr 22)   PROB 7.3.11 (a3)

06.87 DO   PROB 7.3.12 (a,b)
Update [4-25 at 3:30am] downgraded from ORD to DO exercise.

06.89 DO   PROB 7.3.14 (modular equation)

06.91 DO   PROB 7.3.16 (union bound)

06.93 DO   PROB 7.4.2 (conditional probability space)

06.95 DO   PROB 7.4.3 (Bayes's Theorem)

06.97 DO   PROB 7.4.4 ($\Pr(A\cap B\cap C)$ via conditional probabilities)

06.99 DO   PROB 7.4.7 (Theorem of Complete Probability)

06.101 ORD (7+8+5 points)   PROB 7.4.12 (probability of causes)

06.103 DO   PROB 7.5.9 (two nontriv indep events $\Rightarrow$ $|\Omega|\ge 4$)

06.105 ORD (15 points, due Apr 22)   PROB 7.5.12 (correlation between being even and being divisible by 3) ($x$ is picked from the uniform distribution)<

06.107 DO   PROB 7.6.3 (independence of complement)

06.107 DO   PROB 7.6.4 (independence of trivial event)

06.109 ORD (4+7 points)   PROB 7.6.7 (3 events that are pairwise but not fully independent). Prove that you got the smallest possible sample space. Clarity of the definition of the probability space you construct is paramount.

06.111 DO   PROB 7.6.15 (equivalence of the two definitions of independence)

06.113 DO   PROB 7.6.17 (independence of complements)

06.115 ORD (9 points, due Apr 30)   PROB 7.6.19 ($k$ independent events $\Rightarrow$ $|\Omega| \ge 2^k$)

06.117 BON (9 points, due Apr 22)   PROB 7.6.20 ($(n-1)$-wise but not fully independent balanced events). Elegance matters. Prove that your sample space is as small as possible.

06.119 BON (10+10 points)   PROB 7.6.21 (small sample space for pairwise independent events)

06.121 CH   PROB 7.6.22 (ii) (small sample space for pairwise independent balanced events with $|\Omega|=p+1$)

06.123 CH (due Apr 22)   PROB 7.6.23 ($k$ pairwise independent nontrivial events $\Rightarrow$ $|\Omega|\ge k+1$)

06.129 DEF   For $1\le k\le n$, let $S(n,k)$ denote the number of partitions of $[n]$ into $k$ blocks. (Recall that the blocks are non-empty by definition.) The numbers $S(n,k)$ are called the Stirling numbers of the second kind.

06.131 DO   Verify that $S(n,2)=2^{n-1}-1$.

06.133 ORD (8 points)   Prove:   $\displaystyle{S(n,k) \le \frac{k^n}{k!}}$.

06.135 DEF   Recall that 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$

06.137 DO   Verify the values $B_0,\dots,B_4$ by listing all partitions of $[n]$ for $n\le 4$.

06.139 DO   Observe:   $B_n=\sum_{k=1}^n S(n,k).$

06.141 BON (16 points, due Apr 22)   Prove: $(\forall \epsilon > 0)(\exists n_{\epsilon}) (\forall n \ge n_{\epsilon})(B_n < (\epsilon n)^n)$.

06.143 NOTATION   Let $\lambda(n)$ denote the unique solution of the equation $x\ln x=n$.

06.145 ORD (6 points) Prove:   $\lambda(n)\sim n/\ln n$.

06.147 THEOREM (asymptotics of Bell numbers) The following remarkable asymptotic formula for the Bell numbers was published by Canadian mathematicians Leo Moser and Max Wyman in 1955. $$ B_n \sim \frac{1}{\sqrt{n}}\lambda(n)^{n+1/2}\eee^{\lambda(n)-n-1}\,.$$ While we shall not prove this result, we shall make significant steps towards the proof. This result should NOT be used in any of the subsequent exercises.

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

06.151 ORD (8 points, due Apr 30)   Let $\epsilon_n \to 0$. Let $(a_n\mid n\in\nnn_0)$ be a sequence. ($\nnn_0$ denotes the set of non-negative integers.) Assume $|a_n| \le (\epsilon_n n)^n$. Prove: The exponential generating function of $(a_n)$ converges everywhere (for every [real or complex] value of $x$).

06.153 NOTATION   Let $B(x)$ denote the exponential generating function of the Bell numbers: $$ B(x) = \sum_{n=0}^{\infty}\frac{B_n}{n!} x^n\,.$$

06.155 ORD (5 points, due Apr 22)   Prove that the power series $B(x)$ converges everywhere (its convergence radius is infinite).
Do not use the Moser--Wyman Theorem (06.147), but as usual, you may use all other lower-numbered exercises.

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

06.162 BON (9 points)   Use this recurrence to prove that $B(x)$ satisfies the differential equation   $B\,'(x) = \eee^x B(x)\,.$

06.165 ORD (10 points, due Apr 30)   Use the differential equation to prove the following explicit formula: $$ B(x) = \eee^{\eee^x-1} \,.$$

06.169 BON (10 points, due Apr 22)   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!} \,.$$

06.173 CH (due Apr 24)   Let $k(n)\in\nnn$ denote the value of $k$ corresponding to the largest term in Dobiński's formula (so we want to maximize $k^n/k!$). Prove: for $n\ge 1$ we have   $|k(n)-\lambda(n)| < 1$.

Material covered:   Linear and affine space. Affine combination, affine subspace. Affine closure. Affine independence. Affine dimension. Affine subspaces are translates of linear subspaces. Lines in $\fff_3^d$ for a STS. The $d$-dimensional SET cardgame. The Cap set problem.

05.15 STUDY   LinAlg Chapters 5.1, 5.2 (affine combinations)

05.18 Notation   Let $\fff$ be a field and $k,\ell\in\nnn$. Then $\fff^{k\times\ell}$ denotes the set of $k\times\ell$ matrices over $\fff$ (\ie, the matrix elements are from $\fff$).

05.20 ORD (4 points)   Let $A\in \fff^{m\times n}$ and $\bfb\in\fff^m$. Let $\bfx=(x_1,\dots,x_n)^{\tr}\in\fff^n$ be an unknown vector. Let us consider the system $A\bfx = \bfb$ of $m$ linear equations in $n$ unknowns. Let $U$ denote the set of solutions of this system, i.e., $$U = \{\bfx\in\fff^n \mid A\bfx = \bfb\}\,.$$ Prove that $U$ is affine-closed. When is it an affine subspace? (Give a simple answer in terms of the system of equations.)

05.23 DO   Prove that the intersection of any (finite or infinite) set of affine-closed sets is affine-closed.

05.24 DO   LinAlg 5.1.14 (affine subspaces are translates of linear subspaces)

05.26 ORD (3+3 points)   Let $q$ be a prime power. Recall that $\fff_q$ denotes the field of order $q$. Let $U$ be   (a)   a linear subspace   (b)   an affine subspace of $\fff_q^d$ of dimension $k$. Prove:   $|U|=q^k$.

05.29 ORD (4 points)   Count the affine lines in $\fff_q^d$. Your answer should be a simple expression in terms of $q$ and $d$.
(An affine line is a 1-dimensional affine subspace.)

05.32 ORD (4 points)   Let $L_d$ denote the set of affine lines in $\fff_3^d$. Prove that $\calS_d :=(\fff_3^d, L_d)$ is a STS.

05.35 ORD (6 points)   Let $\bfa,\bfb,\bfc\in \fff_3^d$. Prove: $\bfa+\bfb+\bfc=\bzo$ if and only if either $\bfa=\bfb=\bfc$ or $\bfa,\bfb,\bfc$ are distinct and they form an affine line.

05.38 DO   Let $D_d$ denote the deck of cards in the $d$-dimensional "SET" game and let $M_d$ denote the set of "SETs" in the game. Show that $(D_d,M_d)$ is a STS, isomorphic to $\calS_d$.

05.XX DO  

05.51 Notation   Recall the Def of an independent set in a hypergraph (Def 2.155). We denote the maximum size of an independent set in the hypergraph $\calH$ by $\alpha(\calH)$. Let $\alpha_d = \alpha(\SET_d)$. It is known that $\alpha_1=2$, $\alpha_2=4$, $\alpha_3=9$, $\alpha_4=20$, $\alpha_5=45$.

05.54 DEF   Let $(a_k \mid k\in\nnn)$ be an infinite sequence of positive reals. We say that this sequence is supermultiplicative if for all $r,s\in \nnn$ we have $a_{r+s}\ge a_r a_s$.

05.57 ORD (5 points)   Prove:   the sequence $(\alpha_k \mid k\in \nnn_0)$ is supermultiplicative.
($\alpha_k$ refers to the quantity defined in Notation 05.51.)

05.65 BON (10 points) (Fekete's Lemma)   Let $(a_k \mid k\in \nnn)$ be a supermultiplicative sequence of positive reals. Let $b_k=a_k^{1/k}$. Prove: $L:=\lim_{k\to\infty} b_k$ exists and it is equal to $\sup_{k\in\nnn} b_k$.

05.68 DO   Let $L = \lim_{k\in\nnn} \alpha_k^{1/k}$.   (a)   Show that $2\le L \le 3$.   (b)   Show that $L\ge 20^{1/4} \approx 2.1147$, based on the literature of the SET card game which says in particular that the maximum number of cards without a "SET" is 20.

05.XX DO  

More to follow. Please check back later.

Material covered:   Abstract algebra. Divisibility, congruence, operations on residue classes, soundness of definition of operations by representatives, $\zzz_m$. Groups, order of group. Examples. Permutations, the symmetric group of degree $n$. Rings. Examples. Zero-divisors. $\zzz_m$ has no zero-divisors if and only if $m$ is a prime number. Fields. Fields have no zero-divisors. If a finite ring $R$ has order $\ge 2$ and has no zero-divisors then $R$ is a field. Prime property, Euclid's lemma. $\zzz_p$ is a field; notation: $\fff_p$. Other finite fields. Classification of finite fields. Characteristic of field. Infinite field of finite characteristic. Vector space $\fff^n$ over any field $\fff$. Linear combination, linear independence, span. Subspace, dimension. If $W$ is a $d$-dimensional subspace of $\fff_q^n$ then $|W|=q^d$. Dot product. Perpendicular vectors. $\bfv^\perp$, $S^\perp$. $\dim(U)+\dim(U^\perp)=n$. Isotropic vector, totally isotropic subspace. Dimension of totally isotropic subspace $\le \lfloor n/2\rfloor$.

04.10 STUDY   abstract algebra: LinAlg Chapter 14.
WARNING: This chapter has been significantly updated just now: Last update March 29, 2024. Further updates expected over the weekend (will be reported right here, make sure you always refresh this page to see the latest information).

04.14 STUDY   "Geometric algebra": LinAlg Chapter 11.4. When reading this chapter, assume the bilinear form $f$ means the dot product: if $\bfx=(x_1,\dots,x_n)\in\fff^n$ and $\bfy=(y_1,\dots,y_n)\in\fff^n$ then let $f(\bfx,\bfy):=\bfx\cdot\bfy = \sum_{i=1}^n x_iy_i \in\fff$.

04.XX  

04.XX  

04.51 BON (10 points)   Let $\fff$ be a field and $U\le \fff^n$ be a subspace. Prove: $$\dim(U) + \dim(U^\perp) = n\,.$$

04.54 DEF   A subspace $U\le\fff^n$ is totally isotropic if $U\subseteq U^\perp$.

04.57 DO   If $U\le \fff^n$ is a totally isotropic subspace then $\dim(U) \le \lfloor n/2\rfloor$.

04.59 ORD (3+3+3 points)   Let $n\ge 2$. Prove: $\fff^n$ has a totally isotropic subspace of dimension $\lfloor n/2\rfloor$, assuming $\fff$ is one of the following fields:   (a)   $\fff_2$   (b)   $\fff_5$   (c)   $\ccc$.

04.62 BON (12 points)   Deduce the Eventown Theorem from 04.57.

04.XX DO  

04.XX DO  

04.XX DO  

More to follow. Please check back later.

Material covered:   Steiner Triple Systems (STS). Their view as an algebra with one binary operation. Direct product of algebras. Subalgebra, sub-STS. Constraint on $n$ (the number of points). Latin squares. Gluing smaller STSs into bigger ones using Latin squares.

03.15 DEF   A Steiner Triple System (STS) is a 3-uniform incidence geometry (every line has 3 points) with at least 1 point, such that every pair of distinct points is incident with a exactly one line.
Viewed as a hypergraph, an STS is a 3-uniform hypergraph with a non-empty set of vertices where every pair of distinct vertices belongs to exactly one edge. We refer to the edges as "triples".
Examples: 1 point, no triple; 3 points, 1 triple; the Fano plane (7 point, 7 triples); the SETs in the $d$-dimensional SET card game ($n=3^d$ points, $n(n-1)/6$ triples).

03.18 DO   Let $\calS$ be a STS of order $n$ (so $n$ is the number of points). The $m = n(n-1)/6$ ($m$ is the size, i.e., the number of triples).

03.20 DO (continued)   $\calS$ is regular of degree $(n-1)/2$.

03.23 DO   Infer from the preceding two exercises that $n\equiv 1$ or $3 \pmod 6$.

03.26 THEOREM   A STS of order $n$ exists if and only if $n\equiv 1$ or $3 \pmod 6$.

Some elements of the proof will be discussed below.

03.31   A binary operation on a set $\Omega$ is a function $f:\Omega\times\Omega\to\Omega$. Instead of $f(a,b)$ we usually write $a+b$ or $a\cdot b$ or $a\ast b$ or $a\circ b$ or $a\cup b$ or $a\cap b$ or something similar. We refer to a pair $(\Omega, \circ)$ as an algebra with a binary operation. Examples: $(\zzz,+)$ and $(\calP(A),\cup)$.

03.34 (viewing STS as an algebra)   Let $\calS=(V,\calE)$ be a STS. We use $\calS$ to define a binary operation "$\circ$" on $V$. For $a\in V$ define $a\circ a=a$ (the $\circ$ operation is idempotent). For $a\neq b\in V$ define $a\circ b = c$ where $\{a,b,c\}\in\calE$. (Note that there is exactly one such $c$, so this indeed defines a binary operation.) Note that $a\circ b=b\circ a$ (the operation $\circ$ is commutative) and if $a\circ b = c$ then $b\circ c=a$. Let us call this the "rotation property" (this is not a standard term, only for this course).

03.37 DO   Let $(V,\circ)$ be an algebra with a binary operation. Assume the operation $\circ$ is idempotent, commutative, and has the rotation property. Prove that this algebra is defined by a STS. In other words, show that, setting $\calE=\{\{a,b,a\circ b\} \mid a,b\in V, a\neq b\}$, the pair $(V,\calE)$ forms a STS.

03.41 DEF   Let $\calA=(A,\circ)$ and $\calB=(B,\ast)$ be algebras, each with a binary relation. We define their direct product $\calC=\calA\times\calB$ as the algebra $\calC=(C,\diamond)$ by setting $C=A\times B$ and $(a_1,b_1)\diamond (a_2,b_2)=(a_1\circ a_2,b_1\ast b_2)$.

03.44 DO   Prove: each of the following properties of a algebras with a binary operation is inherited by their direct product: idempotence, commutativity, the rotation property. In other words, if $\calA$ and $\calB$ are idempotent (their operation is idempotent) then so is $\cal\times \calB$, and similarly for the other two properties.

03.47 ORD (5+5 points, due Apr 8)   (a)   Based on the preceding exercise, define the direct product of two STSs.   (b)   Let $\calS_1$ and $\calS_2$ be two STSs. Prove:   $\alpha(\calS_1\times\calS_2) \ge \alpha(\calS_1)\cdot \alpha(\calS_2)\,.$

03.49 Corollary   If STSs of orders $n_1$ and $n_2$ exist then there exists a STS of order $n_1n_2$.

03.52 DO   Let $\SET_d$ denote the $d$-dimensional SET card game viewed as a STS. Prove: $\SET_k\times \SET_{\ell} \cong \SET_{k+\ell}$.

03.54 DO   $\alpha(\SET_d)\ge 2^d$.

03.57 DEF   Let $\calA=(A,\circ)$ and $B\subseteq A$. We say that $B$ defines a subalgebra of $\calA$ if $B$ is closed under $\circ$, i.e., $(\forall b,c\in B)(b\circ c\in B)$. In this case, $(B,\circ)$ is an algebra, where $\circ$ here denotes the restriction of the original $\circ$ operation to $B$. We usually refer to the set $B$ itself as a "subalgebra."

03.61 BON (3+7 points)   (a)   Let $\calS=(V,\calE)$ be a STS. Define what it means for a non-empty subset $W\subseteq V$ to be a sub-STS, based on the definition of a subalgebra.   (b)   Let $W$ be a proper subs-STS ("proper" means $W\neq V$). Prove: $|W| \le (n-1)/2$ (where $n=|V|$).

We show a method how to glue smaller STSs together to get bigger ones. These methods are part of a proof of the Theorem.

03.71 DEF   Let $A$ be a set of $n$ symbols. An $n\times n$ Latin square is an $n\times n$ matrix $M=(m_{ij})$ such that $m_{ij}\in A$ and each $k\in A$ occurs in every row and in every column (and therefore $k$ occurs exactly once in every row and in every column). So each row and each column represents a permutation of $A$.

03.73 Example   Make the first row $[0,1,2,\dots,n-2,n-1]$, the second row $[1,2,3,\dots,n-1,0]$, and each subsequent row a cyclic shift of the preceding row by 1 to the left. In formula: $m_{ij} = (i+j \bmod n)$ where the rows and columns are numbered $0$ to $n-1$. We refer to this as the cyclic Latin square.

03.XX  

03.XX  

More to follow. Please check back later.

Material covered:   Hypergraphs, multi-hypergraphs. Order (number of vertices), size (number of edges). Incidence matrix. Dual multi-hypergraph. $r$-uniform (multi-)hypergraph. The Fano plane. Finite projective planes, degenerate finite projective planes. Independence number of a hypergaph. The SET card game and its $d$-dimensional version

02.05 Notation   $\calP(\Omega)$ denotes the powerset of the set $\Omega$, i.e., the set of all subsets of $\Omega$. (So if $|\Omega|=n$ then $|\calP(\Omega)|=2^n$.) For $k\in\nnn_0$,   $\binom{\Omega}{k}$ denotes the set of $k$-subsets of $\Omega$ (subsets of size $k$). So, by definition, $\binom{n}{k}=\left|\binom{\Omega}{k}\right|$. Note that $$\calP(\Omega) = \bigsqcup_{k=0}^n \binom{\Omega}{k}\,.$$ ($\sqcup$ denotes disjoint union, i.e., union of disjoint sets.)

02.10 DEF   A hypergraph is a pair $\calH = (V,\calE)$ where $\calE\subseteq \calP(V)$. The elements of $V$ are called vertices, the elements of $\calE$ are called edges. The singular of the term "vertices" is vertex. We say that the hypergraph is empty if $\calE=\emptyset$, regardless of the number of vertices. If $A\in\calE$ is an edge and $u\in A$ then we say that $u$ is incident with $A$. If the vertices are numbered $V=\{v_1,\dots,v_n\}$ and the edges $\calE=\{E_1,\dots,E_m\}$ then the incidence matrix of $\calH$ is the $m\times n$ $(0,1)$ matrix $M=(m_{ij})$ where $m_{ij}=1$ if $v_j\in E_i$ and $m_{ij}=0$ otherwise.
WARNING: $M$ cannot have identical rows (two edges cannot be the same set) but it can have identical columns (two vertices can be incident with the same edges).
Updated Mar 27 at 17:05. We use the convention that the rows of the incidence matrix correspond to edges and the columns to vertices. In the original posting this was accidentally reversed.

02.12 NOTATIONAL CONVENTION   In most but not all cases, we write $n = |V|$ for the number of vertices and $m = |\calE|$ for the number of edges. So, (DO)   $m\le 2^n$.

02.14 DEF   (a)   The degree $\deg(u)$ of the vertex $u\in V$ is the number of edges incident with $u$. We say that $\calH$ is $d$-regular if every vertex has degree $d$. We say that $\calH$ is regular if it is $d$-regular for some $d$.
  (b)   The rank of an edge $E$ is its size $|E|$. The rank of $\calH$ is the maximum rank of its edges. We say that $\calH$ is $r$-uniform if every edge has rank $r$. We say that $\calH$ is uniform if it is $r$-uniform for some $r$. The rank of $\calH$ is the maximum rank of its edges.

02.16 Example   Let $|V|=n$ and $k\in\nnn_0$. The hypergraph $(V,\binom{V}{r})$ is the complete $r$-uniform hypergraph on $n$ vertices, denoted $K_n(r)$. It has $\binom{n}{r}$ edges.

02.17 DO   Prove that $K_n(r)$ is regular. Compute its degree.

02.18 DO (Handshake Theorem)   Prove: $$ \sum_{v\in V} \deg(v) = \sum_{E\in\calE} \rank(E)\,.$$ Remark. In particular, if $\calH$ is $d$-regular and $r$-uniform then $nd=mr$.

02.20 DEF   Let $\calH=(V,\calE)$ be a hypergraph, where $V=\{v_1,\dots,v_n\}$ and $\calE=\{E_1,\dots,E_m\}$. The incidence matrix of $\calH$ is the $m\times n$   $(0,1)$-matrix $M=(m_{ij})$ where $m_{ij}=1$ if $v_j$ and $E_i$ are incident.
Update. This definition is redundant, it just repeats part of DEF 02.10.

02.23 ORD (2+2 points) Let $\calH$ be the hypergraph given in Def 02.20 and let $M$ be its incidence matrix.   What are the diagonal entries   (a)   of the $m\times m$ matrix $MM^{\tr}$ and   (b)   of the $n\times n$ matrix $M^{\tr}M$, where $M$ is the incidence matrix of the hypergraph $\calH$ ? ($M^{\tr}$ denotes the transpose of $M$.)
Update [Fri Mar 29 at 18:45] "in the preceding exercise" replaced with "in Def 02.20".

02.25 DEF   The trace $\trace(A)$ of the square matrix $A$ is the sum of its diagonal elements.

02.27 ORD (3 points) (trace commutativity)   Let $B$ be an $m\times n$ matrix and $C$ an $n\times m$ matrix. Prove:   $\trace(BC) = \trace(CB)$.

02.29 ORD (3 points)   Show that the Handshake Theorem (02.17) follows from trace commutativity.

02.32 DEF   A graph is a 2-uniform hypergraph.

02.35 DEF   A multiset is a function $\calS:\Psi\to\nnn$ where $\Psi$ (the domain of $\calS$) is a set called the underlying set of the multiset $\calS$ and for each $q\in\Psi$, the number $\Psi(q)$ is the multiplicity of $q$ in $\calS$. The size of the multiset $\calS$ is $|\calS|:=\sum_{q\in\Psi}\Psi(q)$. We usually represent a multiset by a list $(P_1,\dots,P_m)$ where each $P_i$ is a set in the codomain of $\Psi$ and each $q\in\Psi$ occurs $\Psi(q)$ times on the list.
Example.   $(a,b,a,a,c,b,b,b)$ represents the multiset $\{a^3,b^4,c\}$ where $\Psi=\{a,b,c\}$, and the superscripts indicate the multiplicities. So the length of the list (in this case, 8) is the size of the multiset $(3+4+1)$.

02.37 DEF  A multi-hypergraph is a pair $\calH = (V,\calE)$ where $V$ is a set and $\calE$ is a multiset of subsets of $V$. We write $\calE$ as a list $\calE=(E_1,\dots,E_m)$ where $E_i\subseteq V$; in this case we say that $\calH$ has $m$ edges, even though the $E_i$ do not need to be distinct. The degree of vertex $u\in V$ is the number of indices $i$ such that $u\in E_i$.
If $V=\{v_1,\dots,v_n\}$ then the incidence matrix of $\calH$ is the $m\times n$   $(0,1)$-matrix $M=(m_{ij})$ defined as in Def. 2.10.
Note that every $m\times n$   $(0,1)$-matrix defines a multi-hypegraph. This statement is our motivation to consider multi-hypergraphs, rather than just hypergraphs (where the rows of the incidence matrix are distinct). Indeed, there is a one-to-one correspondence between $m\times n$   $(0,1)$-matrices and multi-hypergraphs with $n$ vertices labeled $1,\dots,n$ and $m$ edges labeled $1,\dots,m$.

02.39 DEF (dual multi-hypergraph)   Let $\calH$ be a multi-hypergraph with incidence matrix $M$. The multi-hypergraph $\calH^{\tr}$ with incidence matrix $M^{\tr}$ is called the dual of $\calH$. So $\calH^{\tr}$ has $m$ vertices and $n$ edges; the degree of a vertex in $\calH$ is the rank of the corresponding edge in the dual and vice versa.
Observe:   $(\calH^{\tr})^{\tr} = \calH$.

02.42 DEF   A bipartite graph $\calG=(W,E)$ is a graph whose set of vertices is divided into two parts: $W=V_1\sqcup V_2$ (so $\{V_1,V_2\}$ form a partition of $V$) such that every edge of $\calG$ joins a vertex in $V_1$ to a vertex in $V_2$.
Example.   Let $W$ denote the set of cells of a chessboard. $W$ will be the set of 64 vertices of a graph. Let us say that vertices $u,v$ form an edge in $\calG$ if they represent adjacent cells (the cells they share a side). Then this graph is bipartite (black cells, white cells).

02.45 DEF   The incidence graph of the multi-hypergraph $\calH=(V,\calE)$, where $\calE=(E_1,\dots,E_m)$, is the bipartite graph $\calG = (V\sqcup [m],R)$ where $V$ is viewed as being disjoint from $[m]$, and $$R = \{\{v,i\}\mid v\in V, i\in [m],\text{ and } v\in E_i\}\,.$$ So one part of this bipartite graph is the set of vertices, the other part is set of indices of the edges, and $R$ encodes the incidence relation.
If $\calH$ is a hypergraph then the vertices in the second part of the incidence graph can be the edges themselves, rather than their indices.
Note.   The degree of $u\in V$ in the graph $\calG$ is the same as $\deg(v)$ in $\calH$. The degree of $i\in [m]$ in $\calG$ is the rank of the edge $E_i$.

02.47 DEF (truncation)   Let $\calH=(V,\calE)$ be a multi-hypergraph with $\calE=(E_1,\dots,E_m)$. For $u\in V$ we define the truncation $\calH_u = (V\setminus\{u\},\calE_u)$ where $\calE_u=(E_1\setminus\{u\},\dots,E_m\setminus\{u\})$. So $\calH_u$ is a multi-hypergraph with $n-1$ vertices and $m$ edges.
In terms of the incidence matrix, we removed its column corresponding to $u$. Now rows have been removed.

02.49 BON (18+4 points, due Apr 8)   (a)   Let $\calH=(V,\calE)$ be a hypergraph (no multiple edges) with $n$ vertices and $n$ edges (so $m=n$). Prove: there is a vertex $u\in V$ such that the truncation $\calH_u$ is also a hypergraph, i.e., all the sets $E_i\setminus\{u\}$ are distinct.   (b)   Show that this result is tight in the sense that it will be false for every $n\ge 1$ if we let $m=n+1$. It will be false even if we do not allow the empty set to be an edge. (Get 3 out of the 4 points if your example has an empty edge.)
Update [Apr 3 at 12:50]. Part (b) added.

02.52 DEF   Let $\calH=(U,\calE)$ and $\calK=(W,\calF)$ where $\calE=(E_1,\dots,E_m)$ and $\calF=(F_1,\dots,F_{m'})$ be multi-hypergraphs. A $\calH\to\calK$ isomorphism is a pair of bijections $g:U\to W$ and $h:[m]\to[m']$ (so in particular $|U|=|W|$ and $m=m'$) such that the pair $(g,h)$ preserves incidence: $$(\forall u\in U)(\forall i\in[m])(u\in E_i \Leftrightarrow g(u)\in F_{h(i)}) \,.$$ (If $\calH,\calK$ are hypergraphs then $h$ can be interpreted as a bijection between the sets of edges, rather than their indices.)
We say that $\calH$ and $\calK$ are isomorphic (denoted $\calH\cong \calK$) if there exists a $(g,h): \calH\to\calK$ isomorphism.

02.55 BON (3+6 points)   Let $H(n,r)$ denote the number of non-isomorphic $r$-uniform hypergraphs of order $n$. Prove: $$ \frac{2^{\binom{n}{r}}}{n!} \le H(n,r) \le 2^{\binom{n}{r}}\,.$$

(3 points for the upper bound, 6 for the lower bound)

02.65 STUDY   Incidence geometries, finite projective planes, the Fano plane: DMmaxi Chapter 7.1.

02.67 NOTATION   Incidence: if point $p$ is incident with line $\ell$, we denote this by $p\incid\ell$. If $p$ is not incident with $\ell$, we denote this by $p\nincid\ell$.
For typographical simplicity, you may write $p\in\ell$ and $p\notin\ell$ in the same meanings.

Figure 2.70   The Fano plane

02.72 DO   Establish a natural bijection between incidence geometries (with point and lines numbered) and multi-hypergraphs (with vertices and edges numbered). So incidence geometries are just another view of multi-hypergraphs.

02.75 DO   Observe that the dual of an incidence geometry (DMmaxi Def 7.1.3) corresponds to the dual of the corresponding multi-hypergraph.

02.77 ORD (5 points)   Prove that the Fano plane is self-dual (isomorphic to its dual). Provide a pair of explicit bijections. Use the labeling given in Figure 2.70. No proof required.

02.79 DEF   An incidence geometry is a possibly degenerate projective plane if it satisfies the first two axioms of projective planes (DMmaxi Def 7.1.4) but instead of Axiom 3 we only require the weaker
          Axiom 3$^*$ (triangle axiom)   There exist 3 points not on a line.
A degenerate projective plane is an incidence geometry that satisfies Axioms 1, 2, and 3$^*$, but not Axiom 3.

02.81 DO (construction of degenerate projective planes)   For $n\ge 3$ let $\calD_n$ denote the incidence structure with $n$ points, $p_0,\dots,p_{n-1}$ and $n$ lines, $\ell_0,\dots,\ell_{n-1}$, such that line $\ell_0$ is incident with the points $p_1,\dots,p_{n-1}$, and for $i\in [n-1]$, line $\ell_i$ is incident with $p_0$ and $p_i$. So $\deg(p_0)=\rank(\ell_0)=n-1$ and for $i\in [n-1]$, $\deg(p_i)=\rank(\ell_i)=2$.

02.83 DO   Prove:   for $n\ge 3$, $\calD_n$ is a degenerate projective plane.

02.85 DO   Prove that $\calD_n$ is self-dual (isomorphic to its dual).

02.88 BON (8 points) (uniqueness of degenerate projective planes)   Let $\calH$ be a degenerate projective plane with $n$ points. Prove: $\calH \cong \calD_n$.

02.91 ORD (3+4 points)   Why is it obvious from the axioms that   (a)   the dual of a possibly degenerate projective plane is a possibly degenerate projective plane, but   (b)   it is not immediate from the axioms that the dual of a projective plane is a projective plane? State the simple fact you would need to prove about projective planes in order to establish that the dual of a projecvtive plane is a projective plane (which is a true statement, but you are not asked to prove it here). No proof required, just state what you would need to prove.

02.93 DO   Prove that the dual of a projective plane is a projective plane.

02.95 ORD (4 points)   Let $\calG=(P,L,I)$ be a possibly degenerate projective plane. Let $p\in P$ and $\ell\in L$ such that $p \nincid \ell$ ($p$ and $\ell$ are not incident). Prove:   $\deg(p)=\rank(\ell)$.

02.97 DO   Let $\calP=(P,L,I)$ be a projective plane and $p_1,p_2\in P$. Prove: there exists a line $\ell\in L$ such that $p_1,p_2\notin\ell$.
This is not as straightforward as it seems. Prove that $\ell$ can be chosen to be one of the six lines guaranteed by the nondegeneracy axiom (Axiom 3).)

02.99 BON (8+6 points)   Let $\calP=(P,L,I)$ be a finite projective plane and let $p\in P$ be a point. Let $n=\deg(p)-1$. Prove:   (a)   every point has degree $n+1$ and every line has rank $n+1$   (b)   $|P|=|L|=n^2+n+1$. The value $n$ is called the order of the projective plane.
Note. This is the traditional notation and terminology for projective planes, so in the context of projective planes, the term "order" and the letter $n$ unfortunately mean a different thing than for hypergraphs in general. The reason why $n=\rank(\ell)-1$ and not $\rank(\ell)$ is that one of the points of each line can be treated as a "point at infinity" and $n$ counts the "finite" points of a line.

02.115 STUDY   Relations, equivalence relations, partitions. Fundamental theorem of equivalence relations (and, of intelligence). REAS224.50--4.99, 6.10--6.157 and 7.10--7.57. DO all exercises in these sections. Especially internalize the definitions. This material will be assumed in the course (as it surely has been assumed in all other math courses you have taken). Some of the basic concepts: relation (REAS22 4.80), domain and codomain of a relation, equivalence relation (REAS22 6.130), equivalence classes (REAS22 7.42), function (REAS22 6.15), domain, codomain, range, notation $B^A$ where $A,B$ are sets (REAS22 6.25), collision (REAS22 6.32), injection, surjection, bijection, injective/surjective/bijective proof (REAS22 6.77), permutation (REAS22 6.97), the meaning of the term "unique" (in math, for hundreds of years, not its distortion in recent technological jargon, see REAS22 6.16), Pigeonhole Principle (REAS22 6.44), partition (in math, history and politics, for hundreds of years, not its distortion in recent technological jargon, see REAS22 6.91), blocks (parts) of a partition, kernel of a function (REAS22 6.105), trichotomous relation (REAS22 7.10).

02.120 ORD (4 points)   REAS22 7.25 (count trichotomous relations)

02.123 ORD (6 points)   REAS22 7.29(b) (lower bound on the number of transitive relations)

02.126 BON (10 points)   REAS22 7.35 ("there is some order in every disorder")

02.131 ORD (1+9 points)   Prove the Fundamental Theorem of Equivalence Relations (REAS22 7.40). Use the outline given in REAS22 7.45. At each step of the proof, state, what property of equivalence relations and what previously proved statement you are you using.
Item (c) earns 9 points, all others combined 1 point.

02.134 GRASP   the significance of this theorem to concept formation - the key function of intelligence (COMMENT REAS22 6.157)

02.139 REVIEW   DEF of Bell numbers $B_n$ (REAS22 6.94). DO REAS22 6.95, 6.96.

02.142 ORD (5 points)   Prove:   $B_n \le n!$
Give an injective proof.

02.145 ORD (6 points)   Lower bound on the Bell numbers (REAS22 6.98)

02.148 BON (6 points)   Use the two preceding exercises to prove that $\ln B_n \sim n \ln n$.

02.155 DEF   Let $\calH=(V,\calE)$ be a hypergraph. We say that the set $A\subseteq V$ is independent if $(\forall E\in \calE)(E \not\subseteq A)$ (no edge is a subset of $A$). The independence number of $\calH$ is $$\alpha(\calH)=\max \{|A| \, :\, A\subseteq V\text{ is independent }\}\,.$$

02.158 BON (14 points, due Apr 8)   Let $r\ge 1$. Let $\calH=(V,\calE)$ be an $r$-uniform regular non-empty hypergraph. ("Regular" means every vertex has the same degree. "Non-empty" means $\calE\neq \emptyset$, see DEF 02.10.) Prove:   $\alpha(\calH)\le n(1-1/r)$ (where $n=|V|$ is the order of the hypergraph).
Elegance matters.

More to follow. Please check back later.

Material covered:   Extremal combinatorics. Eventown Theorem (stated). Oddtown Theorem (stated). Asymptotic equality. Stirling's formula (stated). Prime Number Theorem (stated).

01.15 STUDY   LinAlg, Chapter 3 (Matrix rank), Chapter 6 (Determinant), Chapter 14 (Algebra)

01.20 STUDY   ASY, Chapters 1-2 (Sequences), Chapter 3 (Limits)

01.31 ORD (4 points)   ASY 1.10 (negate the sentence that "the sequence $S$ is eventually nonzero" in plain English)

01.35 ORD (7 points)   ASY 2.12 (periodicity of $(F_n \bmod m)$)

01.40 DO   ASY 2.14 (golden ratio)

01.43 DO   ASY 2.15 (ratio of diagonal to side of pentagon))

01.45 ORD (4 points)   ASY 2.17 (ratio of Fibonacci-type geometric progressions)
Clarification [03-23 at 20:16]   The question is about nonzero geometric progressions: at least one of the terms of the sequence is not zero.

01.48 DO   ASY 3.13--3.28

01.51 DO   ASY 4.24 (subadditivity/submultiplicativity of limsup)

01.54 ORD (5 points)   ASY 4.26 (a) (limsup of sum of bounded sequences)

01.59 DO   ASY 5.5 (a,b,c,d) asymptotics of polynomials and rational functions

01.62 ORD (4 points)   ASY 5.5 (e) (asymptotics of binomial coefficient $\binom{n}{5}$)
You may use 01.125.

01.65 DO   ASY 5.8 (a,b,c)

01.68 ORD (5 points)   ASY 5.8 (d) asymptotics of $\sqrt{n^2+1}-n$

01.71 ORD (4 points)   ASY 5.9 (a) (asymptotics vs. derivative)

01.74 ORD (4 points, due Apr 1)   ASY 5.10 ($a_n\sim b_n$ but $a_n^n \nsim b_n^n$)

01.77 ORD (5 points)   ASY 5.12 (asymptotics of middle binomial coefficient).
You may use 01.125.

01.81 DO   ASY 6.3 ($\sim$ an equivalence relation)

01.84 DO   ASY 6.4 (a,b) (addition of asymptics equalities)

01.87 ORD (7+7 points)   ASY 6.5 (a,b) (asymptotics of logarithm)

01.89 DO   ASY 6.7 (sqeeze principle for asymptotic equality)

01.92 ORD (5 points)   ASY 6.8 (a) (lower bound for $n!$)

01.95 DO   ASY 6.8 (b,c)

01.98 DO   ASY 6.9 (a) (asymptotics of $\ln(n!)$ using Stirling's formula)

01.101 ORD (7 points)   ASY 6.9 (b) (asymptotics of $\ln(n!)$ without Stirling's formula)

01.104 BON (10 points)   ASY 6.10 ($p_n \sim n\ln n$)

01.107 CH   ASY 6.11 (product of small primes)

01.115 BON (8+3 points, due Apr 1)   Let $\Omega$ be a set of $n$ elements. Let $A_1,\dots,A_m\subseteq \Omega$ such that

•   $(\forall i)(|A_i| \ge 6)$
•   $(\forall i\neq j)(|A_i\cap A_j| \le 5)$

01.119 Notation   $\nnn :=\{1,2,3,\dots\}$ denotes the set of natural numbers. We write $\nnn_0$ to denote the set of non-negative integers: $\nnn_0:=\{0,1,2,\dots\}=\nnn\cup\{0\}$. For $n\in\nnn_0$ we write $[n]:=\{1,\dots,n\}$. So $[3]=\{1,2,3\}$, $[1]=\{1\}$, $[0]=\emptyset$. We say that set is even if it has an even number of elements, and odd if it has an odd number of elements. Note that $\emptyset$ is even.

01.121 Notation   Let $\Omega$ be a set of $n$ elements $(n\in\nnn_0)$. For $k\in\nnn_0$ we write $$ \binom{\Omega}{k} = \{\left. B\subseteq\Omega\, \right|\, |B|=k\}\,.$$ We define $\binom{n}{k}$ by $$ \binom{n}{k} := \left|\binom{\Omega}{k}\right| $$

01.123 DO   If $k > n$ then $\binom{n}{k}=0$.

01.125 DO   For $n,k\in\nnn_0$ $$\binom{n}{k} = \frac{n(n-1)\cdot\cdot\cdot(n-k+1)}{k!}\,$$ Observe that this equation is valid even $n < k$.

01.128 DO (Binomial Theorem)   For $n\in\nnn_0$, the Binomial Theorem says that $(x+y)^n = \sum_{k=0}^n \binom{n}{k}x^k y^{n-k}$.
The most useful form of the Binomial Theorem uses only one variable: $$(1+x)^n = \sum_{k=0}^{\infty} \binom{n}{k}x^k \,.$$

01.131 DO   Let $E_n$ denote the set of even subsets of $[n]$ and $O_n$ the set of odd subsets of $[n]$. Prove: for $n\in\nnn$ we have $|E_n|=|O_n|$. Note that for $n=0$ we have $|E_0|=1$, $|O_0|=0$. Give two proofs:
  (a)   algebra proof (use the "most useful form" of the Binomial Theorem)
  (b)   bijective proof (construct a simple bijection from $E_n$ to $O_n$).

01.134 DO   Prove:   $$\sum_{i=0}^{\infty} \binom{n}{2i} = \begin{cases} 1 &\text{ if } n=0 \\ 2^{n-1} & \text{ if } n\ge 1 \end{cases} $$ (Note that for $i > n \ge 0$ we have $\binom{n}{i}=0$ by definition.)

01.137 BON (8 points, due Apr 1)   For $n,k\in\nnn$ let $$S(n,k) := \sum_{i=0}^{\infty} \binom{n}{ik}\,.$$ Prove:  $$ \left| S(n,3) - \frac{2^n}{3}\right| < 1\,.$$ Elegance counts.

01.145 DEF   Let $\Omega$ be a set of $n$ elements and let $C_1,\dots,C_m \subseteq\Omega$.
We say that $C_1,\dots,C_m$ form an Eventown system in $\Omega$ if

•   $(\forall i,j\in [m])(C_i = C_j \Leftrightarrow i=j)$
•   $(\forall i,j\in [m])(|C_i\cap C_j|\text{ is even})\,.$
  Note in particular that $(\forall i\in [m])(|C_i|\text{ is even})\,.$
  

•   $(\forall i\in [m])(|C_i|\text{ is odd})\,$
•   $(\forall i, j\in [m])(i\neq j \Rightarrow |C_i\cap C_j|\text{ is even})\,.$

01.148 CH (due Apr 1) (Eventown Theorem, Elwyn Berlekamp 1969)   In an Eventown system, $m \le 2^{\lfloor n/2\rfloor}$.

01.151 ORD (6 points)   Prove that the bound in the Eventown Theorem is tight, i.e., $m = 2^{\lfloor n/2\rfloor}$ is achievable for all $n$.

01.154 Oddtown Theorem (E. Berlekamp 1969)   In an Oddtown system, $m \le n$.

01.156 DO   Show that the bound in the Oddtown Theorem is tight for every $n$, i.e., the value $m=n$ can be achieved.
Proof.   Take the "singles clubs" $(\forall i)(|C_i|=1)$.

01.159 BON (7 points)   Let $C_1,\dots,C_m$ be an Oddtown system in $\Omega$ and let $\bfv_1,\dots,\bfv_m$ be the corresponding incidence vectors. Prove that the $\bfv_i$ are linearly independent over $\qqq$.
(Note that the Oddtown Theorem follows from this.)
Update [3-24 at 20:41] Typo fixed: $\bfv_n \to \bfv_m$.

01.161 BON (7 points, due Apr 1)   Let $A$ be an $m\times n$ matrix with rational entries. Prove:   $\rank_{\qqq}(A)=\rank_{\rrr}(A)$.

01.163 DEF   We say that an Oddtown system is maximal if no club can be added under the Oddtown rules. We say that an Oddtown system is maximum if there is no larger Oddtown system (i.e., $m=n$).

01.164 ORD (7 points)   For every $n\in\nnn$ determine the minimum number of clubs in a maximal Oddtown system.

01.166 DO   Every maximum system is maximal, but not conversely.

01.168 CH   Prove: for every $\epsilon > 0$ there exists $n_0\in \nnn$ such that for all $n\ge n_0$ the number of maximum Oddtown systems is at least $2^{(1-\epsilon)n^2/8}$.

01.171 CH (due Apr 8)   Prove: every maximal Eventown system is maximum (i.e., it has size $m=2^{\lfloor n/2\rfloor}$).

01.174 CH (due Apr 1)   Prove: for all sufficiently large $n$ there exist non-isomorphic maximum Eventown systems.