"LinComb" refers to the online text Linear Algebra Methods in Combinatorics by Peter Frankl and the instructor.
The notation "DMmini 4.1.15" refers to the instructor's Discrete Mathematics Lecture Notes, mini version, Chapter 4, problem 4.1.15.
The notation "DMmaxi" refers to the instructor's Discrete Mathematics Lecture Notes, expanded version.
The notation "LinAlg 6.1.14" refers to the instructor's Linear Algebra text, Discover Linear Algebra, Chapter 2, exercise 6.1.14.
The notation "PROB 7.7.22" refers Exercise 7.7.22 in the handout Finite Probability Spaces. Note: Last updated on April 16, 2020. Check that this date appears right under the title. If an earlier date is shown, you are looking at an older cached version. Refresh your browser.
The notation "ASY 2.21" refers to problem 2.21 in the Asymptotic Equality and Inequality handout.
"DO" problems are strongly recommended to check your understanding of the concepts; do not hand them in.
Problems labeled "HW" must be submitted by noon on Canvas each Tuesday unless expressly stated otherwise.
BONUS PROBLEMS contribute to your grade but you are not required to solve them unless you are looking for a grade of A or A-. However, you are required to read and understand them and use them in solving future problems. Bonus problems are underrated, so solve the ordinary HW problems first. For a grade of A you need to earn at least 50% of the Bonus points (in addition to most of the ordinary HW points). For a grade of A- you need to earn at least 25% of the Bonus points (in addition to most of the ordinary HW points).
CHALLENGE PROBLEMS have no point value (but they earn you the
instructor's attention) and no deadline (except they expire when
discussed in class). Make sure you hand them in on a separate sheet,
state your name, the fact that this is a challenge problem
solution, and indicate the problem being solved. One further
request: if you hand in a solution a challenge problem, send email to the
instructor giving the problem number and the brief indication of the
problem. Such email will create an easy record and help avoid mistakes
in my records.
REWARD PROBLEMS are challenge problems that you should NOT hand in.
The solution is its own reward. No deadline. Of course you may discuss
your thoughts with each other, the TA, and the instructor.
If you suspect an error, please notify the instructor by email.
If you are the first to report a serious error, you may earn bonus points.
Stating that the exercise is wrong and giving a counterexample
will not earn you the credit - report it (along with a possible fix
if you see one). Please also report if the exercise seems too
easy for the number of points given; this may again be a sign of
an error, and the straightforward solution will not earn you the credit.
Apply your critical thinking to whatever the instructor says
or writes.
PROVE YOUR ANSWERS
unless it is expressly stated that no proof is required.
NOTE: the last problem session will be Wednesday, June 3
and the last class Thursday, June 4.
9.05 STUDY the slides and the synopsys of the May 26 class
(click "Slides" on the banner) to learn about the Chebyshev
polynomials and their application to approximate Inclusion-Exclusion
via LP duality.
9.07 STUDY the slides and the synopsys of the May 28 class
to review variance, the Chernoff bound, and discrepancy theory.
9.10 DEF The Chebyshev polynomial of the first kind of degree
$k$ is defined as the polynomial $T_k(x)$ that satisfies the identity
$\cos(k\theta)=T_k(\cos\theta)$. The first few polynomials in this
sequence are
9.12 DEF The Chebyshev polynomial of the second kind of degree
$k$ is defined as the polynomial $U_k(x)$ that satisfies the identity
$\displaystyle{\frac{\sin((k+1)\theta)}{\sin(\theta)}=U_k(\cos\theta)}$.
The first few polynomials in this sequence are
9.14 HW (6 points, due Tuesday, June 2)
Prove the recurrence $T_k(x)=2x\cdot T_{k-1}(x)-T_{k-2}(x)$ $(k\ge 2)$.
Use the identity
$\cos(\alpha+\beta)+\cos(\alpha-\beta)=2\cos(\alpha)\cos(\beta)$.
9.16 DO
Prove the recurrence $U_k(x)=2x\cdot U_{k-1}(x)-U_{k-2}(x)$ $(k\ge 2)$.
Note that this is the same recurrence as for the Chebyshev polynomials of
the first kind; the only difference is in the initial values, specifically,
the case $k=1$: $T_0(x)=U_0(x)=1$, $T_1(x)=x$, $U_1(x)=2x$.
Use the identity
$\sin(\alpha+\beta)+\sin(\alpha-\beta)=2\sin(\alpha)\cos(\beta)$.
9.18 DO Show that $T_k(x)$ has degree $k$ and its leading
coefficient (the coefficent of $x^k$) is $2^{k-1}$ except for $k=0$.
9.20 DO Show that $U_k(x)$ has degree $k$ and its leading
coefficient is $2^k$.
9.22 DO Prove that the generating function of the $T_k$ is
$\displaystyle{\sum_{k=0}^{\infty} T_k(x)\cdot t^k =
\frac{1-tx}{1-2tx+t^2}}$
9.24 DO Prove that the generating function of the $U_k$ is
$\displaystyle{\sum_{k=0}^{\infty} U_k(x)\cdot t^k =
\frac{1}{1-2tx+t^2}}$
9.26 DO Prove the following explicit formula for $T_k(x)$:
9.28 DO Prove the following explicit formula for $U_k(x)$:
9.30 DO Show that all the roots of $T_k(x)$ are real and distinct:
the roots are $\cos(\theta_j)$ for $j=1,\dots,k$, where
$\theta_j = \frac{2j-1}{2k}\cdot\pi$. Note that
$0 < \theta_1 <\dots <\theta_k <\pi$
and $1 > \cos(\theta_1) > \dots > \cos(\theta_k) > -1$.
9.32 DO Show that all the roots of $U_k(x)$ are real and distinct.
Find the roots.
9.40 DO (a) Show: if $-1\le x\le 1$ then $|T_k(x)|\le 1$.
(b) Show that there are exactly $k+1$ values of $x$ where
$|T_k(x)|=1$ and the sign of $T(x)$ alternates along these values.
More formally,
there exist $k+1$ values $\lambda_0 <\lambda_1 <\dots <\lambda_k$
such that $|T_k(x)|=1$ if and only if $x$ is one of the $\lambda_i$.
Moreover, $T(\lambda_i)=(-1)^{k-i}$.
(c) It follows that the roots of $T_k(x)$ are in the $k$ open intervals
between the consecutive $\lambda_i$. (d) Determine the $\lambda_i$.
9.42 DO Note that $2^{1-k}T_k(x)$ is a monic polynomial of
degree $k$ (so the leading term is $x^k$) with real coefficients.
such that for all $x$ in the interval
$-1 \le x \le 1$ we have $|2^{1-k}T_k(x)|\le 2^{1-k}$.
9.44 Bonus (18+8 points, due Wednesday, June 3) (Extremal property
of Chebyshev polynomials) Let $p(x)$ be a monic polynomial
of degree $k$ with real coefficients.
Let $M(p)=\max_{-1\le x\le 1} |p(x)|$. (This is the $L^{\infty}$ norm
of $p(x)$ over the $[-1,1]$ interval.) Prove:
(a) $M(p) \ge 2^{1-k}$. (b) Moreover, $M(p) = 2^{1-k}$ if and
only if $p(x)= 2^{1-k}T_k(x)$. Use only facts listed above.
9.50 DEF Let $x=(x_1,\dots,x_n)\in\rrr^n$. The most frequently
used norms in $\rrr^n$ are the $\ell_1$-norm
$\|x\|_1=\sum_{i=1}^n |x_i|$, the $\ell_2$-norm (euclidean norm)
$\|x\|_2=\sqrt{\sum_{i=1}^n x_i^2}$, and the $\ell_{\infty}$-norm
(max-norm) $\|x\|_{\infty}=\max_{i=1}^n |x_i|$.
9.52 DO $(\forall x\in\rrr^n)(\|x\|_1 \ge \|x\|_2 \ge \|x\|_{\infty})$
9.53 DO $(\forall x\in\rrr^n)(\|x\|_1\cdot\|x\|_{\infty}\ge \|x\|_2^2)$
9.54 DO $(\forall x\in\rrr^n)(\|x\|_1 \le \sqrt{n}\cdot\|x\|_2
\le n\cdot\|x\|_{\infty})$
9.60 Bonus (22 points, due Wednesday, June 3)
(balancing $\ell_2$-bounded vectors)
Let $u_1,\dots,u_n\in\rrr^n$.
Prove: If $(\forall i)(\|u_i\|_2\le 1)$ then
$\exists \epsilon_1,\dots, \epsilon_n \in \{1,-1\}$ such that
$\|\sum_i\epsilon_i u_i\|_{\infty}\le \sqrt{n}$.
9.62 THEOREM (Beck-Fiala, discrete version, proved in class)
If $\calH$ is a hypergraph with maximum degree $d$ then
$\disc(\calH) \le 2d$.
9.63 THEOREM (Beck-Fiala, continuous version: balancing $\ell_1$-bounded
vectors) Let $m,n\ge 1$.
Let $u_1,\dots,u_n\in\rrr^m$ be vectors with $\ell_1$-norm
$\|u_i\|_1\le 1$. Then there exist $\epsilon_1,\dots,\epsilon_n\in\{\pm 1\}$
such that $\|\sum_{i=1}^n \epsilon_i u_i\|_{\infty} \le 2$.
9.65 HW (10 points, due Tuesday, June 2) Prove that Theorem 9.62
(the discrete version) follows from Theorem 9.63 (the continuous version).
Your proof should be just a few lines.
9.67 HW (20 points, due Tuesday, June 2) (balancing $\ell_1$-bounded vectors)
Prove Theorem 9.63 (the continuous version of the Beck-Fiala
theorem). Adapt the proof of the discrete version learned in class. Present
a complete proof, do not omit important details. Your proof should be
understood by a reader who has not seen the proof of Theorem 9.62.
Statements like "this part of the proof goes like the discrete case"
will not be accepted.
9.75 HW (18 points, due Tuesday, June 2) (Multicolor discrepancy)
Let $\calH$ be a hypergraph with $m\ge 2$ edges.
By a $k$-coloring we mean a function $f:V\to [k]$.
(Not necessarily a legal coloring.)
We define the discrepancy of an edge $E$ under the
coloring $f$ as
$$\disc(E,f) = \max_{i\in [k]} \left||E\cap f^{-1}(i)|-\frac{|E|}{k}\right|,$$
the maximum difference between $|E|/k$, the average number of
occurrences of a color in $E$, and the actual number of
occurrences of a color in $E$.
Let $\disc(\calH,f)=\max_{E\in\calE}\disc(E,f)$ and
$\disc_k(\calH)=\min_f \disc(\calH,f)$ where the
minimum is taken over all $k$-colorings.
Let $k=6$.
Prove: $\disc_6(\calH) = O(\sqrt{n \ln m})$.
Use the probabilistic method. State the size
of the sample space of your experiment. Use the Chernoff
bound as stated in PROB, Theorem 7.11.6.
9.80 DO/Bonus
Let us say that a 3-uniform hypergraph is a pre-STS if
every pair of distinct edges shares at most one vertex.
More to follow. Please check back later.
8.01 REVIEW PROB, Section 10 (independence of random variables).
8.02 STUDY PROB, Section 11 (strong concentration: Chernoff bounds).
Learn the proofs of Theorems 7.11.2 and 7.11.7.
HW 8.10 (9 points, due Tuesday, May 26)
Lemma 2 in the May 19 slides states the following
trigonometric identity:
$$\sum_{k=1}^m \frac{1}{\sin^2{\frac{k\pi}{2m+1}}} =\frac{2m(m+1)}{3} \,.$$
Use this identity to prove the upper bound
$\displaystyle{\sum_{n=1}^{\infty} \frac{1}{n^2} \le \frac{\pi^2}{6}}$.
(In class we proved the matching lower bound.)
8.11 HW (9 points, due Tuesday, May 26)
Prove the trigonometric identity stated in the
preceding exercise. (Hint: use the cotangent identity proved in
class. The slides are posted.)
8.15 DEF Let $b_i > 0$. We say that the infinite product
$\prod_{i=0}^{\infty} b_i$ is convergent if the limit
$L = \lim_{n\to\infty} \prod_{i=0}^n b_i$ exists and $0 < L < \infty$.
So, for instance, the product $\prod_{i=2}^{\infty}(1-1/i^2)$ is
convergent, and the product $\prod_{i=2}^{\infty}(1-1/i)$ is
divergent.
8.16 DO Let $0 < a_i < 1$. Prove that the infinite product
$\prod_{i=0}^{\infty} (1-a_i)$ converges if and only if the
infinite sum $\sum_{i=0}^{\infty} a_i$ converges.
8.20 HW/Bonus
Let $o_n$ denote the number of partitions of the non-negative integer $n$
into a sum of positive odd terms ("odd-term partitions"),
and $d_n$ the number of partitions into a sum of distinct positive terms
("distinct-term partitions"). For instance, $o_6=4$ because the odd-term
partitions of $6$ are
$6=5+1$, $6=3+3$, $6=3+1+1+1$, and $6=1+1+1+1+1+1$.
We also have $d_6=4$ because the distinct-tem partitions of $6$ are
$6=6$, $6=5+1$, $6=4+2$, $6=3+2+1$. Note that $o_0=d_0=1$ on
account of the partition of $0$ as the empty sum.
(c) (Bonus, 15 points, due Friday, May 29)
Prove that $(\forall n)(o_n = d_n)$ by proving that $O(x)=D(x)$.
(A direct proof by other methods will not be accepted. Your proof
should make essential use of the product representation
of your generating functions.)
Structure your proof by stating a clear and simple lemma.
8.25 HW (8+9 points, due Friday, May 29)
For $1\le k \le n$, let $T(n,k)=\sum_{i=0}^k \binom{n}{i}$.
8.30 HW/Bonus Let $\nnn=\{1,2,3,\dots\}$ denote the set of
positive integers and $\nnn_0 = \{0,1,2,3\dots\}$ the set of
non-negative integers. Let $k\ge 2$ and let $A_1,\dots,A_k\subseteq \nnn$
be infinite arithmetic progressions: $A_i = \{a_i+kd_i \mid k\in\nnn_0\}$
where $a_i, d_i\ge 1$. We refer to $d_i$ as the increment
of the arithmetic progression $A_i$. Assume $\nnn$ is the disjoint
union of the $A_i$:
$\nnn = A_1\sqcup\dots\sqcup A_k$. (This means that the union of the
sets is $\nnn$ and the sets are pairwise disjoint.)
8.35 DEF (disrepancy)
Let $\calH = (V,\calE)$ be a hypergraph with $n$
vertices and $m\ge 2$ edges. Let $f: V\to \{1,-1\}$ be a 2-coloring
of $V$ (say $1$ is "blue" and $-1$ is "red") (not necessarily a
"legal coloring" of $\calH$ in the sense of chromatic theory).
The discrepancy of an edge $E\in\calE$ with respect to $f$ is
$\disc(E,f)=|\sum_{v\in E}f(v)|$. The discrepancy of $\calH$
with respect to $f$ is $\disc(\calH,f)=\max_{E\in\calE}\disc(E,f)$.
The discrepancy of the hypergraph $\calH$ is
$\disc(\calH)= \min_f \disc(\calH, f)$ where the minimum is taken
over the set of all functions $f:V\to \{1,-1\}$.
8.37 HW (2+2+5 points, due Tuesday, May 26)
(a) Prove: every hypergraph has discrepancy $\le (n+1)/2$.
(b) Prove: every $r$-uniform hypergraph has discrepancy $\le r$.
(c) For every $n\ge 2r$ find an $r$-uniform hypergraph
with $n$ vertices and discrepancy $=r$.
8.40 HW (18 points, due Tuesday, May 26)
Let $\calH$ be a hypergraph with $m\ge 2$ edges.
Prove: $\disc(\calH) < \sqrt{2n \ln(2m)}$.
Use the probabilistic method. State the size
of the sample space of your experiment.
8.42 CH (due Monday, May 25 because I may discuss it in
class on May 26) Let $d\ge 1$ be the maximum degree
of the hypergraph $\calH$. Prove: $\disc(\calH) \le 2d$.
8.47 Bonus (18 points, due Friday, May 29)
Prove that there exists a constant $c > 0$ such the following holds.
For every $n\ge 1$ and every sequence $a_1,\dots, a_n$ of non-zero
integers, $P(|\sum_{i\in I} a_i|\le c\sqrt{n}) \le 1/2$, where
$I\subseteq [n]$ is chosen uniformly from the powerset of $[n]$.
Estimate the asymptotic value $c$ you get. State the size of the sample
space of this experiment. (Note: the $a_i$ are given.
They are not random.) "Asymptotic value of $c$" means a value $c'$
such that for all $\epsilon > 0$, the statement is valid
with $c=c'-\epsilon$ for all sufficiently large $n$.
So there are two things to do: (1) show that there exists $c >0$
that works for all $n\ge 1$, and (2) give an asymptotic
estimate of $c$.
[Update: clarifications "$n\ge 1$" and "asymptotic value"
and the meaning of "asymptotic value" added 5-29 3:20pm.
Final clarification "So there are two things to do"
added 4:20pm]
8.50 DEF (the submatrix hypergraph)
Let us define the "$k\times \ell$ submatrix hypergraph" $\SUB_{k,\ell}$
as follows. Let $V = [k]\times [\ell]$ be the set of vertices.
A combinatorial rectangle
is a set of the form $K\times L$ where $K\subseteq [k]$ and
$L\subseteq [\ell]$. The edges of $\SUB_{k,\ell}$
are the combinatorial rectangles. So the number of vertices
is $n=k\ell$ and the number of edges $m=2^{k+\ell}$.
(DO: verify the last sentence.)
8.51 HW (7 points, due Tuesday, May 26)
Assume $k\le \ell$. Prove: $\disc(\SUB_{k,\ell})=O(\sqrt{k}\ell)$.
You may use any exercises above.
8.53 Bonus (15 points, due Friday, May 29)
Assume $k\le \ell$.
Prove: $\disc(\SUB_{k,\ell})=\Omega(\sqrt{k}\ell)$.
(So, combined with the preceding exercise, we have
the exact order of magnitude of the discrepancy of the
submatrix hypergraph: $\Theta(\sqrt{k}\ell)$.)
You may use any of the exercises above.
8.56 Bonus DO:
Let $A=(a_{ij})$ be an $n\times n$ Hadamard matrix.
Let $R$ be an $r\times s$ combinatorial rectangle in $[n]\times [n]$.
Prove: $|\sum_{(i,j)\in R} a_{ij}|\le \sqrt{rsn}$. (So we are
adding up the entries of an $r\times s$ submatrix, i.e., we are looking
at the disrepancy of one of the edges of $\SUB_{n,n}$ with respect
to the 2-coloring defined by the matrix $A$.) Your proof should
be no more than four lines.
8.58 DO:
Assume $k \le \ell$.
We know from Exercise 8.51 that $\disc(\SUB_{k,\ell})=O(\sqrt{k}\ell)$.
This means there exists a 2-coloring $f:[k]\times [\ell]\to \{1,-1\}$
such that $\disc(\SUB_{k,\ell}, f) = O(\sqrt{k}\ell)$. The proof
in Ex. 8.51 relies on a random coloring $f$ achieving this bound.
Find an explicit coloring $f$ that achieves this bound. "Explicit"
means that given the name of a vertex (i.e., a pair
$(i,j)\in [k]\times [\ell]$) one can compute the color of that vertex,
$f(i,j)$ in our case), in polynomial time. "Polynomial time" means
the number of computational steps is bounded by $O(N^c)$ for
some constant $c$, where $N$ is the bit-length of the input
(the name of the vertex) which can be taken to be
$\log_2 |V|$, so in our case $N=\log_2(k\ell)$.
8.65 REVIEW Ramsey's Theorem on the May 21 slides.
8.66 DEF: Consider a $k$-coloring $f :\binom{[N]}{r} \to [k]$
of the edges of the complete $r$-uniform hypergraph $K_N^{(r)}$.
We say that a subset $A\subseteq [N]$ is homogeneous
w.r.to $f$ if all $r$-subsets of $A$ get the same color,
i.e., if $f$ restricted to $\binom{A}{r}$ is constant.
8.67 DEF: (Erdös-Rado arrow symbol).
Let $N,n,r,k$ be positive
integers. The notation $N\to (n)_r^{\,k}$ means:
$$(\forall f:\binom{[N]}{r} \to [k])(\exists A\subseteq [N])
(|A|=n\text{ and } A \text{ is homogeneous })$$
8.70 Ramsey's Theorem:
$\displaystyle{(\forall n,r,k)(\exists N)(N\to (n)_r^{\,k})}\,.$
8.69 DEF (Ramsey numbers) The smallest $N$ such that
$N\to (n)_r^{\,k}$ is denoted $R_r^k(n)$
8.72 DEF (tower function) (recursive definition)
Let $\tower_0(x)=x$ and for $r\ge 0$
let $\tower_{r+1}(x)=2^{\tower_r(x)}$.
8.75 THEOREM (Erdös-Hajnal-Rado, 1965)
For all $r\ge 3$ we have
$\tower_{r-2}(\Omega_k(n^2))\le R_r^{k}(n) \le \tower_{r-1}(O_k(n))$
8.80 DO Let $A$ be a set of 5 points in the plane in general
position, meaning that no three are on a line. Prove:
There are four points among them that determine a convex 4-gon.
8.82 HW (16 points, due Friday, May 29) Use Ramsey's Theorem
and the preceding exercise to
prove that there exists a function $f:\nnn\to\nnn$ such that
$(\forall n\in\nnn)($if $A$ is a set of $f(n)$ points in the plane
in general position then there is subset $S\subseteq A$ of size $n$
that determines a convex $n$-gon$)$. Determine the upper bound you get
using the Erdös-Hajnal-Rado bound on the corresponding Ramsey
number.
-- Solutions that do not use Ramsey's Theorem and the
Erdös--Hajnal--Rado bounds stated above will not be accepted.
8.85 THEOREM (lower bound: Erdös, 1947)
$\displaystyle{2^{n/2} < R_2^{\,2}(n) < 4^n}$
8.87 Remark. With this lower bound, Paul Erdös
inaugurated the probabilistic method of proving
the existence of objects without constructing them.
The lower bound in Theorem 8.85 asserts that
$2^{n/2} \not\to (n)_2^2$, i.e., there exists a 2-coloring
of the edges of the complete graph on $2^{n/2}$ vertices such that
there is no homogeneous subset of size $n$ in either color.
Explicit constructions of colorings verifying $N\not\to (n)_2^2$
are only known for much smaller values of $N$. The following
exercises provide such colorings.
8.89 HW (9+4 points, due Friday, May 29)
(a) Give a very simple 2-coloring of $\binom{[N]}{2}$ for $N=(n-1)^2$
that verifies the relation $N\not\to (n)_2^2$. The proof that
your coloring is correct should not be more than two lines,
from first principles (not using any theorem).
(b) Both 8.89 (a) and 8.91 establish constructive lower bounds for
the Ramsey numbers $R_2^2(n)$. State the lower bounds given by
each and compare them: for what values of $n$ does 8.89 give a
stronger result?
8.91 Bonus (16 points, due Friday, May 29)
The following 2-coloring of $\binom{[N]}{2}$ was given
by Zsigmond Nagy (1973) for $N=\binom{n-1}{3}$.
The set of vertices is $\binom{[n-1]}{3}$. Let
$A, B\in \binom{[n-1]}{3}$ be two distinct vertices.
Define $f(A,B)=1$ if $|A\cap B|=1$, and $f(A,B)=0$ otherwise.
Prove that this 2-coloring verifies the relation
$N\not\to (n)_2^2$ for $N=\binom{n-1}{3}$. You need to prove
two things: that there is no homogeneous subset of size $n$
of color 1, and that there is no homogeneous subset of size $n$
of color $0$. In each case, use results we proved earlier
in class or in homework in the area of extremal hypergraphs
(max number of edges under some conditions on the hypergraph),
with the effect that your proof should consist essentially
only of these two references. Proofs that don't follow these
guidelines will not be accepted; the point is to find
links between various parts of the material covered.
8.100 DEF Let $\calH_i=(V_i,\calE_i)$ be hypergraphs $(i=1,2)$.
An $\calH_1\to\calH_2$ isomorphism is a bijection $f:V_1\to V_2$
such that a subset $A\subseteq V_1$ is an edge of $\calH_1$
if and only if $f(A)$ is an edge of $\calH_2$. We say that
$\calH_1$ and $\calH_2$ are isomorphic if there exists a
$\calH_1\to\calH_2$ isomorphism; we denote this circumstance
by $\calH_1\cong\calH_2$. An automorphism
of $\calH$ is a $\calH\to\calH$ isomorphism. So the automorphisms
are permutatins of the set of vertices. Let $\aut(\calH)$
denote the set of automorphisms of $\calH$. Note that $\aut(\calH)$
is a grouop under composition.
8.103 DEF The STS $(W,\calF)$ is a subSTS
of the STS $(V,\calE)$ if $W\subseteq V$ and $\calF\subseteq \calE$.
For instance, for $d\le e$, $\SET_d$ is a subSTS
of $\SET_e$.
8.105 Bonus (25 points, due Tuesday, June 2)
Prove: The Fano plane is not isomorphic to any subSTS
of $\SET_d$ for any $d$.
8.107 Bonus (15 points, due Tuesday, June 2)
Let $\calS_1$ and $\calS_2$
be STSs where $\calS_i$ has $n_i$ vertices. Assume
$\calS_2$ is a proper subSTS of $\calS_1$. ("Proper"
means $n_2 < n_1$.) Prove: $n_2 < n_1/2$.
8.110 Bonus (20 points, due Tuesday, June 2)
Let $\calS$ be an STS with $n$ vertices.
Prove: $\displaystyle{|\aut(\calS)|< n^{1+\log_2 n}}$.
8.114 DEF We specify a projective plane as an incidence
structure $\calP=(P,\calL,I)$ where $P$ is the set of points, $\calL$
is a set of lines, and $I\subseteq P\times\calL$ is the incidence
relation. A projective plane $\calP_2=(P_2,\calL_2,I_2)$ is a subplane
of the projective plane $\calP_1=(P_1,\calL_1,I_1)$ if $P_2\subseteq P_1$,
$\calL_2\subseteq \calL_1$, and $I_2=I_1\cap(P_2\times \calL_2)$.
In other words, if $p\in P_2$ and $\ell\in\calL_2$ then
$p$ is incident with $\ell$ in $\calP_2$ if and only if they are
incident in $\calP_1$.
8.115 DO (a) Let $\calP_i$ be a projective plane of order $n_i$
$(i=1,2)$. Suppose $\calP_2$ is a proper subplane of $\calP_1$.
Prove: $n_2 \le \sqrt{n_1}$. (b) Prove that there exist
infinitely many values of $n$ such that there exists a projective
plane of order $n$ that has a subplane of order $\sqrt{n}$.
(Such subplanes are called Baer subplanes.)
8.116 CH Let $\calP$ be a projective plane of order $n$.
Prove: $|\aut(\calP)| = n^{O(\log\log n)}$.
8.125 HW (12 points, due Friday, May 29)
Prove that the Prime Number Theorem $(\pi(x)\sim x/\ln x)$
is equivalent to the statement that $p_n \sim n\ln n$
where $p_n$ denotes the $n$-th prime number (so $p_1=2$,
$p_2=3$, $p_3=5$, $\dots$).
8.127 Bonus (15+9 points, due Tuesday, June 2)
(a) Let $q$ be a prime power. Let $u_q(n,k)$ denote the
number of $k$-dimensional subspaces of $\fff_q^n$. Give
a simple formula for $u_q(n,k)$ that is a closed-form expression
for every fixed $k$. (b) Compute $\lim_{q\to 1} u_q(n,k)$
($n,k$ are fixed, $q$ is a real variable that you can plug into
your formula). Your answer should be a very simple and familiar
expression.
7.01 STUDY the new handout:
Log-asymptotics of products of factorials.
7.08 HW (10 points, due Tuesday, May 19)
Let $\calH$ be a $\tau$-critical
$r$-uniform hypergraph with $\tau(\calH)= t$ $(r,t\ge 2)$. Then
the number of edges of $\calH$ is
$$ m \le \binom {r+t-1}{r} $$
Deduce this result from Bollobás's Theorem, numbered 6.46 below.
This result, conjectured by Erdös, was Bollobás's
original motivation.
7.10 TERMINOLOGY. A graph is a 2-uniform hypergraph.
Two vertices that form an edge are called neighbors.
7.11 HW (8 points, due Tuesday, May 19)
A village graph is a graph where every pair of distinct
vertices shares exactly one common neighbor. ("Village graph"
is not standard terminology.) Example: a triangle, i.e.,
the complete graph on 3 vertices.
7.12 Bonus (25 points, due Tuesday, May 26)
Prove: in a village graph, there is a vertex that is a neighbor
of all other vertices.
You may use any problem stated in this section (HW set #7)
or earlier. State what you use.
7.13 Bonus (18 points, due Tuesday, May 26) "Gwennie's challenge"
Let $\calH=(V,\calE)$ be a hypergraph with at least one
non-empty edge. Prove: there exists a non-empty edge such that
the average degree of the vertices of that edge is not
less than the overall average degree. So we need to show that
there exists an edge $E\in\calE$, $E\neq\emptyset$ such that
$$ \frac{\sum_{v\in V} \deg(v)}{|V|} \le
\frac{\sum_{v\in E} \deg(v)}{|E|} $$
(Problem proposed by your classmate Gwendolyn Gilbert-Snyder.)
7.15 REVIEW the notions of divisibility and gcd from DMmini, Section 4.1.
Understand in particular that $0 \mid 0$ and $\gcd(0,0)=0$.
7.20 DEF/DO Let $A\in M_n(\zzz)$ (an integral matrix).
We say that $A$ is unimodular if $\det(A)=\pm 1$.
Prove: $A \in M_n(\zzz)$ has an integral inverse if and only if
$A$ is unimodular.
7.22 DEF An $k\times n$ integral matrix $B=(b_{ij})\in\zzz^{k\times n}$
is in Smith Normal Form if (1) $(\forall i\neq j)(b_{ij}=0)$
(2) $b_{11} \mid b_{22} \mid b_{33} \dots$ (each diagonal entry divides
the next one).
7.24 DEF/DO Let $A\in\zzz^{k\times n}$ be an integral matrix of
rank $r$.
For $j\le \min\{k,n\}$, let $d_j(A)$ be the gcd of all $j\times j$ minors
(determinant of the intersection of a set of $j$ rows and $j$ columns).
Define $d_0(A):=1$. [Update: the word "determinant" added
in parenthetical explanation 5-18, 8pm]
7.26 DO/DEF Prove: for $1\le j\le \min\{k,n\}$ we have
$d_{j-1}\mid d_j$.
(Recall: $0\mid 0$.) NOTATION: For $1\le j\le r$ we set
$a_j(A) = d_j(A)/d_{j-1}(A)$. The integers $a_j(A)$ are called the
elementary divisors (also called invariant factors) of $A$.
For $r+1\le j\le \min\{k,n\}$ we set $a_j(A)=0$. With this convention
we have $d_j(A) = \prod_{i=1}^j a_i(A)$ for all $j$ in the range
$0\le j \le {\min\{k,n\}}$.
7.28 THEOREM Let $a_j(A)$ be the elementary divisors of the matrix
$A\in \zzz^{k\times n}$. Then $a_j(A) \mid a_{j+1}(A)$ for $1\le j \le r-1$
where $r=\rank(A)$.
7.30 DO Let $A\in \zzz^{k\times n}$, $K\in M_k(\zzz)$, and $L\in M_n(\zzz)$.
Assume $K$ and $L$ are unimodular. Prove: $\rank(A)=\rank(KAL)$ and
$A$ and $KAL$ have the same invariant factors (and therefore also
the same determinantal divisors).
7.32 DO
(a) Given a matrix $A=(v_1,\dots,v_n)\in M_n(\zzz)$ (the $v_i$ are
the columns), the effect of the elementary column operation
$v_i \leftarrow v_i-\lambda v_j$ ($i\neq j$) is that we multiply
$A$ to the right by a certain unimodular matrix. Which matrix?
7.34 DO Let $B\in\zzz^{k\times n}$ be in Smith normal form. Prove
that its diagonal entries $b_{11}, b_{22},\dots,b_{rr}$ are its
elementary divisors.
7.33 THEOREM (Smith Normal Form Theorem) Given
$A\in \zzz^{k\times n}$ there exist unimodular matrices
$K\in M_k(\zzz)$ and $L\in M_n(\zzz)$ such that $KAL$ is in
Smith normal form. KAL is called the Smith normal form of $A$.
The Smith normal form of $A$ is unique.
7.36$^*$ DO Derive the Fundamental Theorem of Finitely Generated
Abelian Groups from the Smith Normal Form Theorem.
7.38 HW (6+6 points, due Tuesday, May 19)
Determine the Smith normal form of the following matrices.
7.40 HW (12 points, due Tuesday, May 19) True or false?
"The Smith normal form of a triangular
matrix depends only on the diagonal elements." If true, give a short proof.
If false, give the smallest counterexample.
7.42 Bonus (17 points, due Friday, May 22)
Let $p_1,\dots,p_n$ be distinct prime numbers.
Let $A=(a_{ij})$ be an upper triangular matrix with diagonal elements
$a_{ii}=p_i$. Determine the Smith normal form of $A$.
7.45 Bonus (19 points, due Friday, May 22)
Let $A\in M_n(\zzz)$ and let $p$ be a prime
number. Let $\rank_p A$ denote the rank of $A$ over $\fff_p$. Let
$k=\rank_p(A)$. Prove: $p^{n-k} \mid \det(A)$.
7.49 DO Prove: If $x$ is an odd number then $x^2\equiv 1 \pmod 8$.
7.51 HW (9 points, due Tuesday, May 19)
Let $n\equiv 6 \pmod 8$. Prove that there is no
projective plane of order $n$. Use the Bruck-Ryser Theorem.
Eventown math and the non-existence of projective planes.
The following exercises lead to an alternative proof of 4.51 and an
approach to proving non-existence of projective planes of order
$\equiv 2 \pmod 4$. It was used in the computer aided proof
of non-existence of projective planes of order 10.
7.52 TERMINOLOGY In the theory of error correcting codes,
a $k$-dimensional subspace $C\le \fff_q^n$ is called an $[n,k]$-code
over the field $\fff_q$. If $q=2$, the code is called a binary code.
Error-correcting codes are fundamental to audio and video recordings
and communication devices.
If $C\le \fff_q^n$ is an $[n,k]$-code then
the space $C^{\perp}$ is called the dual code, which is
an $[n,n-k]$ code. If $C=C^{\perp}$ then $C$ is called a
self-dual code. Self-dual codes played an important role
in the proof of non-existence of a projective plane of order 10.
Their role is shown in the following exercises.
7.53 DEF The weight of a vector $v=(v_1,\dots,v_n)\in \fff_q^n$
is the number of non-zero coordinates $v_i$. E.g., the weight of
$(0,1,7,0,0,0,2,2,0)$ is 4. Let $C\subseteq \fff_q^n$. The
weight enumerator of $C$ is the polynomial in two variables
$W_{C} = \sum_{i=0}^n w_i x^{n-i}y^i$ where $w_i$ denotes the number
of vectors of weight $i$ in $C$.
7.54 THEOREM (MacWilliams duality) Let $C\le \fff_2^n$ be
a $k$-dimensional subspace. Then
$$ W_{C^{\perp}}(x,y) = \frac{1}{2^k} W_C(x+y,x-y) $$
This identity was discovered by Florence Jessie MacWilliams (1917-1990),
who studied error-correcting codes at Bell Laboratories.
7.55 CH Prove the MacWilliams identity.
7.58 DEF Let $M$ be the incidence matrix of a projective
plane of order $n$. The rows of this matrix have length
$N=n^2+n+1$. Let us add a parity check bit to each row,
i.e., an $(N+1)$-st bit ($0$ or $1$) to make all row sums even.
7.60 HW (7 points, due Tuesday, May 19)
(We use the notation of DEF 7.58.)
Prove: If $n$ is even then $U$ is
totally isotropic, i.e., $U\subseteq U^{\perp}$.
7.62 Bonus (35 points, due Friday, May 22)
(We use the notation of DEF 7.58.)
Let $n\equiv 2\pmod 4$ and assume we have a finite projective
plane $\calP$ of order $n$. Let $U$ be the subspace of $\fff_2^{N+1}$
spanned by the rows of the augmented incidence matrix.
Prove: $U$ is a maximal totally isotropic subspace, i.e.,
$U = U^{\perp}$.
7.63 SIGNIFICANCE For self-dual codes $C\le \fff_2^n$, the
MacWilliams identity turns into a functional equation:
$W_C(x,y)=2^{-n/2}W_C(x+y,x-y)$. This equation places
strong constraints on the coefficients, many of which turn
out to be zero. This in turn eliminates most conceivable
configurations of points and lines, and helps to dramatically
reduce the search space so as to permit a successful computer
search to rule out the case $n=10$.
7.70 DEF Let $\calP=(P,\calL)$ be a finite projective plane.
A polarity is a bijection $f : P \to \calL$ such that
$(\forall p\in P)(\forall \ell\in\calL)(p\in\ell \iff f^{-1}(\ell) \in f(p))$.
We say that $p$ is a fixed point of the polarity if $p\in f(p)$.
7.72 Bonus (9 points, due Tuesday, May 19)
Prove: Every Galois plane has a polarity.
(A Galois plane is a projective plane coordinatized by a finite
field. Recall the homogeneous coordinates.)
7.73 DO Recall the characterization of degenerate projective
planes: There is a "long" line that contains all but one of the points.
All the remaining lines have two points each, connecting the extra
point to each point of the long line. In particular, the number
of points is equal to the number of lines.
7.74 HW (10 points, due Tuesday, May 19)
For what values of $n$ (number of vertices) does a degenerate
projective plane have a fixed-point-free polarity? (Use 7.73.)
[Update: clarification of the meaning of $n$ added 5-18, 7:40pm]
7.77 Bonus (32 points, due Tuesday, May 26) Prove: A finite
projective plane cannot have a fixed-point-free polarity.
Hint. Analyze the eigenvalues of the incidence matrix.
7.80 HW (9 points, due Tuesday, May 19)
Let $\calS$ be a STS with $n$ vertices.
Prove: $\alpha(S) = \Omega(\sqrt{n})$. ($\alpha$ denotes
the independence number.) In fact, prove that
every maximal independent set has size $\Omega(\sqrt{n})$.
Specify the constant implicit in the $\Omega$ notation;
try to make it as large as you can. Do not use 7.82.
7.82 Bonus (18 points, due Tuesday, May 19)
Let $\calS$ be a STS with $n$ vertices.
Prove: $\chi(S) = O(\sqrt{n})$.
7.84 Bonus (18 points, due Friday, May 22) Let $\calS$ be a STS
with $n > 3$ vertices. Prove: $\calS$ is not 2-colorable.
7.86 Bonus (21 points, due Tuesday, May 26) For every
$n\equiv 3 \pmod 6$, $n\ge 15$, construct a 3-colorable STS
on $n$ vertices. Make your construction easy to read.
7.95 DEF (a) The generating function of the sequence
$a_0, a_1, \dots$ is the power series
$$ f(x) = \sum_{n=0}^{\infty} a_n x^n $$
(b) The exponential generating function of the sequence
$a_0, a_1, \dots$ is the power series
$$ g(x) = \sum_{n=0}^{\infty} \frac{a_n}{n!} x^n $$
We treat these as formal power series, so we don't need to
worry about convergence issues. This does not cause problems
as long as we don't plug in non-zero values for the variable.
Examples: take the constant sequence $1,1,1,\dots$. The
generating function is $f(x) = \sum_{n=0}^{\infty} x^n = \frac{1}{1-x}$.
The exponential generating function is
$g(x) = \sum_{n=0}^{\infty} \frac{x^n}{n!} = \eee^x$.
These examples illustrate that for some sequences of interest
we get closed-form expressions for the generating function.
7.98 DEF The Fibonacci numbers are the numbers
$0,1,1,2,3,5,8,13,21,34,55,89,\dots$, formed from the
initial values $F_0=0$ and $F_1=1$ by the recurrence
$F_n = F_{n-1}+F_{n-2}$ $(n\ge 2)$.
7.99 DO Use the Fibonacci recurrence to prove that
the generating function of the Fibonacci numbers is
$$ \sum_{n=0}^{\infty} F_n x^n = \frac{x}{1-x-x^2} $$
7.100 DO (partial fractions) Prove:
$$\frac{x}{1-x-x^2} = \frac{A}{1-\alpha x} + \frac{B}{1-\beta x} $$
where $\alpha$ and $\beta$ are the roots of the polynomial
$x^2-x-1$, which is the reciprocal polynomial of the
denominator $1-x-x^2$, so $\alpha = (1+\sqrt{5})/2$ is the
golden ration and $\beta = (1-\sqrt{5})/2$ is the
negative reciprocal of the golden ratio. Moreover, $A=1/\sqrt{5}$
and $B=-1/\sqrt{5}$. So we have
$$ \frac{x}{1-x-x^2} =\frac{1}{\sqrt{5}}\sum_{n=0}^{\infty}
(\alpha x)^n - \frac{1}{\sqrt{5}}\sum_{n=0}^{\infty} (\beta x)^n.$$
By comparing the coefficients we obtain the remarkable explicit
formula $F_n = (1/\sqrt{5})(\alpha^n - \beta^n)$ for the
$n$-th Fibonacci number.
7.105 DEF $B_n$ - the $n$-th Bell number: number of
partitions of a set of $n$ elements, or equivalently,
the number of equivalence relations on such a set.
Example: $B_3 = 5$;
here are the five partitions of $[3]$:
7.106 HISTORICAL COMMENT. In a medieval Japanese parlor game called
genji-ko, guests were asked to determine an equivalence
relation among five objects (five packets of incense)
by smelling them. Diagrams depicted the $B_5=52$ possible
outcomes. (Wikipedia)
7.108 HW (6+8+10 points, due Friday, May 22)
(a) Prove: $B_n \le n!$
(b) Prove: for all $k$ in the range $1\le k\le n$
we have $B_n \ge k^{n-k}$ (c)
Prove: $\ln B_n \sim n\ln n$. Use (a) and (b).
Do not use the exercises below.
7.110 DO Prove the recurrence
$$ B_n = \sum_{k=0}^{n-1} \binom{n-1}{k} B_k \quad (n\ge 1) $$
7.112 REVIEW the proof, given in class, that the exponential generating
function of the Bell numbers is
$$ b(x) = \sum_{n=0}^{\infty} \frac{B_n}{n!} x^n = \eee^{\eee^x-1}$$
The proof is based on the recurrence 7.110.
7.114 HW (15 points, due Friday, May 22) Use the exponential
generating function of the Bell numbers to derive Dobiński's
formula (1877),
$$ B_n = \frac{1}{\eee}\sum_{k=0}^{\infty} \frac{k^n}{k!} $$
7.115 DO
Find the largest term in Dobiński's formula.
Let $k_n$ denote the value of $k$ for which $k^n/k!$ attains its maximum
for a given $n$. (a) Let $\lambda(n)$ denote the solution to the equation
$x\ln x=n$. Prove: $|k_n - \lambda(n)| <1$.
(b) Prove: $k_n \sim n/\ln n$. [Update: this problem
was updated 5-16 at 6am]
7.117 THEOREM (Leo Moser, Max Wyman, 1955)
$$ B_n \sim \frac{1}{\sqrt{n}}\lambda(n)^{n+1/2}\eee^{\lambda(n)-n-1}$$
A proof appears in Lovász's "Combinatorial Problems and Exercises"
listed on the course home page (Problem 1.9(b) in that book).
7.125 HW (13 points, due Friday, May 22)
Prove a statement of the following form:
7.130 DO Let $A,B,C,D$ be (not necessarily square) matrices for
which the products $AC$ and $BD$ make sense. Prove:
$(A\otimes B)(C\otimes D)=(AC)\otimes(BD)$.
7.132 DO Let $A\in M_k(\ccc)$ and $B\in M_n(\ccc)$. Let
the eigenvalues of $A$ be $\lambda_1,\dots,\lambda_k$ and
the eigenvalues of $B$ be $\mu_1,\dots,\mu_n$. Prove:
(a) $\trace(A\otimes B)=\trace(A)\cdot\trace(B)$.
(b) The
eigenvalues of $A\otimes B$ are $\lambda_i\mu_j$ $(1\le i\le k, 1\le j \le n)$.
Here the eigenvalues are listed with their multiplicities.
Remember that $A$ and $B$ are not necessarily diagonalizable.
7.135 DO Recall the Gale-Berlekamp switching game
from the slides of the May 14 class. In this game, two players,
the House and the Patron, play as follows. The House fills
every entry of an $n\times n$ matrix $A$ with $a_{ij}=\pm 1$.
The Patron is allowed to switch the sign of any set of rows
and columns. The payoff to the Patron is $\sum_{i=1}^n\sum_{j=1}^n a_{ij}$.
7.136 THEOREM. The value of this game is $\Theta(n^{3/2})$.
7.138 DO Suppose there exists an $n\times n$ Hadamard matrix $H$.
Prove: if the House presents $H$ to the Patron then the payoff will
be $\le n^{3/2}$.
7.140 Bonus (20 points, due Friday, May 22) Prove: the House can
achieve goal (2) of Theorem 7.136 for every $n$ (not only those $n$ for
which and $n\times n$ Hadamard matrix exists).
State and prove a clean lemma about certain matrices that does not
involve the game; use your lemma to solve this problem.
7.142 Bonus (28 points, due Friday, May 22) Prove: the Patron
can achieve goal (1) of Theorem 7.136. Use the following randomized
strategy, suggested in class. The Patron switches randomly selected columns,
deciding about each column with a flip of a fair coin. After this, flip
each row that has a negative sum. So in the end each row will have a
positive sum. Prove: the expected payoff is $\Omega(n^{3/2})$. Do not
use the Central Limit Theorem or other non-trivial tools of probability theory;
use only facts we proved in class or as homework.
7.144 CH (due Monday, May 25, by 11:59am, because I may discuss a solution
in class on Tuesday, May 26). Find an efficient
deterministic strategy for the Patron that is guaranteed to achieve
a payoff of $\Omega(n^{3/2})$. "Efficient" means the algorithm must
run in polynomial time, i.e., the number of computational steps should
be $O(n^c)$ for some constant $c$. State your exponent $c$ and briefly
justify it. Assume that multiplication of two $n$-digit numbers
takes $\Theta(n^2)$ steps (no fancy multiplication).
7.150 HW (1 point, due Friday, May 22) I would like the class to
be more interactive. My impression is that it is always the same 5 or 6
people who answer my questions or ask questions. Give me advice on
how I could help you personally become more active during class.
Get an early start on these problems.
6.1 STUDY the proof of the bound $(n+1)(n+4)/2$ on the
size of a 2-distance set in $\rrr^n$ from the
slides presented in class. (Click "Slides" on the banner.)
6.3 HW (14 points, due Friday, May 15)
Let $A=(a_{ij})\in M_n(\fff)$ where $\fff$ is an arbitrary
field. Let $B=(b_{ij})\in M_n(\fff)$ be defined by $b_{ij}=a_{ij}^2$
(we square every entry of $A$). Let $\rank(A)=r$. Prove:
$\rank(B) \le \binom{r+1}{2}$. -- You will get full credit
if you solve this problem over the reals ($\fff = \rrr$).
6.5 NOTATION For $1\le d\le n$ let
$B(n,d)=\sum_{k=0}^{\infty}\binom{n}{kd}$.
Note that this is a finite sum (because for $m > n$ we have
$\binom{n}{m}=0$). Not having to worry about the upper
limit of the summation is a notational convenience.
6.7 RECALL/DO: $B(n,2)= 2^n/2$ for $n\ge 1$.
Notice that $B(n,3) \neq 2^n/3$ (why?)
6.9 Bonus (16 points, due Friday, May 15)
Find an elegant expression for $B(n,d)$ that is
closed-form for every fixed $d$. In a closed-form expression,
there can be no summation or multiplication signs or dot-dot-dots.
If the expression is closed-form for every fixed $d$ then
it may have summations signs, but the number of terms in the summation
must depend on $d$ only, not on $n$, so for fixed $d$ we can get
rid of the summation. Hint: $B(n,2)= (1/2)((1+1)^n + (1-1)^n)$.
Use complex numbers.
6.10 Bonus (10 points, due Tuesday, May 19) Prove:
$\displaystyle{\left|B(n,3) - \frac{2^n}{3}\right| < 1}$.
6.12 MULTIVARIATE POLYNOMIALS. A monomial in the
the variables $x_1,\dots,x_n$ is a product of the form
$\prod_{i=1}^n x_i^{k_i}$. Example: $x_1x_3^7x_6^2$. Here,
if $n=7$, we have $k_1=1$, $k_3=7$, $k_6=2$, and
$k_2=k_4=k_5=k_7=0$. The degree of this monomial is $\sum_{i=1}^n k_i$.
The monomial of degree zero is the number 1.
A polynomial in the variables $x_1,\dots,x_n$ over the field $\fff$
is an $\fff$-linear combination (a linear combination with coefficients
from $\fff$) of monomials. If no monomial is repeated then
the degree of the polynomial $f$, denoted $\deg(f)$,
is the maximum degree of
the monomials involved with non-zero coefficient. The zero
polynomial is the empty sum of monomials; its degree is $-\infty$.
A multilinear monomial has all exponents $k_i$ equal to zero
or 1, e.g., $x_1x_3x_6$. A multilinear polinomial is
a linear combination of multilinear monomials. A polynomial
is homogeneous if it is a linear combination of
monomials of equal degree. Example: $x_1^3 + 8x_1x_3x_6 - 2x_2^2x_3$
is a homogeneous polynomial of degree 3.
Note that the zero polynomial is a homogeneous polynomial
of every degree.
6.13 DO Let $f,g\in\fff[x_1,\dots,x_n]$. Prove:
(a) $\deg(f+g)\le \max\{\deg(f),\deg(g)\}$
(b) $\deg(fg) = \deg(f)+\deg(g)$.
6.14 NOTATION/DO $\fff^{\le k}[x_1,\dots,x_n]$ denotes the
set of polynomials of deree $\le k$. Prove: this is a subspace
of the space $\fff[x_1,\dots,x_n]$ (i.e., it is closed under
linear combinations, including the empty linear combination, i.e.,
it includes the zero polynomial).
6.15 HW (4+4 points) (a) Determine the dimension of the space
of multilinear polynomials in $n$ variables.
(b) Determine the dimension of the space of homogeneous
multilinear polynomials of degree $k$ in $n$ variables.
In each case, give a simple formula; no proof required.
[Update: the word "homogeneous" was added in part (b) 5-11 at 6:40pm]
6.17 HW (9+7 points) (a) Determine the dimension of the
space of homogeneous polynomials of degree $k$ in $n$ variables.
(b) Determine $\dim \fff^{\le k}[x_1,\dots,x_n]$.
In both cases, your answer should be a simple
binomial coefficient expressed in terms of $n$ and $k$.
(Briefly reason your answers.)
6.25 DEF/DO Let $a,b\in\rrr^n$ be non-zero vectors. We say that the
angle between them is $\theta$ if
$a\cdot b = \|a\|\cdot\|b\|\cdot\cos\theta$. This defines a unique value
$-1 \le \cos\theta \le 1$ (why?). A line across the origin
is a one-dimensional subspace. We define the angle between two lines
as follows. We pick a non-zero vector on each line such that
their angle is between $0$ and $\pi/2$; this is the angle
between the lines. (So the cosine of angles between lines is
always non-negative.) A set of lines is equiangular
if they are pairwise at the same angle (same nonnegative cosine).
Example: the four diagonals of the cube, the six diagonals of the
icosahedron.
6.27 HW (12 points, due Friday, May 15)
Prove: If there exist $m$ equiangular lines in $\rrr^n$
then $m \le (n+1)(n+4)/2$. Your proof should be just
a few lines, using a fact proved in class.
[Update: By mistake, "Gram matrix" was given as a hint
to this problem. This hint was intended for the next problem.]
6.29 Bonus (12 points, due Friday, May 15)
Prove: If there exist $m$ equiangular lines in $\rrr^n$
then $m \le \binom{n+1}{2}$. Your proof should be just
a few lines, using a fact stated in these notes.
By solving this problem, you will NOT earn credit
for the preceding problem; for that problem, you need
to reference a result proved in class.
(Hint: Gram matrix.) [Update: Hint added 5-15, 9am]
6.40 THEOREM (Béla Bollobás, 1965)
Let $A_1,\dots,A_m, B_1,\dots,B_m$ be
$2m$ sets such that $(\forall i)(A_i\cap B_i=\emptyset)$
and $(\forall i\neq j)(A_i\cap B_j\neq\emptyset)$.
Then
$$ \sum_{i=1}^m \frac{1}{\binom{|A_i|+|B_i|}{|A_i|}} \le 1\,.$$
6.41 RECALL: The BLYM inequality states the following.
Let $\calF=\{F_1,\dots,F_m\}$ be a Sperner family, $F_i\subseteq [n]$.
Then
$$ \sum_{i=1}^m \frac{1}{\binom{n}{|F_i|}} \le 1\,.$$
(See Exercise 3.20.) We used this inequality to prove Sperner's Theorem.
6.42 HW (9 points, due Friday, May 15)
Derive the BLYM inequality from Bollobás's Theorem.
6.44 Bonus (18 points, due Friday, May 15)
Prove Bollobás's Theorem by a variant of the
permutation method we used to derive the BLYM inequality.
We may assume all the $A_i$ and $B_i$ are subsets of the
set $[n]$ for some $n$. Your creative job is to define,
when to consider a linear order $\sigma$ of $[n]$
"compatible" with the pair $(A_i,B_i)$.
Most of the credit goes for a simple and clear
definition of this concept. To emulate the
BLYM proof, you need to ensure that (1) for each
linear order $\sigma$ of $[n]$ there is at most one
$i\in [m]$ such that
$\sigma$ is compatible with $(A_i,B_i)$, and (2)
if we select $\sigma$ at random from all linear orders
of $[n]$ then the probability that $\sigma$
is compatible with a given pair $(A_i,B_i)$ is
$\displaystyle{\frac{1}{\binom{|A_i|+|B_i|}{|A_i|}}}.$
If these two conditions are satisfied, the claimed
inequality follows (how?).
6.46 THEOREM (Uniform version of Bollobás's theorem).
Let $r,s \ge 1$ and let $A_1,\dots,A_m, B_1,\dots,B_m$ be
$2m$ sets such that $(\forall i)(|A_i|=r \text{ and } |B_i|=s)$ and
$(\forall i)(A_i\cap B_i=\emptyset)$
and $(\forall i\neq j)(A_i\cap B_j\neq\emptyset)$.
Then $\displaystyle{ m \le \binom{r+s}{r}}$.
6.47 HW (9 points, due Friday, May 15)
Derive Theorem 6.46 from Theorem 6.40.
6.48 HW (5 points, due Friday, May 15)
Prove that Theorem 6.46 is tight for every $r,s \ge 1$.
6.53 Bonus (9+6 points, due Friday, May 15)
We say that the matrices $A,B\in M_n(\fff)$ commute
if $AB=BA$. Let $A_1,\dots,A_m,B_1,\dots,B_m\in M_n(\fff)$.
(a) Assume (i) $(\forall i)(A_i$ and $B_i$ do not commute$)$;
(ii) $(\forall i\neq j)(A_i$ and $B_j$ commute$)$.
Prove: $m \le n^2$. (b) Let us replace assumption (ii)
by the following weaker version:
(iii) $(\forall i < j)(A_i$ and $B_j$ commute$)$. (We omitted
half the conditions.)
Prove that (i) and (iii) still imply $m \le n^2$.
6.60 Bonus (Birthday paradox) (15 points, due Tuesday, May 19)
Let $f : [k]\to [n]$ be a random
function (chosen from the uniform distribution over $[n]^{[k]}$).
Let $P(n,k)$ denote the probability that $f$ is an injection
(has no collisions). Recall (from 2.53) that
$$P(n,k) = \frac{n(n-1)\cdots(n-k+1)}{n^k}=\prod_{i=1}^{k-1}\frac{n-i}{n}
= \prod_{i=1}^{k-1}\left(1 - \frac{i}{n}\right)$$
In class on May 7 we discussed the proofs of the following
two statements. Let $k_n$ be an infinite sequence of positive integers.
(a) If $k_n = o(\sqrt{n})$ then $P(n,k_n)\to 1$.
(b) If $\sqrt{n} = o(k_n)$ then $P(n,k_n)\to 0$. (Review these proofs.)
6.65 HW (14 points, due Tuesday, May 19)
Let $0\le k \le n$. Prove:
$\sum_{j=0}^{k} (-1)^{k-j} \binom{n}{j} \ge 0$.
6.67 REVIEW Inclusion-Exclusion.
Let $A_1,\dots,A_m\subseteq\Omega$ be events in
the probability space $(\Omega,P)$. Let $B = \bigcup_{i=1}^m A_i$.
For $I\subseteq [m]$ let $A_I = \bigcap_{i\in I} A_i$.
The Inclusion-Exclusion formula states that the probability
of the compement of $B$ is
$$ P(\Bbar) = \sum_{I\subseteq [m]} (-1)^{|I|} P(A_I)
= \sum_{j=0}^m (-1)^j S_j$$
where $S_j$ is the sum of the probabilities of the $j$-wise intersections:
$$S_j = \sum_{I\subseteq [m], |I|=j} P(A_I) .$$
Convention: $A_{\emptyset}= \Omega$ (the intersection of
nothing is everything). It follows that $S_0 = 1$.
6.69 Bonus (Bonferroni's inequalities) (16 points, due Tuesday, May 19)
We use the notation of 6.67. Let $0\le k\le m$. Prove:
6.71 HW (10 points, due Tuesday, May 19)
A function $f:A\to B$ is a surjection if $B$ is the range of $f$,
i.e., $f(A)=B$. In other words, $(\forall b\in B)(\exists a\in A)(f(a)=b)$.
More to follow. Please check back later.
5.1 STUDY the
Order Statistics
handout. In it we discuss conditional expectation and give an intuitive
solution to Bonus problem 3.45 (Order statistics).
5.2 STUDY the Linear Programming (LP) and Integer Linear Programming (ILP)
problems and the LP Duality Theorem from online sources, including
the synopsys and the slides of the Tuesday, April 28 lecture.
(Click "Slides" on the navigation bar.)
5.3 STUDY the concept of fractional matchings and fractional covers
from online sources, including the synopsys and the slides of the
Tuesday, April 28 lecture.
5.7 DO (Fixed-point-free permutations)
(See Exercise 3.57 for terminology and notation.)
As in Ex. 3.57, let $\FFE_n$ denote the number of fixed-point-free
even permutations and $\FFO_n$ the number of fixed-point-free odd
permutations of $[n]$.
5.10 NOTATION (prime counting function) For $x\in\rrr$,
$\pi(x)$ denotes the number of primes $\le x$. For instance,
$\pi(11)=5$, $\pi(100)=25$, $\pi(\pi)=2$, $\pi(\sqrt{2})=0$, $\pi(-5)=0$.
5.12 THEOREM (Chebyshev 1850) $\pi(x) = \Theta(x/\ln x)$.
5.13 THEOREM (Chebyshev 1850) If $\lim_{x\to\infty} \pi(x)/(x/\ln x)$
exists, then this limit is 1, i.e., $\pi(x)\sim x/\ln x$.
5.14 PRIME NUMBER THEOREM (PNT) (Hadamard and de la Vallée Poussin,
1896) $\pi(x) \sim x/\ln x$.
5.15 DO Let $p_n$ denote the $n$-th prime number, so $p_1=2$,
$p_2=3$, $p_3=5$, $\dots$. Prove that the following statement is
equivalent to the PNT: $p_n\sim n\ln n$.
5.16 DO Let $P(x)$ denote the product of all primes $\le x$.
Prove that the following statement is equivalent to the PNT:
$P(x) \approx \eee^x$ in the sense that their logarithms are
asymptotically equal: $\ln P(x) \sim x$.
5.17 Bonus (12 points, due Tuesday, May 12) Let $q$ be a
prime power (a number of the form $p^{\,t}$ for some prime number $p$
and $t\ge 0$). Prove: If $q$ is a divisor of the binomial coefficient
$\binom{n}{k}$ then $q\le n$. Your proof should be fairly short
and entirely elementary.
5.18 Bonus (12 points, due Tuesday, May 12) Use the preceding
exercise to give a very short and elementary proof of the result that
$\pi(x) = \Omega(x/\ln x)$ (the lower bound in Chebyshev's
result 5.12). (Calculus counts as elementary.)
Hint: Study the prime factorization of the middle binomial
coefficient $\binom{n}{n/2}$ for even $n$.
5.20 Bonus (12 points, due Tuesday, May 12) Prove: for $x\ge 0$
we have $P(x) \le 4^x$ where $P(x)$ is the product of all primes $\le x$.
Use the prime factors of the middle binomial coefficients. Your proof
should be fairly short and entirely elementary.
5.21 Bonus (12 points, due Tuesday, May 12) Use the preceding
exercise to prove that $\pi(x) = O(x/\ln x)$ (the upper bound in
Chebyshev's result 5.12). Your proof sould be very short and
entirely elementary. -- This will complete an elegant elementary
proof of Chebyshev's theorem 5.12 based on the study of the
middle binomial coefficients (Erdös, 1925; Erdös was
an undergraduate at the time).
5.30 TERMINOLOGY. A matrix of order $n$ is an $n\times n$ matrix.
5.31 DEF An Hadamard matrix is an $n\times n$ matrix
$H=(h_{ij})$ such that every entry of $H$ is $\pm 1$ and the columns
of $H$ are orthogonal. For instance, $S_1 = \begin{pmatrix} 1 & 1\\ 1 & -1
\end{pmatrix}$ is a $2\times 2$ Hadamard matrix. (Pronunciation:
In Hadamard's name, the letter "H" at the beginning and the letter "d"
at the end are silent. Each "a" sounds like the "a" in the word "art."
5.33 DO If $H$ is an $n\times n$ Hadamard matrix then
the $(2n)\times (2n)$ matrix $\begin{pmatrix} H & H \\ H & -H
\end{pmatrix}$ is again Hadamard. Starting from the
$2\times 2$ matrix $S_1$ described in the preceding problem,
we obtain inductively the $2^k\times 2^k$ Hadamard matrix
$S_k = \begin{pmatrix} S_{k-1} & S_{k-1}\\ S_{k-1} & -S_{k-1}
\end{pmatrix}$. The matrices $S_k$ are called Sylvester-Walsh
matrices.
5.35 DO Prove: the order of an Hadamard matrix is
either 1 or 2 or is divisible by 4.
5.37 CH Let $p=4k-1$ be a prime. Prove: there exists
an Hadamard matrix of order $p+1$.
5.39 Bonus (8 points) Prove: If there exist an Hadamard matrix
of order $k$ and an Hadamard matrix of order $\ell$ then
there exists an Hadamard matrix of order $k\ell$.
5.41 CONJECTURE For every $k\ge 1$ there exists an
Hadamard matrix of order $4k$.
5.43 NOTATION Let $h_1=1, h_2=2, h_3=4,\dots$ denote the sequence
of those numbers $n$ for which an Hadamard matrix of order $n$
exists. So the Conjecture above says that for $k\ge 3$ we have
$h_k = 4(k-2).$
5.44 OPEN PROBLEM True or false: $h_k = O(k)$.
5.45 DO Prove: $h_k = O(k \log k)$.
5.50 HW (8 points) Let $H$ be an Hadamard matrix of order $n$.
Prove: $|\det H|= n^{n/2}$.
5.52 Bonus (8 points, due Friday, May 8) Let $\lambda\in\ccc$
be an eigenvalue of an Hadamard matrix of order $n$. Prove:
$|\lambda|= \sqrt{n}$.
5.55 Bonus (14 points, due Tuesday, May 12)
Let $H$ be an Hadamard matrix of order $n$.
Prove: the absolute value of the sum of all
entries of $H$ is $O(n^{3/2})$. (This implies that
almost all terms in the sum cancel.)
5.58 DO$^*$ (Hadamard's inequality)
Let $A\in M_n(\rrr)$ with columns $a_1,\dots,a_n$.
Prove: $|\det(A)| \le \prod_{i=1}^n \|a_i\|$.
Hint. First, show that we may
assume that $(\forall i)(\|a_i\|=1)$. Then consider
the eigenvalues of the matrix $A^TA$.
5.60 DO Let $A=(a_{ij})\in M_n(\fff)$ and $x=(x_1,\dots,x_n)\in\fff^n$.
Verify: $x^TAx = \sum_{i=1}^n\sum_{j=1}^n a_{ij}x_ix_j$.
5.61 DEF Recall that a symmetric matrix $A\in M_n(\rrr)$
($A=A^T$) is positive semidefinite if
$(\forall x\in\rrr^n)(x^TAx \ge 0)$. We say that
$A$ is positive definite if
$(\forall x\in\rrr^n)(x\neq 0 \implies x^TAx > 0)$.
5.62 DO Prove: If $A, B$ are positive semidefinite
then so is $aA +bB$ for all $a,b\ge 0$.
5.63 DO Prove: if $A$ is positive definite and $B$ is positive
semidefinite then $aA+bB$ is positive definite for all $a >0$ and $b\ge 0$.
5.64 HW (6+6 points) (a) Prove: a diagonal matrix is positive
definite if and only if all diagonal entries are positive.
(b) The all-ones matrix $J_n\in M_n(\rrr)$ (all entries are 1)
is positive semidefinite.
5.65 HW (8 points) Let $A\in M_n(\rrr)$ be a positive semidefinite
matrix. Prove: $A$ is non-singular if and only if $A$ is positive
definite.
5.66 HW (7+5 points, due Friday, May 8) Let $v_1,\dots,v_m\in\rrr^n$.
Let $G$ denote the Gram matrix of this list of vectors. (a) Prove:
$G$ is positive semidefinite. (b) Prove: $G$ is positive definite
if and only if $v_1,\dots,v_m$ are linearly independent.
5.70 HW (8 points) Let $A=(a_{ij})\in M_n(\rrr)$. Let $b > 0$.
Assume all off-diagonal entries of $A$ are equal to $b$ and all
diagonal entries are greater than $b$. Prove that $A$ is non-singular.
5.71 CH (K. N. Majumdar) Give an explicit formula for the determinant
of the matrix $A$ described in the preceding exercise.
You formula should be simple enough to permit to
immediately conclude that $A$ is non-singular.
(This will be a more difficult route to solving the
preceding exercise than the one suggested by the above
sequence of exercises.)
5.75 HW (8 points) Let $\calH=([n],\calE)$ be a
hypergraphs with $\calE=\{E_1,\dots E_m\}$. Let $f \ge 0$.
Assume that for every $i$ we have $|E_i| > f$ and for
every $i\neq j$ we have $|E_i\cap E_j|=f$. Prove: $m\le n$.
(The notable difference compared to Exercise 3.18 is that we are
not assuming that $\calH$ is uniform.)
5.80 DO Let $\calP=(P,\calL)$ be a possibly degenerate finite
projective plane. ($P$ is the set of points and $\calL$ the set
of lines.) Let $p\in P$ and $\ell\in\calL$ be a point and a line
that are not incident. Prove: $\deg(p) = |\ell|$. (This problem
was discussed in a problem session.)
5.82 DO (a) Let $\calP=(P,\calL)$ be a finite projective plane.
Let $p \neq q\in P$. Prove: $(\exists \ell\in \calL)(\ell$ is not
incident with either $p$ or $q$. (b) Conclude that all
points have the same degree. (c) Infer that all lines have
the same size, and this size is the same as the degree of every point.
We call this common value $n+1$, and call $n$ the order of
the plane. In particular, this proves that finite projective
planes are regular and uniform hypergraphs.
5.84 DO Let $(P,\calL)$ be a finite projective plane of
order $n$. Prove: $|P|=|\calL|=n^2+n+1$.
5.86 HW (8 points, due Friday, May 8)
We defined possibly degenerate finite
projective planes as hypergraphs $(P,\calL)$ that satisfy
the first two axioms (every pair of points lies on a unique line,
every pair of lines intersects in a point) and the weaker third
axiom that there are 3 points not on a line (so not all points are
on a line). Prove: under these conditions, $|P|=|\calL|$.
(You may use any of the exercises above. Give a very short and
elegant proof -- no case distinctions.)
5.88 DO
A hypergraph is a degenerate finite projective plane
if it satisfies the first two axioms and the weaker third
axiom but not the stronger third axiom (so there are no four points
such that no three are on a line). In a breakout session, the
following degenerate projective planes were found: the plane has
one line, $\ell$, that has all but one of the points; call the
extra point $p$. So $p$ and $\ell$ are not incident.
The remaining lines have two points
each, connecting $p$ to each point of $\ell$. So again,
the number of points and the number of lines is equal,
as they should be according to Exercise 5.86.
Check that even though these hypergraphs are neither
regular nor uniform, they satisfy Exercise 5.80 (as they should).
Prove that there are no other degenerate projective planes.
So for every $n\ge 3$ there is exactly one degenerate projective plane
with $n$ points.
5.90 HW (2+3+10+2+4 points) Let $\calP=(P,\calL)$ be a
degenerate finite projective plane with $n$ points. Determine
(a) $\nu(\calP)$ (the matching number) (b) $\tau(\calP)$
(the covering number)
(c) $\tau^*(\calP)$ (the fractional covering number); state the
difference $\tau-\tau^*$ as a simple function of $n$
(d) $\alpha(\calP)$ (the independence number)
(e) $\chi(\calP)$ (the chromatic number).
5.92 HW (2+15 points) Let $\calP=(P,\calL)$ be a finite
projective plane of order $n$. Determine (a) the matching number $\nu$
and (b) the covering number $\tau$ of $\calP$. Express these values
in terms of $n$. Your proof should be very short.
(You may use the exercises above.)
5.94 HW (12 + 4 points) (a) Let $\calH=(V,\calE)$ be a
regular $k$-uniform hypergraph. Determine its fractional
matching number $\nu^*$ and fractional covering number $\tau^*$.
Express your answer as a function of $n$ (number of vertices)
and $k$. (b) Apply your result to finite projective
planes of order $r$: determine the fractional matching
number and the fractional covering number of a projective
plane of order $r$. Compare your result with the results
of Exercise 5.92. [Typo fixed May 4, 8:30pm.
Previous versions incorrectly referred to Exercise 5.70, then to 5.90.]
5.96 HW (7+7+9 points, due Friday, May 15):
Comparing random choice with the greedy bound.
Let $\calH=(V,\calE)$ be a non-empty regular $r$-uniform hypergraph
$(1\le r\le n-1)$.
We have shown that random choice leads to a cover of size
$\le \lceil(n/r)\ln m\rceil$ (Exercise 4.112). Lovász
has shown that the greedy cover algorithm leads to a cover of size
$\le \tau^* (1+\ln \deg_{\max})$ where $\deg_{\max}$ is the maximum
degree (in our case, the degree of each vertex).
The task is to compare the two bounds.
Let $P$ denote the probabilistic bound (ignore rounding),
and $G$ the greedy bound.
5.100 NOTATION (edge removal) Let $\calH=(V,\calE)$
be a hypergraph and $E\in\calE$. We denote the hypergraph
$(V, \calE\setminus\{e\})$ by $\calH-E$. Let $\calF\subseteq\calE$.
We denote the hypergraph $(V,\calE\setminus\calF)$ by $\calH-\calF$.
Hypergraphs of the form $\calH-\calF$ are called spanning
subhypergraphs of $\calH$. The word "spanning" refers
to the fact that we did not remove any vertices, we only
removed edges.
5.102 DEF We call the hypergraph $\calH=(V,\calE)$
$\tau$-critical
if $(\forall E\in\calE)(\tau(\calH-E) < \tau(\calH))$
(the removal of any of the edges reduces the covering number).
5.103 DO Prove: Every hypergraph $\calH$ contains a $\tau$-critical
spanning subhypergraph $\calH'$ such that $\tau(\calH')=\tau(\calH)$.
5.105 HW (7+7 points) (a) Determine the covering number
of the complete $r$-uniform hypergraph $K_n^{(r)}$ (DEF 4.78).
(b) Prove that $K_n^{(r)}$ is $\tau$-critical.
5.107 Bonus (10 points, due Friday, May 15)
Let $\calP=(P,\calL)$ be a finite projective
plane of order $k$. (So the number of points is $n:=k^2+k+1$,
and the same is the number of lines.) Is $\calP$ $\tau$-critical?
5.108 Bonus (9 points, due Friday, May 15)
Let $\calP=(P,\calL)$ be a finite projective plane of order $k$
and $\ell\in\calL$. Determine the fractional covering number
of $\calP-\ell$. (We remove $\ell$ from the set of edges but
do not change the set of vertices.)
5.120 DEF (orthogonal Latin squares)
Recall that two $n\times n$ Latin squares
$A=(a_{ij})$ and $B=(b_{ij})$ are orthogonal
if every pair $(k,\ell)\in [n]\times [n]$ occurs
exactly once as $(a_{ij},b_{ij})$. For instance,
the Latin squares $\begin{pmatrix} 1 & 2 & 3\\
2 & 3 & 1\\
3 & 1 & 2 \end{pmatrix}$
and $\begin{pmatrix} 1 & 3 & 2\\
2 & 1 & 3\\
3 & 2 & 1 \end{pmatrix}$
are orthogonal: if we superimpose them, we get the matrix
$\begin{pmatrix} 11 & 23 & 32\\
22 & 31 & 13\\
33 & 12 & 21 \end{pmatrix}$
with all the nine entries distinct.
5.122 HW (8 points, due Friday, May 8)
Prove: if $n\ge 3$ is odd then there exists
a pair of orthogonal Latin squares of order $n$ (i.e.,$n\times n$
Latin squares).
5.123 Bonus (8 points, due Friday, May 8)
Find three pairwise orthogonal $4\times 4$ Latin squares.
Describe how you constructed them. If you took it
from a source, describe how the source constructed them.
It your source does not tell, you cannot use it.
[The last three sentences were added May 6, 7:20am]
5.124 DO Prove: If there exists a pair of orthogonal Latin
squares of order $k$ and a pair of orthogonal Latin squares of
order $\ell$ then there exists a pair of orthogonal Latin squares
of order $k\ell$.
5.125 DO (a) Let $A_1,\dots,A_m$ be a set of pairwise
orthogonal Latin squares of order $n$. Prove: $m\le n-1$.
5.126 DO Infer from the preceding exercises that for
every $n\ge 3$, $n \not\equiv 2 \pmod 4$, there exists
a pair of orthogonal Latin squares of order $n$.
5.127 STORY (Euler's 36 officers problem) Leonhard Euler
proposed in 1782 the question whether there exists a pair of
orthogonal Latin squares of order 6 and expected a negative
answer. The non-existence of such a pair of Latin squares
was proved by Gaston Tarry in 1901. Contrary to expectation,
however, a pair of orthogonal Latin squares of order $4k+2$
was found for every $k\ge 2$ by R. C. Bose, S. S. Shrikhande,
and E. T. Parker in 1959, thus proving that a pair of
orthogonal Latin squares exists for every order $\ge 3$
with the sole exception of the order 6.
5.130 DO Infer from the results stated above that
no projective plane of order 6 exists.
The following sequences of exercises are in preparation for the
construction and counting of Latin squares.
5.140 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$.
5.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.
5.143 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.
5.145 THEOREM ("Marriage Theorem")
(Dénes König (1931), Philip Hall (1935))
If none of the Hall conditions is violated then $\calF$ has a SDR.
5.146 Historical remarks. This is one of the central results of
combinatorial optimization. It can be equivalently restated in
terms of bipartite graphs, and also in terms of $(0,1)$ matrices.
König's result is stronger than Hall's and asserts
that for bipartite graphs, $\tau = \nu$ (see Exercise 5.148 below),
anticipating combinatorial
duality theory; the method anticipates primal/dual algorithmic
techniques. The result (and the method) was immediately (1931)
extended to weighted bipartite graphs (the "assignment problem")
by Jenö Egerváry, König's colleague at the
Budapest University of Technology. These two papers appeared
in Hungarian in the same issue of the "Matematikai és
Fizikai Lapok."
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.
5.148 DO König's Duality Theorem (1931)
states that "$\tau = \nu$ for bipartite graphs."
Derive the Marriage Theorem from this result.
5.149 THEOREM (König 1916) Let $r\ge 1$. Every
$r$-regular $r$-uniform hypergraph has a SDR.
5.150 HW (9 points, due Tuesday, May 12) Prove the following stronger
result.
5.155 CH
Let $r\ge 1$. Prove: an $r$-regular $r$-uniform hypergraph
has at least $r!$ SDRs. (Do not use the Permanent Inequality.)
5.156 DO Use the preceding problem to show that
$\ln L(n) \gtrsim (1/2) n^2 \ln n$. (Note that this is half of
the true magnitude, see 5.202.)
Historic comment. For several decades, the best lower bound
known for $L(n)$ was 5.156. This was only improved using the
Permanent Inequality (5.202).
5.160 DEF Let $1\le k\le n$. A $k\times n$ Latin rectangle
is a $k\times n$ matrix $A=(a_{ij})$ such that $(\forall i,j)(a_{ij}\in[n])$
and no entry is repeated in any row and in any column. In particular,
each row is a permutation of $[n]$.
5.161 DO Let $L(n,k)$ denote the number of $k\times n$
Latin rectangles. Prove: $L(n,k) \le (n!)^k$.
5.162 HW (7 points, due Tuesday, May 12)
Prove: $\displaystyle{L(n,2) \sim \frac{(n!)^2}{\eee}}$.
You may use any result stated above. State what you use.
5.164 HW (9 points, due Tuesday, May 12)
Let $1\le k < n$. Prove: every Latin rectangle
can be extended to a Latin square (by adding rows).
Hint. You only need to add one row at
a time, i.e., given a $k\times n$ Latin rectangle where
$k < n$, add a row to obtain a $(k+1)\times n$ Latin rectangle.
Use König's 1916 theorem (Ex. 5.149) to prove this.
5.170 Bonus (8 points, due Tuesday, May 12)
Let $L(n)$ denote the number of $n\times n$ Latin squares.
Use Challenge problem 5.155 to prove that $\ln L(n) \gtrsim (1/2)\,n^2\ln n$.
Do not use the Permanent Inequality (below).
(For the $\gtrsim$ ("greater than or asymptotically equal")
notation, see the ASYMP handout.) [Update: Problem 5.155 was previously
numbered 5.150. Fixed May 7, 11:30pm] [This problem restates
DO exercise 1.156. Please read the historic comment after 5.156.]
5.180 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.
5.181 COMMENT (Computational intractability of the permanent)
While the determinant can be efficiently computed using
Gaussian 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 hard as to count the
solutions to any NP-puzzle, e.g., counting the 3-colorings of a graph
or 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.
5.182 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!$ .
5.183 DO Let $\calH$ be a hypergraph with $n$ vertices and $n$ edges.
Let $M$ be the incidence matrix of $\calH$; so $M$ is an $n\times n$
$(0,1)$-matrix. Prove: the number of SDRs of $\calH$ is $\per M$.
5.184 DO Prove that counting SDRs of hypergraphs is $\#P$-hard.
This should be an immediate consequence to (in fact, equivalent to)
Valiant's result (5.181) if we permit the hypergraph to have repeated
edges. The result remains valid under our convention that we do not
permit repeated edges; this causes only a slight technical difficulty,
which is the main subject of this exercise. Give a very simple reduction
of computing an $n\times n$ $(0,1)$-permanent to counting the SDRs
of a hypergraph with $2n$ vertices and $2n$ edges, no repeated edges
permitted.
5.188 DEF Let $A=(a_{ij})\in M_n(\rrr)$. We say that $A$ is a
stochastic matrix if every row of $A$ is a probability
distribution, i.e., $(\forall i,j)(a_{ij}\ge 0$ and
$(\forall i)(\sum_{j=1}^n =1)$ (every row sum is 1). We say that
$A$ is doubly stochastic if both $A$ and $A^T$ are stochastic.
In other words, $A$ is doubly stochastic if its entries are non-negative
and the sum of each row is 1 and the sum of each column is 1.
5.189 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.
5.190 DO Prove: convex combinations of doubly stochastic matrices
are doubly stochastic.
5.191 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.)
5.194 HW (9+6 points, due due Tuesday, May 12)
Let $A$ be a doubly stochastic matrix. (a) Prove: $\per(A)\le 1$.
(b) Prove: $\per(A)=1$ if and only if $A$ is a permutation matrix.
5.195 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}}$.
5.197 THE PERMANENT INEQUALITY (Egorychev, 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).
5.198 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 that $\per(A) > \eee^{-n}$ was obtained by Norwegian mathematician
Toger Bang in the 1970s. That weaker result will suffice for our applications.
An elementary proof of the Permanent Inequality can be found in the book
by Van Lint and Wilson (listed on the course home page).
5.200 HW (8 points, due Friday, May 8) 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.) [Updates: Typo "$(r\ge 0)$" corrected May 8, 0:45am.
Parenthetical sentence added May 8, 3:30am.]
5.202 Bonus (8 points, due Tuesday, May 12) Let $L(n)$
denote the number of $n\times n$ Latin squares.
Prove: $\ln L(n) \sim n^2\,\ln n$. Use
any of the results stated above.
TYPOS FIXED at a late date:
4.1 CLARIFICATION of TERMINOLOGY.
A family $\calF=\{A_1,\dots,A_m\}$ of sets is
uniform if all the $A_i$ have the same size. It is $k$-uniform
if $(\forall i)(|A_i|=k)$. So if $\calF$ is a $k$-uniform family
of subsets of the set $V$ then $\calF\subseteq \binom{V}{k}$.
Important examples of uniform families include Steiner Triple Systems
(they are 3-uniform) and finite projective planes: a projective plane
of order $n$ is $(n+1)$-uniform. $\binom{V}{k}$ is the maximal
$k$-uniform subfamily of $\calP(V)$.
4.2 STUDY the basic concepts of abstract algebra (groups,
fields, rings) and linear algebra over arbitrary fieldss.
Read a very quick summary in
LinComb,
Sections 2.1.1 ("Fundamental structures") and 2.1.3 ("Linear spaces").
4.3 STUDY the first five sections of Chapter 2.2 ("Affine subspaces,
linear equations, rank") of
LinComb.
Pay special attention of Section 2.2.5 ("Projective spaces").
4.10 FIELDS. In the following exercises, $\fff$ will be an arbitrary
field. If you are not comfortable with the abstract concept of a field,
think of $\fff$ as one of the following fields: $\ccc$, $\rrr$, $\qqq$
(the rational numbers), of $\fff_p$ (the integers modulo $p$ where $p$
is a prime number).
4.11 DEF. Let $\fff$ be a field, $a\in\fff$, and $n\in\zzz$.
We define $na\in\fff$ as the sum $a+\dots+a$ ($n$ times) of $n>0$;
as $-(-n)a$ if $n <0$, and as 0 if $n=0$.
4.12 DO Prove both distributive laws: Let $n,m\in\zzz$
and $a,b\in\fff$. Then $n(a+b)=na+nb$ and $(n+m)a=na+ma$.
4.13 DO Prove both associative laws: $(mn)a=m(na)$
and $n(ab)=(na)b$.
4.14 DO Prove: if for some $a\in\fff$, $a\neq 0$ we have
$na=0$ then $(\forall b\in\fff)(nb=0)$.
4.15 DEF The characteristic of the field $\fff$
is the smallest positive integer $k$ such that
$(\forall a\in\fff)(ka=0)$. If no such $k$ exists, we
say that the field has characteristic zero.
For example, $\ccc$, $\rrr$, $\qqq$ have characteristic zero,
and $\fff_p$ has characteristic $p$.
4.16 DO The characteristic of every field is either
zero or a prime number.
4.17 DO For every prime $p$ find an infinite field
of characteristic $p$. Hint: quotients of formal polynomials.
4.19 DEF. Let $\fff$ be a field. $\fff^{\times}$ denotes
the set $\fff\setminus\{0\}$, the multiplicative group
of $\fff$. We write $\fff^n$ denotes the space of
vectors $(a_1,\dots,a_n)$ where $a_i\in \fff$. Let $\fff^{n\times k}$
denote the set of $n\times k$ matrices over $\fff$ and let
$M_n(\fff)=\fff^{n\times n}$ be the set of $n\times n$ matrices.
We usually think of the elements of $\fff^n$ as column vectors,
so $\fff^n = \fff^{n\times 1}$, so, strictly speaking, it is not
$(a_1,\dots,a_n)$ but its transpose, $(a_1,\dots,a_n)^T$ that belongs
to $\fff^n$.
4.20 NOTATION $U\le \fff^n$ denotes that $U$ is a subspace
of $\fff^n$.
4.21 HW (6 points) Prove: If $U$ is a $k$-dimensional subspace
of $\fff_p^n$ then $|U|=p^k$.
4.24 DEF The standard dot product has the usual definition:
if $a,b\in \fff^n$ then $a\cdot b = a^Tb = \sum_{i=1}^n a_ib_i$
where $a=(a_1,\dots,a_n)^T$ and $b=(b_1,\dots,b_n)^T$.
4.25 DEF We say that $a,b\in\fff^n$ are orthogonal or
"perpendicular" if $a\cdot b=0$. We denote this circumstance
by $a\perp b$. For $a\in \fff^n$ and $S\subseteq \fff^n$ we
write $a\perp S$ if $(\forall s\in S)(a\perp s)$. For
$S, T\subseteq \fff^n$ we write $S\perp T$ if
$(\forall s\in S)$(\forall t\in T)(s\perp t)$.
4.26 DEF
For $v\in\fff^n$ we write $v^{\perp}=\{w\in\fff^n\mid w\perp v\}$.
For $S\subseteq\fff^n$ we write $S^{\perp} = \{w\in\fff^n\mid w\perp S\}$.
4.27 DO $v^{\perp} = \{v\}^{\perp}$
4.25 DO $\displaystyle{S^{\perp}=\bigcap_{s\in S} s^{\perp}}$.
4.28 DO For $S\subseteq \fff^n$, the set $S^{\perp}$ is a
subspace of $\fff^n$.
4.29 DO Show: (a) $\emptyset^{\perp}=0^{\perp}=\fff^n$.
(b) $(\fff^n)^{\perp} = \{0\}$.
4.30 DO If $S\subseteq \fff^n$ then $S\subseteq S^{\perp\perp}$.
4.32 HW (12 points) Let $U\le \fff^n$ (subspace). Prove:
$ \dim U + \dim U^{\perp} = n$ .
4.33 DO (Corollary) If $U\le \fff^n$ then $U^{\perp\perp} = U$.
4.35 DEF The vector $u\in\fff^n$ is isotropic
if $u\neq 0$ and $u\perp u$. So if $u=(u_1,\dots,u_n)\in\fff^n$
then $u$ is isotropic if and only if not all the $u_i$ are zero
and $\sum_{i=1}^n u_i^2=0$.
4.36 DO Find an isotropic vector in $\fff^2$ where
$\fff$ is (a) $\ccc$ (b) $\fff_2$ (c) $\fff_5$.
4.37 DO Show that there is no isotroopic vector in (a) $\rrr^n$
(b) $\fff_3^2$ (c) $\fff_7^2$.
4.38 PROJECT (DO) For what values of the prime $p$ does there exist
an isotropic vector in $\fff_p^2$ ? (a) Show that the answer is
yes if and only if $-1$ is a quadratic residue mod $p$, i.e.,
there exists an integer $x$ such that $x^2\equiv -1 \pmod p$.
(b) Find the very simple pattern for these primes
by experimenting with small values of $p$.
(c) Prove that the pattern holds in general. This involves two parts:
(c1) showing that for primes
that satisfy the pattern, an isotropic vector exists; and
(c2) showing that for primes that do not satisfy the pattern,
no isotropic vector exists. (c2) is easier.
4.39 DO Prove: $(\forall \text{ primes } p)(\exists$
isotropic vector in $\fff_p^3)$.
You may use the fact that the product of two quadratic non-residues is
a quadratic residue mod $p$. (Look up what this means.)
4.40 DEF A subspace $U\le \fff^n$ is totally isotropic
if $U\perp U$, i.e., $(\forall u,v\in U)(u\perp v)$.
In other words (DO),
$U$ is totally isotropic if and only if $U\le U^{\perp}$.
4.41 DO (a) Observe that every non-zero vector in a totally isotropic
subspace is isotropic. (b) Show that the converse does not hold:
there exists a field $\fff$ and a subspace $U\le \fff^n$ for some $n$ such
that every vector in $U$ is isotropic but the subspace is not
totally isotropic. (c) Show that if $\fff$ does not have characteristic 2
(i.e., $1+1\neq 0$) and all non-zero vectors in a subspace $U\le\fff^n$
are isotropic then $U$ is totally isotropic.
4.43 Bonus (6 points) Prove: If a field $\fff$ has
characteristic $p > 0$ and $a,b\in\fff$ then
$(a+b)^{\,p} = a^{\,p} + b^{\,p}$.
(You may use the exercises 4.10-4.16 above.)
4.45 HW (6 points) Prove: If $U\le \fff^n$ is totally
isotropic then $\dim U \le \lfloor n/2 \rfloor$.
You may use any exercise stated above. Indicate what you are using.
4.46 HW (12 points) For every $n$, find a totally
isotropic subspace of dimension $\lfloor n/2\rfloor$
in $\fff^n$ for the following fields $\fff$:
$\ccc$, $\fff_5$, $\fff_2$.
4.47 Bonus (18 points) Show that every maximal totally
isotropic subspace in $\fff_2^n$ is maximum. In other words, you have
to show that if $U\le \fff_2^n$ is a totally isotropic subspace
of dimension less than $\lfloor n/2\rfloor$ then $U$ is properly
contained in a larger totally isotropic subspace.
4.50 HW (20 points) Let $A_1,\dots,A_m\subseteq [n]$ be a family of
Eventown clubs, i.e., $(\forall i,j)(|A_i\cap A_j|\text{ is even})$.
(Note that this condition in particular implies that each club has
even size.) Prove: $m\le 2^{\lfloor n/2\rfloor}$. For the proof,
you may use all results stated above as exercises, including bonus problems.
Indicate what you are using.
4.51 DO Prove: Every maximal Eventown club system is maximum.
In other words, if we have a family of fewer than
$2^{\lfloor n/2 \rfloor}$ Evetown clubs then another club can be
added such that the Eventown rules continue to be observed.
Use an exercise stated above.
4.52 Bonus (18 points, due Thursday, April 30) Prove, for all
sufficiently large $n$, that there exists a maximal
family of Eventown clubs in $[n]$ that is not isomorphic to the
"married couples" club system (where couples join clubs together).
(You may use all exercises stated above.) State how large is
"sufficienty large" in your solution. Define "isomorphic."
4.60 HW (8 points) Find all families that are simultaneously
$3$-uniform and $8$-uniform. [Point value raised 4-27 1am]
4.65 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. So a hypergraph
is a family of sets with an emphasis on the universe $V$.
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 $n\times m$ $(0,1)$
matrix $M=(m_{ij})$ where $m_{ij}=1$ if $v_i\in E_j$ and $m_{ij}=0$
otherwise.
4.66 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$.
4.67 DEF 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 id every vertex has degree $d$.
4.69 DO What are the entries (a) of the $n\times n$ matrix $MM^T$
(b) of the $m\times m$ matrix $M^TM$, where $M$ is the
incidence matrix of the hypergraph $\calH$ ?
4.71 DEF The rank of a hypergraph is the maximum size
of its edges.
4.72 DEF We say the $\calH$ is a $k$-uniform hypergraph
if $\calE$ is a $k$-uniform family, i.e., $(\forall E\in\calE)(|E|=k)$.
In other words, $\calH$ is $k$-uniform if $\calE\subseteq \binom{V}{k})$.
--- A hypergraph is uniform if it is $k$-uniform for some $k$.
4.73 HW (6 points) Let $\calH$ be a $d$-regular
$r$-uniform hypergraph. Prove: $nd = mr$. Use the incidence matrix.
4.74 DEF Recall that a Steiner Triple Systems
is a 3-uniform hypergraph where every pair of vertices belongs
to exactly one edge.
4.75 HW (6+4 points)
Let $\calS = (V,\calE)$ be a Steiner Triple System (STS).
(a) Prove that $\calS$ is regular; find its degree in terms of $n$.
(b) Express the number of edges in terms of the number
of vertices.
4.76 DO Observe that a finite projective plane of order $k$
is a $(k+1)$-uniform hypergraph (with some additional properties).
4.77 DEF A graph is a 2-uniform hypergraph. Its vertices
are often called "nodes" and its edges "links."
4.78 DEF The complete $r$-uniform hypergraph on $n$ vertices
is $\displaystyle{K_n^{(r)} = \left([n],\binom{[n]}{r}\right)}$.
It has $m=\binom{n}{r}$ edges.
4.79 DEF A hypergraph is empty if it has no edges:
$\calH = (V,\emptyset)$.
Next, we define four important parameters of the hypergraph
$\calH = (V,\calE)$.
4.80 DEF A set $B\subseteq V$ is independent
if it does not contain any edges, i.e.,
$(\forall E\in\calE)(E\not\subseteq B)$. [Typo fixed
in this formula Apr 27, 3:30pm]
4.81 DEF Let $C$ be a set; we refer to the elements of $C$
as "colors." A legal coloring of $\calH$ with codomain $C$
is a function $f:V\to C$ that does not
make any edge monochromatic, i.e., every edge receives
at least two colors: $(\forall E\in\calE)(|f(E)|\ge 2)$.
We say that $\calH$ is $k$-colorable if $k$
colors suffice for a legal coloring.
The minimum number of colors needed for a legal
coloring is the chromatic number of $\calH$,
denoted $\chi(\calH)$ (using the Greek letter "chi"; the "ch" is
pronounced as in "technology"]; in LaTeX: $\tt \backslash chi$).
So $\calH$ is $k$-colorable if and only if $k\ge \chi(\calH)$.
We write $\chi(\calH)=\infty$ if no legal coloring exists.
4.82 DO A legal coloring exists if and only if every edge
has size $\ge 2$. In this case, $\chi(\calH) \le n$.
4.83 DEF A cover of $\calH$ is a set $D\subseteq V$
such that $(\forall E\in \calE)(D\cap E \neq \emptyset)$.
A cover is also called a transversal, or a hitting set
(it hits every edge). This last term is especially popular in the
theoretical computer science literature. The covering number
is the minimum size of a cover, denoted $\tau(\calH)$ (using
the Greek letter "tau," in LaTeX: $\tt \backslash tau$).
If the empty set is an edge, $\tau$ is not defined (you cannot hit
the empty set.) So when talking about $\tau(\calH), we assume
that the empty set is not an edge.
4.84 DEF A matching is a set of disjoint edges.
The matching number is the maximum number of disjoint edges,
denoted $\nu(\calH)$ (using the Greek letter "nu," in LaTeX:
$\tt{\backslash nu}$).
4.90 DO Prove: $\alpha(\calH)+\tau(\calH) = n$.
4.91 DO Prove: $\alpha(\calH)\cdot \chi(\calH) \ge n$.
4.92 DEF Let $\SET_d$ denote the hypergraph with vertex set
$V=\fff_3^d$ where the edges are the affine lines. Note that
the vertices of $\SET_4$ correspond to the cards in the card game "SET"
and the edges are the "SET" configurations (triples of cards the players
need to find). --- A set of cards without a "SET" is called a capset;
these are exactly the independent sets in $\SET_4$. The largest such
set has size $\alpha(\SET_4)=20$. The generalization of this question
to $\SET_d$ has turned out to be an exciting mathematical problem which
we discuss next. An independent set in $\SET_d$ is called a $d$-cap.
4.93 DEF A sequence $a_1,a_2,\dots$ of positive numbers is
supermultiplicative if $(\forall k,\ell \ge 1)(a_{k+\ell}
\ge a_k\cdot a_{\ell})$.
4.94 DO (a) Let $\alpha_d=\alpha(\SET_d)$.
Prove: the sequence $\alpha_d$ is supermultiplicative.
4.95 DO Fekete's Lemma Prove: If the sequence
$a_n > 0$ is supermultiplicative then the limit $\lim_{n\to\infty} a_n^{1/n}$
exists and is equal to $\sup_{n\in \nnn} a_n^{1/n}$. (Note that this
limit can be infinite.)
4.96 DO Let $L=\lim_{d\to\infty} \alpha_d^{1/d}$.
We know that $2\le L \le 3$. Prove: $L > 2$. Use the fact that
$\alpha_4 = 20$. To obtain stronger lower bounds, use the following
data: $\alpha_5=45$ and $\alpha_6=112$.
4.97 STORY. It is a non-trivial result that
$\alpha_d = o(3^d)$. Roy Meshulam proved in 1995 that
$\alpha_d \le (2/d)\cdot 3^d$ using an elegant argument
in discrete Fourier analysis over the group $\zzz_3^d$.
However, $\lim_{d\to\infty} ((2/d)3^d)^{1/d}=3$, so this
result did not decide the question whether $L < 3$.
This inequality ($L < 3$) was confirmed 22 years later (2017)
in a pair of papers, the first by Péter Pál Pach,
Ernie Croot, and Vsevolod Lev, the second by Jordan Ellenberg
and Dion Gijswijt, using the linear algebra method
applied to spaces of polynomials.
4.100 Bonus (12 points, due Thursday, April 30)
Find infinitely many STSs $\calS$
such that $\alpha(\calS) > n/2$. (Hint. Projective
geometry.)
4.101 HW (15 points)
Let $\calH=(V,\calE)$ be a non-empty 3-uniform regular hypergraph.
Prove: $\alpha(\calH)\le 2n/3$.
4.102 Bonus (18 points, due Thursday, April 30)
We say that $\calH$ is an intersecting hypergraph
$\nu(\calH)= 1$, i.e., every pair of edges intersects.
Prove: If $\calH$ is a non-empty, regular, $r$-uniform
intersecting hypergraph with $n\ge 2$ vertices then
$r > \sqrt{n}$. [Condition $n\ge 2$ added
April 27 5:20pm]
4.105 HW (15 points, due Thursday, April 30)
Prove: If $\calH$ is an $r$-uniform
hypergraph, $r\ge 2$, with $m\le 2^{r-1}$ edges, then
$\calH$ is 2-colorable. (Hint: Show that a random 2-coloring
has a positive chance of being legal. You will earn
partial credit by solving the case when $m < 2^{r-1}$.)
4.106 PROBLEM (Erdös) Let $m(r)$ denote the minimum
number of edges of an $r$-uniform hypergraph that is not 2-colorable.
The preceding exercise says that $m(r) > 2^{r-1}$.
4.107 CH (Erdös) $m(r) = O(r^2 2^r)$.
(Hint. The probabilistic method.)
4.108 DO $\log_2 m(r) \sim r$. (Use 4.107 and 4.105.)
4.110 DO Let $\cal$ be a non-empty regular $r$-uniform hypergraph.
(a) Prove: $\tau(\calH) \ge n/r$. (b) An exercise
above is an immediate consequence of this. Which one?
4.111 DO Prove: $(\forall x\neq 0)(1+x < \eee^x)$
4.112 Bonus (18 points, due Thursday, April 30)
Let $\calH$ be a [non-empty] regular $r$-uniform hypergraph
with $m\ge 2$ edges.
Prove: $\tau(\calH) \le \left\lceil (n/r)\ln m\right\rceil$.
Do not use Lovász's theorem on the greedy cover
algorithm.
Hint: random choice. [Update: The condition $m\ge 2$
was added April 30, 5:15am. This supersedes the non-emptiness condition,
so I put that condition in brackets. - Regularity is not required
in this problem.]
4.120 DO Prove:
For all hypergraphs, $\nu(\calH) \le \tau(\calH)$.
4.121 HW (8 points, due Thursday, April 30)
Prove:
For all $r$-uniform hypergraphs, $r\cdot\nu(\calH) \ge \tau(\calH)$.
4.130 Bonus (16 points, due Thursday, April 30)
Prove: $\displaystyle{\chi(K_n^{(r)}) =
\left\lceil\frac{n}{r-1} \right\rceil}$.
4.133 HW (12+10 points, due Tuesday, May 5
(a) Show that there exists a STS of chromatic number $\ge 100$.
(b) Prove that there exists a positive constant $c$ such that
for every $k$ there is a STS of chromatic number $\ge k$
with $n \le k^c$ vertices. You may use any of the results
stated above. For each statement, use the weakest among the
relevant results. Indicate what result(s) you are using.
4.136 Bonus (15 points, due Tuesday, May 5)
Let $\calH$ be a hypergraph such that every edge has at least
two vertices (so $\calH$ has a legal coloring).
For a positive integer $x$, let $f_{\calH}(x)$ denote the
number of legal colorings of $\calH$ with codomain $[x]$.
Prove that the function $f_{\calH}$ is a polynomial.
It is called the chromatic polynomial of $\calH$.
What are the degree and the leading term of this polynomial?
4.140 HW (7+7 points, due Tuesday, May 5)
(a) Find a linear program (LP) such that the primal is feasible and
the dual is not.
4.145 HW (14+4 points, due Tuesday, May 5)
(a) Let $k\ge 1$. Let $\calH=(V,\calE)$ be a hypergraph such that
$(\forall E\neq F \in \calE)(|E\cap F| < k)$. Prove:
$$ m\le \binom{n}{k}+ \binom{n}{k-1}+\dots+\binom{n}{0}.$$
(b) Prove that this bound is tight for every pair $(n,k)$
of positive integers.
Hint. No linear algebra needed for this problem.
Solve it from first principles.
3.1 STUDY DMmini Chap 1 (Quantifier notation, with some number theory)
3.2 STUDY ASY (Asymptotic equality and inequality).
3.3 STUDY DMmini Chap 2 (Asymptotic notation), Sections 2.1, 2.3, 2.4, 2.7.
(Skip Sec. 2.2 because it is superseded by ASY.)
LaTeX: $\Theta$ is the capital Greek letter Theta, in LaTeX:
$\tt \backslash Theta$.
3.4 STUDY DMmini Chap 3 (Convex functions and Jensen's Inequality)
3.5 STUDY PROB Section 7.8 (Variance, Covariance, Chebyshev's Inequality)
and Sections 7.9 and 7.10 (Independence of random variables)
3.6 STUDY the proof of Sperner's Theorem and the BLYM Inequality
from the slides posted (click "Slides" on the banner of the
course home page).
3.7 STUDY DMadvanced Chap 7 (Finite projective planes)
3.10 DEF Let $A\subseteq [n]$. The incidence vector of $A$
is the $(0,1)$-vector $a=(u_1,\dots,u_n)$ where $u_i=1$ if $i\in A$
and $u_i=0$ if $i\notin A$.
3.11 DO Let $A,B\subseteq [n]$. Let $a$ and $b$ denote their
respective incidence vectors. The dot product of the incidence vectors is
$a\cdot b = |A\cap B|$.
3.12 DO Let $B=(b_{ij})\in M_n(\zzz)$ be an $n\times n$ integral
matrix (a matrix with integer entries). Suppose the diagonal
entries $b_{ii}$ are odd and the off-diagonal entries $b_{ij}$
$(i\neq j)$ are even. Prove: $B$ is non-singular.
3.13 REVIEW: Oddtown Theorem (Elvyn Berlekamp, 1969).
Let $A_1,\dots, A_m \subseteq [n]$. Assume this set system satisfies
the "Oddtown rules":
3.18 HW (15 points) Let $0\le \ell < k \le n$. Let
$A_1,\dots,A_m \in \binom{[n]}{k}$ be a $k$-uniform family of
subsets of $[n]$ such that $(\forall i\neq j)(|A_i\cap A_j|=\ell)$.
Prove: $m \le n$. Hint. Mimic the proof of the
Oddtown Theorem. Use a familar determinant.
3.20 HW (2+2+6 points) (a) State Sperner's Theorem, including
the definition of a Sperner family, including the definition of
what it means for a pair of sets to be "comparable."
(b) State the BLYM
(Bollobás-Lubell-Yamamoto-Meshalkin) Inequality.
For (a) and (b), use the slides (NOT the video) of the
April 14 lecture. (Click "Slides" on the navigation bar.)
(c) Prove Sperner's Theorem using the BLYM Inequality.
The essential content of your proof should be just one line.
(Do not prove the BLYM inequality.)
3.21 HW (6 points) Find $n+1$ Sperner families in
$\calP([n])$ for which equality holds in the BLYM Inequality.
3.22 QUESTION (CH) Are there any non-uniform Sperner families
for which equality holds in the BLYM Inequality? (I don't know
the answer.)
3.23 HW (2+6points) Let $0\le k\le n$.
Let $A\subseteq [n]$ be a given
$k$-set. Let $\sigma$ be a random linear ordering of the set $[n]$,
chosen from the uniform distribution. (a) What is the size of
the sample space for this experiment? (b) Prove:
$$ P(A \text{ is a prefix of }\sigma) = \frac{1}{\binom{n}{k}} $$
3.25 DEF: A sequence $a_0,a_1,\dots,a_n$ of real numbers
is unimodal
if $(\exists k)(a_0\le a_1\le \dots \le a_k \ge a_{k+1}\ge \dots \ge a_n)$.
3.26 DEF: A sequence $a_0,a_1,\dots,a_n$ of positive
numbers is log-concave if
$(\forall i\in [n-1])(a_{i-1}a_{i+1}\le a_i^2)$.
3.27 HW (8 points)
Prove: If a sequence is log-concave then it is unimodal.
3.28 DO (a) Prove that the sequence $\binom{n}{0}$, $\binom{n}{1}$,
$\dots$, $\binom{n}{n}$ (the $n$-th row of the Pascal triangle)
is unimodal. (b) Prove that this sequence is log-concave.
3.29 DO (Newton) Let $b_1,\dots,b_n > 0$. Consider the
polynomial $f(t)=\prod_{i=1}^n (t+b_i)=\sum_{j=0}^n a_j t^{\,j}$.
(So all roots of $f$ are negative real numbers.) (a) Prove:
the sequence $a_0,\dots,a_n$ of coefficients is log-concave.
(b) Prove the following stronger property: the sequence
$\displaystyle{\frac{a_j}{\binom{n}{j}}}$ is log-concave.
Prove that this property is indeed stronger than the log-concavity
of the $a_j$ sequence.
3.35 HW (10 points) Asymptotically evaluate the quantity
$\displaystyle{r_n:=\binom{n}{\lfloor n/2\rfloor}}$. Your
answer should be an asymptotic equality of the form
$r_n \sim a\cdot n^b\cdot c^n$. Determine the constants
$a,b,c$. Use Stirling's formula. Show your work.
Solve the case of even $n$ first, then reduce the case of odd
$n$ to the case of even $n$ in one line.
3.36 HW (9 points) Let $a_n, b_n$ be sequences of positive real
numbers. Assume $a_n\to\infty$. Assume further that
$a_n = \Theta(b_n)$. Prove: $\ln a_n \sim \ln b_n$.
3.37 HW (3+7 points) (a) Prove: $\ln x = o(x)$, i.e.,
$\lim_{x\to\infty} \frac{\ln x}{x}=0$. Use L'Hôpital's rule.
(b) (Bootstrapping) Prove:
$\ln x = o(x^{1/100})$. Do not use calculus. Use part (a)
and a substitution of variables. Your proof should be very short.
(The term "bootstrapping" refers to a procedure when we use a result
to obtain a much stronger result at almost no extra cost.)
3.38 HW (6 points, due Thursday, April 23) [Added 4-19 2am]
Prove: For all $n\ge 1$ we have $n! > (n/\eee)^n$.
3.40 HW (9+4 points) Let $0 \le k, \ell \le n$.
Let $A$ be a random $k$-subset of
$[n]$ and $B$ a random $\ell$-subset of $[n]$, chosen uniformly and
independently from $\binom{[n]}{k}$ and from $\binom{[n]}{\ell}$,
respectively. (a) Determine $E(|A\cap B|)$.
(b) What is the size of the sample space for this
experiment?
3.42 HW (8 points)
Construct a probability space and two random variables that are
uncorrelated but not independent. Make your sample space as small
as possible. You do not need to prove minimality of your sample space.
3.45 Bonus ("Order statistic") (Due Thursday, April 23) (20 points)
Let $1\le k\le n$. Let $A$ be a random $k$-subset of $[n]$,
chosen from the uniform distribution over $\binom{[n]}{k}$.
Let $A=\{a_1,\dots,a_k\}$ where $a_1 < a_2 < \cdots < a_k$. Note
that the $a_i$ are random variables. For $1\le i\le k$, prove:
$$ E(a_i) = \frac{i(n+1)}{k+1} $$
Try to give a simple proof. Elegance counts.
3.50 Bonus (Due Thursday, April 23) (2+18+4 points)
(Littewood-Offord Problem, solution by Paul Erdös)
Let $a_1,\dots,a_n,b$ be real numbers
and assume $\prod_{i=1}^n a_i \neq 0$. Pick a random subset
$I\subseteq [n]$ from the uniform distribution over $\calP([n])$.
3.53 Bonus (due Tuesday, April 28) (18B points)
PROB 7.8.20 (a) (Strongly negatively correlated events)
3.55 DEF (Cycle structure of permutations):
A permutation of a set $\Omega$
is a bijection $\pi:\Omega\to \Omega$. A fixed point of
$\pi$ is an element $x\in\Omega$ such that $\pi(x)=x$. For
$x\in\Omega$, the $\pi$-cycle of $x$ is the cyclic sequence
$(x, \pi(x), \pi^2(x):=\pi(\pi(x)), \dots)$. By a cyclic sequence
we mean an equivalence class of sequences under cyclic shifts,
so for instance the cyclic sequences $(a,b,c,d)$ and $(b,c,d,a)$
are considered equal. The length of this cycle is the smallest
$k\ge 1$ such that $\pi^k(x)=x$.
This value is called the period of $x$ under $\pi$;
we shall denote it by $p(x,\pi)$.
So for instance $x$ is a fixed point if and only if $p(x,\pi)=1$.
The support of a cyclic sequence
$\sigma=(a_0,\dots,a_{k-1})$ is the set $\supp(\sigma)=\{a_0,\dots,a_{k-1}\}$.
3.56 HW (Due Thursday, April 23) (2+9+9 points)
Let $1\le k\le n$. Let $\pi$ be a random permutation
of $[n]$, chosen from the uniform distribution. (a) What is the
size of the sample space for this experiment?
(b) Prove: $P(p(1,\pi)=k)=1/n$. (The period of item 1
is uniformly distributed in $[n]$.)
(c) Prove: $E(c(\pi))\sim \ln n$ (the expected number of
cycles of a random permutation of an $n$-set is asymptotically
equal to the natural logarithm of $n$).
3.57 Bonus (Due Thursday, April 23) (18 points)
We say that a permutation $\pi :[n]\to [n]$
is fixed-point-free if it has no fixed points.
Let $\FFE_n$ denote the number of fixed-point-free even permutations
and $\FFO_n$ the number of fixed-point-free odd permutations.
For every $n\ge 1$, decide whether $\FFE_n > \FFO_n$ or
$\FFE_n = \FFO_n$ or $\FFE_n < \FFO_n$. (The answer depends on $n$.)
(Hint. A familiar determinant.)
The following problems have been added on April 19 at 3am.
3.60 HW (2+10+10 points, due Thursday, April 23)
Recall that $\fff_2$, the field of order two, has two elements,
$0$ and $1$, and arithmetic operations are performed modulo 2,
so $1+1=0$. The set of $n\times n$ matrices over $\fff_2$
is denoted $M_n(\fff_2)$.
3.63 DEF (Maximal versus maximum) We say that a set system
is maximal with respect to certain constraints if no set can
be added to it and still satisfy the constraints. A set system is
maximum with respect to certain constraints if it is the
largest system satisfying the constraints. By definition, every maximum
system is maximal, but only seldom is every maximal system maximum.
3.64 EXAMPLE Let us consider the Sperner families
of subsets of $\calP([n])$. DO: Show that for every $k$
in the range $0\le k \le n$, the $k$-uniform family $\binom{[n]}{k}$
is a maximal Sperner family. (But only the middle one(s)
is (are) maximum.) In particular, taking $k=0$ we see
that there is a maximal Sperner family that has only one member.
3.65 HW (6 points, due Thursday, April 23)
We have seen that a maximum family of Oddtown clubs has
$n$ clubs. For every $n$, find a maximal
family of Oddtown clubs that consists of $\le 2$ clubs.
3.66 CH Every maximal family of Eventown clubs is maximum.
3.68 HW (4 points, due Thursday, April 23)
What is the maximum number of SET cards that do not
contain a "SET"? Look it up, report the number and
where you found it. No proof is necessary. DO: verify
that the proposed maximum configuration indeed does not
contain a SET. CH Can you think of an efficient method
to verify that it is maximum? (I don't know such a method.)
3.70 DO (Finite projective planes) Solve DMmaxi 7.1.6--7.1.11.
3.72 DO Prove the Fundamental Theorem of Projective Geometry
(DMmaxi 7.2.3).
3.75 HW (Breakout room feedback, due April 23, 3 points)
[Added April 21, 5pm]
Please comment on your Breakout room experience
during the Tuesday, April 21, class.
Please include the following:
PROVE YOUR ANSWERS
unless it is expressly stated that no proof is required.
IMPORTANT.
The Canvas site has contracted versions
of the problems assigned. Some of those are relatively
informative, others are less so, but none of them contains
full information about the problem. The contractions serve only
the easy identification of each problem. The only authentic
source of the problems assigned is this website (and the online
sources referenced here).
2.0 NOTATION: If $k\ge 0$ is an integer then $[k]=\{1,\dots,k\}$.
Examples: $[0]=\emptyset$, $[1]=\{1\}$, $[2]=\{1,2\}$,
$[5]=\{1,2,3,4,5\}$.
2.1 READING: LinAlg, Chapters 1-7 except sections 5.4 and 5.5.
Pay particular attention to Theorem 1.3.40 ("First Miracle of
Linear Algebra"), Section 3.2 (elementary operations), and
Section 6 (determinants). "Reading" includes solving most
exercises.
2.2 READING: PROB, Sections 7.1, 7.2, 7.3, 7.4 (independence of events,
conditional probability),
7.7 (random variables, linearity of expectation, indicator variables).
"Reading" includes solving most exercises.
Solve especially the problems listed in Exercise 2.43 below.
2.3 DO [Added April 12, 6:20pm]
Use the definition of the determinant ($n!$-term expansion, see LIN Sec 6.2,
Eq.(6.20)) to prove the following.
You can use these properties of the determinant
without proof in the HW problems below.
(a) If $A'$ is the transpose of the
$n\times n$ matrix $A$ then $\det(A')=\det(A)$.
(b) Elementary column operations $(i,j,\lambda)$ do not change the value
of the determinant. (See LIN, Def 3.2.1.) (c) Swapping two columns
changes the sign of the determinant, i.e., if the matrix $A'$ is obtained
from $A$ by swapping two columns then $\det(A')=-\det(A)$.
(d) Use (a) and (b) to infer that elemetary row operations
do not change the value of the determinant. (e) Use (a) and (c)
to prove that swapping two rows does not change the value of the
determinant. (f) If the matrix $A'$ is obtained from $A$ by multiplying
one column of $A$ by $c\in\rrr$ then $\det(A')=c\cdot\det(A)$.
(g) Prove that the determinant is a multilinear function
of its columns (LIN, Prop. 6.2.12). (The preceding item, (f),
is a special case.) (h) Prove the cofactor expansion of
the determinant.
2.4 DO [Added April 12, 7:40pm] Prove that the determinant of a
triangular matrix is the product of the diagonal.
You can use this without proof in the HW problems below.
2.5 HW (5 points) What happens to the value of the determinant
if we cyclically permute four columns? (This means that for some distinct
values $i_0,i_1,i_2,i_3$, column $i_t$ of the matrix $A$ becomes column
$i_{t+1}$ of the modified matrix $B$, where arithmetic on subscripts is
performed modulo 4, i.e., $3+1=0$. All other columns of $A$ are inherited
without change by $B$.) Reason your answer, but see "2.3 DO" exercise.
2.6 HW (9+4 points) We write $M_n(\rrr)$ to denote the set of
$n\times n$ real matrices. Let $a,b\in\rrr$ and $n\ge 1$. Let
$R_n(a,b)=(r_{ij})\in M_n(\rrr)$ denote the $n\times n$ matrix
with $r_{ii}=a$ for all $1\le i\le n$ and and $r_{ij}=b$ for all
$1\le i,j\le n$ where $i\neq j$. So each diagonal entry of the
matrix is $a$ and each off-diagonal entry is $b$:
$$R_n(a,b)=\begin{pmatrix}
a & b & b & \cdots & b \\
b & a & b & \cdots & b \\
b & b & a & \cdots & b \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
b & b & b & \cdots & a \\
\end{pmatrix}$$
(a) Determine the value of $\det(R_n(a,b))$. Your answer should be
a simple expression in terms of $n,a,b$.
2.7 HW (2+6+(3+2)+8B points)
Let $x_1,\dots,x_n\in\rrr$. The Vandermonde matrix
$V_n(x_1,\dots,x_n)=(v_{ij})\in M_n(\rrr)$ is defined
by $v_{ij}=x_j^{i-1}$, so the matrix is
$$V_n(x_1,\dots,x_n)=\begin{pmatrix}
1 & 1 & 1 & \cdots & 1 \\
x_1 & x_2 & x_3 & \cdots & x_n \\
x_1^2 & x_2^2 & x_3^2 & \cdots & x_n^2 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
x_1^{n-1} & x_2^{n-1} & x_3^{n-1} & \cdots & x_n^{n-1} \\
\end{pmatrix}$$
We say that $(x_1,\dots,x_n)$ is the list of generators of this matrix.
The determinant of this matrix is called the
Vandermonde determinant.
(a) Prove: If two of the generators are equal (i.e.,
$(\exists i\neq j)(x_i=x_j)$), then the Vandermonde
matrix is singular, i.e., the Vandermonde determinat is zero.
Do not use part (c) of this problem.
(d) (Bonus, due Thursday, April 16) Prove the general result
(evaluation of the Vandermonde determinant) stated in item (c).
If you use elementary operations, describe each step you make;
use the notation of LinAlg Chap. 3.2 to describe each step.
Alternatively, if you use the theory of multivariate polynomials,
state the results you are using.
2.8 HW (2 points, due Tuesday, April 21)
[Note that this exercise has been deferred by a week]
[Deferral announced 4-13 5pm]
Describe in one or two paragraphs your favorite activity these days,
other than solving the Combinatorics assignments. Add your
location info for context.
2.10 DEF Let $a=(a_1,\dots,a_n)$ and $b=(b_1,\dots,b_n)$
be vectors in $\rrr^n$. Their standard dot product
is defined as $a\cdot b = \sum_{i=1}^n a_ib_i$. The
euclidean norm of $a$ is defined as
$\|a\|=\sqrt{a\cdot a} = \sqrt{\sum_{i=1}^n a_i^2}$.
2.11 DO Prove: for $a\in\rrr^n$ we have $\|a\|=0$ if and
only if $a=0$. Note that the two zeros in this statement are
different: $\|a\|$ is a real number, while $a$ is a vector.
The meaning of the symbol "0" should always be clear from the
context.
2.12 DO Prove: $a\cdot (b+c)=a\cdot b+a\cdot c$.
2.13 DO (Cauchy--Schwarz)
$|a\cdot b|\le \|a\|\cdot \|b\|$.
2.14 DO (Triangle inequality)
$\|a+b\|\le \|a\|+\|b\|$.
Show that this result is equivalent to Cauchy--Schwarz.
2.15 DEF The vectors $a,b\in\rrr^n$ are orthogonal
if $a\cdot b=0$. We say that the vectors $v_1,\dots,v_k\in\rrr^n$
are orthogonal if they are pairwise orthogonal, i.e.,
$(\forall i, j\in [k])(i\neq j \implies v_i\cdot v_j = 0)$.
(Recall notation 2.0 above.)
2.16 DO Prove: If the non-zero vectors $v_1,\dots,v_k\in\rrr^n$
are orthogonal then they are linearly independent.
2.20 HW (7+7B points) Let $v_1,\dots,v_k\in\rrr^n$. The
Gram matrix of this list of vectors is the $k\times k$
matrix $G(v_1,\dots,v_k)=(g_{ij})$ where $g_{ij}=v_i\cdot v_j$
is the standard dot product of the vectors $v_i$ and $v_j$.
2.21 HW (8 points) Let $v_1,\dots,v_m\in\rrr^n$ be vectors
that are pairwise at unit distance, i.e.,
$(\forall i,j\in[m])(i\neq j \implies \|v_i-v_j\|=1)$. (Recall
notation 2.0 above.) We stated in class that in this case,
$m\le n+1$. The first step toward proving this is the following:
Find the Gram matrix of the vectors $w_1,\dots,w_{m-1}$
where $w_i=v_i-v_m$. (You need to determine each entry
of the $(m-1)\times (m-1)$ matrix $G(w_1,\dots,w_{m-1})$.)
The matrix will take a very simple and familiar form.
Prove your answer.
2.22 HW (6 points, due Thursday, April 16)
Let $v_1,\dots,v_m\in\rrr^n$ be vectors
that are pairwise at unit distance. Prove: $m\le n+1$.
2.30 DEF Let $(\Omega,P)$ be a finite probability space.
We say that an event $A\subseteq \Omega$ is trivial
if $P(A)=0$ or $P(A)=1$.
2.31 HW (5 points) PROB 7.3.13 (about independence of $A\cap B$
and $A\cup B$).
2.32 HW (5 points) PROB 7.3.14 (about independence of $A$ and $A$).
2.34 DO PROB 7.4.16 and 7.4.17 (independence of complements).
2.35 HW (8 points) Let $(\Omega, P)$ be a finite probability space.
Prove: If there exist two nontrivial independent events in this space
then $|\Omega|\ge 4$. You may use Problem 2.34. If you submit a correct
solution to 2.36 then you don't need to describe your solution
to 2.35 in detail, just submit a 1-line statement that refers to
your solution to 2.36. (This statement seems necessary so we can
properly credit you on Canvas.)
2.36 HW (Bonus, 8 points) Let $(\Omega, P)$ be a finite
probability space. Prove: If there exist $k$ nontrivial independent
events in this space then $|\Omega|\ge 2^k$. You may use 2.34.
2.37 HW (3+8+3 points, due Tuesday, April 21)
[Note that this exercise has been deferred by a week]
[Deferral announced 4-13 5pm]
(a) Prove: If three events are pairwise but not fully independent
then none of them can be trivial.
2.38 (Bonus, 12B points, due Thursday, April 16) PROB 7.4.20 (a)
(small sample space for pairwise independent non-trivial events)
[Note: PROB 7.4.20(a)was slightly updated (April 11, 4pm): the assumption
$k\ge 1$ replaced by $k\ge 3$. Thank you to a member of this class
for the warning that the statement is false for $k=2$.]
2.39 CH (no deadline, no point value) PROB 7.4.20 (b)
(small sample space for pairwise independent events with probability
$1/2$)
2.40 CH PROB 7.4.22 (tight lower bound on sample space size
for pairwise independent non-trivial events)
2.43 DO
You are expected to solve all exercises from the
sections of PROB indicated in READING exercise 2.2. Please pay
special attention to PROB Section 7.7
(Random variables, expected value, indicator variables).
In particular, do not miss 7.7.3 (equivalence
of the alternative definition of expected value), 7.7.5 ($E(X)$
is between the minimum and the maximum value of $X$), 7.7.6
and 7.7.7 (linearity of expectation),
7.7.10 (bijection between events and indicator variables),
7.7.11 (expected value of an indicator variable).
2.44 WORKED EXAMPLE (done in class). [Added April 11, 11:59pm]
In the hat-check problem,
$n$ customers at an establishment check their hats on arrival.
They have to leave in a hurry, so the hat check person hands
each of them a hat at random. All the $n!$ permutations of
the hats are equally likely. Call a customer lucky
if they get their own hat. Determine the expected number
of lucky customers. State the size of the sample space
for this problem.
2.45 HW (20 points) PROB 7.7.18 (Club of 2000)
(Hint: indicator variables.) Half the credit goes for
an accurate definition of the random variables you use
in your solution.
2.50 DEF Let $A,B$ be sets. Then $B^A$ denotes the
set of functions with domain $A$ and codomain $B$, i.e.,
the set of functions $f:A\to B$.
2.51 DO If $A$ and $B$ are finite sets then
$\left|B^A\right| = |B|^{|A|}$.
2.52 DEF Let $A, B$ be finite sets and $f\in B^A$.
Let $x,y\in A$, $x\neq y$. We say that $x$ and $y$ collide
(under $f$) if $f(x)=f(y)$. Let $c(f)$ denote the number of collisions,
i.e., the number of unordered pairs $\{x,y\}$ $(x,y\in A, x\neq y)$
such that $x$ and $y$ collide. Clearly $0\le c(f)\le \binom{m}{2}$.
The function $f$ is injective if and only if $c(f)=0$.
2.53 DO
Let $A, B$ be finite sets of respective cardinalities $|A|=m$ and $|B|=k$.
Pick $f\in B^A$ at random (under the uniform distribution). Prove
that the probability that $f$ is an injection is
$$ P(c(f)=0) = \frac{k(k-1)\cdots(k-m+1)}{k^m}=\prod_{i=0}^{m-1}\frac{k-i}{k}
= \prod_{i=0}^{m-1}\left(1 - \frac{i}{k}\right)
.$$
Later we shall analyze the behavior of this quantity; we shall see that
it is small if $m$ is much greater than $\sqrt{k}$ and large if
$m$ is much smaller than $\sqrt{k}$. This phenomenon is called
the "Birthday paradox."
2.55 HW (9+1 points, due Thursday, April 16) (Collisions)
Let $A, B$ be finite sets of respective cardinalities $|A|=m$ and $|B|=k$.
2.60 STUDY conditional probabilities (PROB Section 7.2)
2.61 HW (4+9+3 points, due Thursday, April 16)
PROB 7.2.5 (a) (b) (c) (Probability of causes)
Show your work! State all intermediate results.
Express your answers as exact simple fractions rather
than decimal approximations.
1.1 HW (3 points) Assigned 04-07 due 04-09 by noon on Canvas.
State three of your favorite theorems, one each from (a) analysis,
(b) linear algebra, and (c) discrete mathematics. If you don't
have a favorite theorem in DM, add a second theorem in one of the
other two subjects.
For a theorem to qualify, you need to certify that you have studied
the proof. Include any definitions that may not be part of an
introductory course. If you are not sure whether a concept needs
to be defined, ask the instructor by email. If a theorem has
a name, state the name as well.
This assignment has only a nominal point value; the main purpose is
to test the mechanics of homework submission. Make sure to state
your name, the date, and the homework number (HW1 in this case)
prominently at the top of the first page of your submission.
Please typeset your answer in LaTeX and compile it to PDF.
If you don't know LaTeX yet, please contact the instructor by email.
1.2 DO Let $p_1,\dots,p_m$ be $m$ points in $\rrr^n$,
pairwise at unit distance:
$(\forall i,j)(\text{ if }1\le i < j \le m\text{ then }
\|p_i-p_j\|=1)$ where $\|.\|$ stands for the standard
euclidean norm: for the vector $x=(x_1,\dots,x_n)$
we set $\|x\|=\sqrt{x_1^2+\dots+x_n^2}$. Prove: $m\le n+1$.
1.3 DO A set $S=\{p_1,\dots,p_m\}$ of points in $\rrr^n$ is
a two-distance set if $(\exists s,t\in\rrr)$ such that
the distance of every pair of points in $S$ is $s$ or $t$.
Find as large a two-distance set in $\rrr^n$ as you can.
Find a set of quadratic size, i.e., of size $m \ge cn^2$
for some constant $c>0$ and all sufficiently large $n$.
Hint: find a two-distance set of size $m=\binom{n}{2}$.
Can you find an even larger set?
1.3 DO Calculate the determinant of the $n\times n$ matrix
$J-I$ where $J$ is the all-ones matrix (every entry is 1)
and $I$ is the identity matrix. You should get a simple formula.
REFRESH your browser to see latest update
Homework set #9.
This is the last set of problems.
Most problems are due Tuesday, June 2, at 11:59pm.
Some problems are due Wednesday, June 3, at 11:59pm.
There will be no tests/exam.
Due dates.
Tuesday, June 2: ORDINARY problems: 9.14, 9.65, 9.67, 9.75.
BONUS problems: 8.105, 8.107, 8.110, 8.127
Wednesday, June 3: BONUS problems only: 9.44, 9.60, 9.80b.
$$T_k(x) = \frac{1}{2}\left((x+\sqrt{x^2-1})^k+(x-\sqrt{x^2-1})^k\right)$$
This formula holds for all $x\in\rrr$, including in the interval
$-1 < x < 1$. Explain!
$$U_k(x) = \frac{\left((x+\sqrt{x^2-1})^k-(x-\sqrt{x^2-1})^k\right)}{2\sqrt{x^2-1}}$$
This formula holds for all $x\in\rrr$, $x\neq \pm 1$, including in the interval
$-1 < x < 1$. Explain!
Hint. Let $q(x)=p(x)-2^{1-k}T_k(x)$. Then $\deg(q)\le k-1$.
Analyze the values $q(\lambda_j)$ defined in 9.40. Infer that
$q$ has at least $k$ roots and therefore must be the zero polynomial.
Remark. While the Linial-Nisan proof discussed in class on May 26 is
inspired by this extremal property of the Chebyshev polynomials,
it does not use this property directly but instead adapts the proof
outlined here to the discrete situation (maximum taken over a finite
number of values instead of the entire $[-1,1]$ interval).
(a) DO:
Let $\calH$ be a pre-STS. Prove: $\alpha(\calH)=\Omega(\sqrt{n})$.
(b) Bonus (40 points, due Wednesday, June 3)
Prove that for every $n$ there exists a preSTS
$\calH$ with $n$ vertices such that $\alpha(\calH) = O(n^{0.76})$.
Use the probabilistic method. State your sample space and the
probability distribution.
REFRESH your browser to see latest update
Homework set #8.
Sum of reciprocals of the squares. Trigonometric
identities from application of the Binomial Theorem to the de Moivre formula.
Generating functions. Number-partition function. Random number
puzzle. Ramsey's Theorem, the Erdös-Rado arrow symbol.
Strong concentration: Chernoff bounds. Discrepancy.
Due dates.
In addition to the problems assigned in this section (Homework set 8),
the following Bonus problems are due Tuesday, May 26, by 11:59pm:
7.12, 7.13, 7.77, 7.86.
[Update: typo on right-hand side of trig identity fixed 5-22, 7pm]
(a) (HW, 10 points, due Tuesday, May 26)
Determine the odd-term generating function
$O(x)=\sum_{n=0}^{\infty} o_nx^n$.
(b) (HW, 10 points, due Tuesday, May 26)
Determine the distinct-term generating function
$D(x)=\sum_{n=0}^{\infty} d_nx^n$.
Each answer should be given as an infinite product of very simple expressions,
each expression being either the sum of two terms or the reciprocal of such
an expression. Give a brief reasoning why your infinite products
represent the generating functions in question.
(a)
Prove: for all $x$ in the interval $0 < x < 1$ we have
$\displaystyle{T(n,k) < \frac{(1+x)^n}{x^k}}$.
(b) Use part (a) to prove that
$\displaystyle{T(n,k) < \left(\frac{\eee n}{k}\right)^k}$.
(A proof that does not essentially use part (a) will not be accepted.)
(a) (Bonus, 28 points, due Friday, May 29)
Prove: two of the increments must be equal.
(b) (HW, 10 points, due Tuesday, May 26)
Construct and example where $k=100$
and all the increments are distinct except $d_1=d_2$.
(c) (DO) Prove that no two of the increments can be relatively
prime.
Remark. So the goal is to find a coloring that has low
discrepancy simultaneously on all edges -- the coloring of
all large edges is balanced
-- the number of blue vertices and red vertices within the edge
is almost the same. Random coloring does a pretty good job.
Cases of particular interest are those where (1) the random
coloring can be replaced by an explicit coloring, or at
least one that can be found algorithmically; (2) where
the random coloring can be beaten (we can achieve smaller
discrepancy than by random coloring).
Discrepancy plays a big role not only in combinatorics but
in other areas of mathematics such as number theory and
discrete geometry, probability theory (Markov chains),
computational complexity theory,
and also in application areas such as
statistics and machine learning.
[Update: in part (a), the upper bound, previously stated as $n/2$,
was changed to $(n+1)/2$, May 24, 1am]
[Update: first sentence was added 5-24, 1am]
Remark: This hypergraph, and its discrepancy,
play an important role in Communication complexity theory,
a core branch of the theory of computing (a.k.a. theoretical
computer science).
In other words, given $n,k,r$, for all sufficiently large $N$,
for every $k$-coloring of the $r$-subsets of $[N]$ there is
a homogeneous $n$-subset.
So $\tower_1(x)=2^x$, $\tower_2(x)=2^{2^x}$, etc.
(Here $O_k$ and $\Omega_k$ mean the usual bog-Oh and big-Omega symbols
where the implied constant depends on $k$).
So for instance $2^{cn^2} < R_3^2(n) < 2^{2^{c'n}}$ for suitable
constants $c,c' > 0$.
WARNING. Even though Nagy's result is generally stronger
than Exercise 8.89, solving this problem will not
earn you credit for 8.89.
REFRESH your browser to see latest update
Homework set #7.
$\tau$-critical hypergraphs. Smith normal form.
Projective planes of order $4k+2$ and self-dual codes.
The MacWilliams identity. Polarities of projective planes.
Chromatic number of Steiner Triple Systems. Generating functions.
Fibonacci numbers. Bell numbers, estimates, recurrence, exponential
generating function, Dobiński's formula, asymptotic formula.
Due dates.
The following problems are due Tuesday, May 19, by 11:59pm:
HW6.71, 7.08, 7.11, 7.38, 7.40, 7.51, 7.60, 7.74, 7.80 and
Bonus problems 6.10, 6.60, 6.65, 6.69, 7.72, 7.82.
The following problems are due Friday, May 22, by 11:59pm:
HW7.108, 7.114, 7.125, 7.150 and Bonus 7.42, 7.45, 7.62, 7.84, 7.140, 7.142
These lists are complete as of May 12, 8pm, but further problems may be
added later this week.
If that happens, the added problems will also be added to these lists.
For every odd number $n\ge 1$, find a village graph with $n$ vertices.
[Update: The previous wording was that there are no village
graphs other than the one for every odd number that you
found in the preceding exercise. This is correct but the
revised version is accessible even if you did not solve 7.11.]
Example.
$$ \begin{pmatrix} \boe & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & \boe & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & \bth & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & \bsx & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & \ftw & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & \ftw & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & \hxe & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & \bzo & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \bzo & 0 & 0 & 0 \\
\end{pmatrix} $$
(DO) Note that $d_j(A)=0 \iff j > r$. For $j\le r$ we call
$d_j(A)$ the $j$-th determinantal divisor of $A$.
[Update: in the last two sentences, $a_j$ and $d_j$ were switched.
Update posted: 5-18, 7:50pm]
(b) Permuting the columns of $A$ has the same type of effect.
(c) Same about elementary row operations; here the multiplication comes
from the left. (Do not repeat the arguments from (a) and (b),
just use the identity $(AB)^T=B^TA^T$.)
(a) \begin{pmatrix} 1 & 5 & 3 \\
4 & 2 & 0 \\
1 & 1 & 1
\end{pmatrix}
(b) The diagonal matrix $\diag(4, 6, 8, 30, 30)$.
Prove you answers. You may use all statements above.
Example: If a row of $M$ is $(0 1 1 0 0 0 1)$ then the augmented
row will be $(0 1 1 0 0 0 1 \boe)$.
We shall call the resulting $N\times (N+1)$ matrix the augmented
incidence matrix. Let $U\le \fff_2^{N+1}$ denote the subspace
of $\fff_2^{N+1}$ spanned by the rows of the augmented incidence matrix.
$[3]$, $\{1\}\sqcup\{2,3\}$, $\{2\}\sqcup\{1,3\}$, $\{3\}\sqcup\{1,2\}$,
$\{1\}\sqcup\{2\}\sqcup\{3\}$.
The first few values of the $B_n$
sequence are $B_0=1$, $B_1=1$, $B_2=2$, $B_3=5$, $B_4=15$, $B_5=52$,
$\dots$.
After having solved this problem, compare your solution with the handout
The greatest term in Dobiński's formula.
"Let $\calH$ be an $r$-uniform hypergraph such that every vertex
has degree $\le f(r)$. Then $\calH$ is 2-colorable." Find as
large a value of $f(r)$ as you can so as to make the statement
true. Express your $f(r)$ as a simple formula in terms of $r$.
The value $f(r)$ should depend on $r$ only and cannot involve any other
parameter of $\calH$ (such as the number of vertices).
Use the Lovász Local Lemma (LLL) for the proof.
Prove that the assumptions of LLL are satisfied in your model.
$f(r)$ should be "close" to $2^r$ in the sense that
$\log_2 f(r) \sim r$. Verify that your choice of $f(r)$
satisfies this requirement.
What this means is that (1) regardless of the matrix presented by
the House, the Patron can always achieve a positive payoff of
$\Omega(n^{3/2})$. (2) The House can keep the Patron from
winning more, i.e., there exists a matrix $A$ such that no matter
what rows and columns the Patron switches, the payoff willl
always remain $O(n^{3/2})$.
REFRESH your browser to see latest update
Homework set #6.
The following problems
are due Tuesday, May 12, by 11:59pm: ordinary HW problems
5.150, 5.162, 5.164, 5.194, 6.15, 6.17 and
Bonus problems 5.17, 5.18, 5.20,
5.21, 5.55, 5.170, 5.202.
The following problems are due Friday, May 15, by 11:59 pm:
ordinary HW problems 5.96, 6.3, 6.27, 6.42, 6.47, 6.48, and
Bonus problems 5.107, 5.108, 6.9, 6.29, 6.44, 6.53.
Recall also that for a grade of A
you need to collect at least 50% of the Bonus points and
for a grade of A-, at least 25%. (These are necessary but not
sufficient conditions for these grades.)
Example: $B(n,3)=\binom{n}{0}+\binom{n}{3}+\binom{n}{6}+\dots$.
The set of polynomials in variables $x_1,\dots, x_n$ over $\fff$
is denoted $\fff[x_1,\dots,x_n]$. This is a vector space over $\fff$.
The monomials are linearly independent by definition, so
this space has infinite dimension.
A complete solution to (b) also earns you the credit
for (a), but partial credit for (b) traslates to
proportional partial credit for (a) unless you gave
a separate solution to (a).
(c) Prove: If $k_n = \Theta(\sqrt{n})$ then $P(n,k_n)$ is bounded away
from $0$ and $1$, i.e., there exist positive constants $c_1$ and $c_2$
such that for all sufficiently large $n$ we have $c_1\le P(n,k_n)\le 1-c_2$.
REVIEW the two proofs of the Inclusion-Exclusion formula
given in class on May 7.
(a) If $k$ is even then $P(\Bbar) \le S_0 - S_1 + - \dots + S_k$
(b) If $k$ is odd then $P(\Bbar) \ge S_0 - S_1 + - \dots - S_k$.
You may use any result stated above. State what you are using.
(Update: condition $0\le k\le n$ was updated to $0\le k\le m$
to make the notation consistent with 6.67. 5-11 at 9:30pm.)
Count the $f:[n]\to [5]$ surjections. Give a closed-form
expression (no summation or product signs or dot-dot-dots).
REFRESH your browser to see latest update
Homework set #5. Due Tuesday, May 5, by noon, unless otherwise
stated. Recall that problems 4.133, 4.136, 4.140, 4.145
are also due on May 5.
(a) Prove: $\FFE_n - \FFO_n = \det(J_n - I_n)$ where
$J_n$ denotes the $n\times n$ all-ones matrix and $I_n$ is the
identity matrix.
(b) (Hat-check problem)
Let $\FF_n$ denote the event that a random permutation
of $[n]$ is fixed-point-free. Prove:
$\displaystyle{P(\FF_n) = \sum_{k=0}^n \frac{(-1)^k}{k!}}$.
(c) Prove: $\lim_{n\to\infty} P(\FF_n) = 1/\eee$.
Show that this convergence is rapid: the error term is less than
$1/(n+1)!$.
Historical note:
HW 3.18 (the uniform case of Exercise 5.75)
was proved by Raj Chandra Bose (1949), generalizing an earlier
result of statistician Ronald A. Fisher (1940). (Fisher considered
"block designs." We formulate the result for the dual of Fisher's
hypergraphs; in this setting, Fisher's assumptions translate to the
hypergraph being regular, uniform, and the pairwise intersections
have the same size. Bose removed the condition of regularity.
Fisher used a Cauchy-Schwarz argument.)
Bose's proof was
revolutionary in that it introduced the linear algebra argument
into extremal combinatorics. In class we reproduced Bose's determinant
calculation to prove non-singularity. A few years later Kulendra
Narayan Majumdar
(1953) extended Bose's result to the non-uniform setting presented in
this exercise. Majumdar (later Mujindar) proved this result by solving
the Challenge problem above (5.71, calculating the arising determinant),
a nontrivial task.
(a) Prove: if $r \le n/3$ then $G < P$ (the greedy bound is stronger).
(b) Prove: $P/G \le 1 + \ln n$ (the greedy bound is not much stronger).
(c) Consider an infinite sequence of hypergraphs $\calH_k$.
Assume $\calH_k$ has $n_k$ vertices, $m_k$ edges, is regular
and $r_k$-uniform, where $n_k\to \infty$.
Assume $m_k=\Theta(n_k^3)$ and $r_k=\Theta(\sqrt{n_k})$.
Determine the limit of $P_k/G_k$ as $k\to\infty$.
This exercise is straightforward (keep deleting edges as long as you
can without reducing the covering number), yet it indicates
the significance of studying the structure of $\tau$-critical
hypergraphs to the study of the covering number.
(b) Prove: a set of $n-1$ pairwise orthogonal Latin squares exists
if and only if there exists a projective plane of order $n$.
In other words, the conjunction ("AND") of the $2^m$ Hall conditions
is necessary and sufficient for the existence of a SDR.
Let $r\ge 1$. Let $\calH=(V,\calE)$ be a hypergraph. Assume every
vertex has degree $\le r$ and every edge $E\in\calE$ has size $|E|\ge r$.
Prove: $\calE$ has a SDR. Use the Marriage Theorem.
This apparent extreme computational difficulty is a partial explanation
of the difficulty of proving theoretical results about the permanent.
Examples: $(1/n)J$, $I$, all permutation matrices.
REFRESH your browser to see latest update
Homework set #4. Due Tuesday, April 28, by noon, unless otherwise
stated. Recall that 3.53 (Bonus problem) is also due on April 28.
4.80 (DEF of an independent set in a hypergraph)
3.53 (Bonus problem: only part (a) required)
4.102 (Bonus problem: condition $n\ge 2$ added)
NOTE: There is no typo in HW 4.60, the seemingly paradoxical
question about uniform hypergraphs.
If a set $A$ has $k$ elements, we call it a $k$-set. We do not say "$A$
is $k$-uniform." The term "$k$-uniform" is an adjective of a
family, namely, a family of $k$-sets.
Note that a field has at least two elements, namely, $0$ and $1$;
by definition, $0\neq 1$. Moreover, every non-zero element has
a multiplicative inverse: $(\forall a\neq 0)(\exists b)(ab=1)$.
It follows that if $ab=0$ then $a=0$ or $b=0$.
The independence number
$\alpha(\calH)$ is the size of the largest independent set in $\calH$.
($\alpha$ is the Greek letter "alpha"; in LaTeX: $\tt \backslash alpha$.)
(b) Prove: $2^d \le \alpha_d \le 3^d$.
(b) Find a LP such that neither the primal nor the dual is feasible.
Make your matrices as small as possible.
Homework set #3. Due Tuesday, April 21, by noon, unless otherwise
stated. Recall that the following exercises, assigned
last week, are also due on April 21: HW2.8 and HW2.37.
WARNING: An initial set of exercises was posted on Tuesday, April 14,
and Wednesday, April 16. The numbering of those problems was
changed on Thursday, April 16, at 10am when additional problems
were posted.
LaTeX: $a_n \sim b_n$: $\tt a\_n \backslash sim~ b\_n$ ;
$a_n \gtrsim b_n$: $\tt a\_n \backslash gtrsim~ b\_n$ ;
$a_n \lesssim b_n$: $\tt a\_n \backslash lesssim~ b\_n$ .
Pronunciation: "Yensen."
WARNING. PROB has been updated. Make sure you are
looking at the version that says right under the title:
"Last updated on April 16, 2020." If it gives an earlier date,
you are looking at an older cached version. Refresh your browser.
Hint: Prove that $\det(B)$ is odd, by noting that $B\equiv I \pmod 2$,
i.e., every entry of the matrix $B-I$ is even.
(i) $(\forall i)(|A_i| \text{ is odd})$;
(ii) $(\forall i\neq j)(|A_i\cap A_j| \text{ is even})$.
Then $m\le n$.
Proof. Let $a_i$ be the incidence vector of $A_i$, so $a_i\in\rrr^n$.
Claim. The incidence vectors $a_1,\dots,a_m$ are linearly
independent in $\rrr^n$.
The Claim immediately implies the desired inequlity $m\le n$ (by the
"First Miracle of Linear Algebra" (LIN 1.3).
To prove the Claim, we use HW 2.20. Let $G=(g_{ij})$ be the Gram matrix
of the incidence vectros, so $g_{ij}=a_i\cdot a_j$. By DO 3.11,
each diagonal entry $g_{ii}$ of $G$ is an odd integer, and
each off-diagonal entry $g_{ij}$ $(i\neq j)$ is even. Therefore
by DO 3.12, $G$ is nonsingular. QED
The extreme cases $k=0$ and $k=n$ deserve special mention; the former
means the sequence is decreasing, the latter means the sequence is increasing.
So these two types of sequences are included among the unimodal sequences.
You cannot use Stirling's formula (because that formula would only
prove it for sufficiently large $n$). Use the power series
expansion of the exponential function.
Note (DO!) that this means $(\forall i)(P(i\in I)=1/2)$ and the $n$
events "$i\in I$" are independent.
(a) What is the size of the sample space for this experiment?
(b) Prove:
$$ P\left(\sum_{i\in I} a_i = b\right) \le
\frac{\binom{n}{\lfloor n/2\rfloor}}{2^n} $$
First solve the problem under the additional
assumption the all the $a_i$ are positive
(partial credit for this case: 6 points).
(c) Prove that this bound is tight for every $n$. In other words,
for every $n\ge 1$, find $a_1,\dots,a_n,b$ such that equality holds
in item (b).
Your solution should be just a few lines. [Only part (a)
required. -- This fix was added Apr 27, 3:45pm]
DO:
The supports of the cycles of $\pi$ form a partition of $\Omega$.
Example: Let $\pi:[10]\to[10]$ be the permutation whose cycles are
$(1,4,10)$, $(2)$, $(3,9)$, $(5,9,8)$, $(6)$. This means that
2 and 6 are fixed points of $\pi$, $\pi(1)=4$, $\pi(4)=10$, $\pi(10)=1$,
etc. We write $\pi=(1,4,10)(3,9)(5,9,8)$ (we omit the fixed points in
this notation) but we say the the number of cycles is $c(\sigma)=5$
(each fixed point counts as a cycle). (We write $\pi=()$ for
the identity permutation (that fixes all points)).
The order of the cycles does not matter, so we could equivalently write
$\pi=(9,3)(1,4,10)(9,8,5)$.
The cycle structure
of $\pi$ is described by the expression $1^2\cdot 2\cdot 3^2$,
indicating that there are two 1-cycles, one 2-cycle, and two 3-cycles.
(So the cycle structure of the identity permutation of a set of
$n$ elements is $1^n$.)
(a) Compute $|M_n(\fff_2)|$ (the number of $n\times n$ matrices over $\fff_2$).
Your answer should be a very simple formula. No proof required.
(b) Let $f(n)$ denote the number of those matrices $B\in M_n(\fff_2)$
that satisfy the equation $B^TB=0$, where $B^T$ denotes the transpose
of $B$ and "$0$" denotes the all-zero matrix in $M_n(\fff_2)$.
Let $n\ge 2$ be an even number. Prove: $\displaystyle{f(n)\ge 2^{n^2/2}}$.
(c) [Update: typo corrected 4-20 7pm]
Prove: For all sufficiently large $n$ there are more than
$2^{0.49 n^2}$ Eventown club systems, each consisting of $n$ distinct clubs.
[THE ERRONEOUS FORMULA WAS $n^{0.49 n^2}$. Thank you to two of
the students in this class for pointing out the error.]
(Recall that the clubs in an Eventown club system have even size and their
pairwise intersection also has even size.) (A club system is a set of sets,
and this defines when two club systems are equal. In particular, the
order in which the clubs are listed in City Hall does not matter.)
(a) number of people in your room
(b) the room number
(b) was there some discussion in the group?
(c) did you learn something from the discussion?
(d) did you get some new idea of your own during the discussion?
(e) did you share your ideas with the others in the room? If you knew
a complete solution, were you able to give just a hint rather
than reveal the complete solution?
(f) did more than one person contribute to the discussion?
(g) on which problems did the group make progress? (There were three problems:
(1) uniform family of subsets of $[n]$ with only two intersection
sizes -- make it large
(2) two-distance set of size greater than $\binom{n}{2}$ in $\rrr^n$
(3) degenerate projective plane with $N$ points for all $N\ge 3$.)
(h) overall, do you find such a discussion a useful way of learning?
(i) any other comments you care to make.
REFRESH your browser to see latest update
Homework set #2. Due Tuesday, April 14, by noon, unless otherwise
stated.
Determinants. Finite probability spaces, independence of events,
random variables, linearity of expectation. Collisions.
Answer:
$(a-b)^{n-1}(a+(n-1)b)$.
This answer was posted April 15, 1am, so you can use the result
in a problem due Thursday, April 16, and seberal future problems.
Instructions: Use the elementary steps
listed in DO 2.3 (elementary operations (LinAlg Chap. 3.2),
swapping columns (or rows), multilinearity, cofactor expansion,
the determinant of a triangular matrix). [This clarification of steps
was added between April 12, 6pm and April 13, 1am.]
Describe each step you make;
use the notation of LinAlg Chap. 3.2 to describe each step.
(b) For every $n\ge 1$, determine the set of all pairs $(a,b)\in\rrr^2$
such that $R_n(a,b)$ is singular, i.e., $\det(R_n(a,b))=0$.
(b) Prove:
$$\det(V_3(x_1,x_2,x_3))=(x_2-x_1)(x_3-x_1)(x_3-x_2)$$
Use elementary operations (LinAlg Chap. 3.2). Describe each step you make;
use the notation of LinAlg Chap. 3.2 to describe each step.
(c) The general result is the following.
$$\det(V_n(x_1,\dots,x_n))=\prod_{1\le i < j \le n} (x_j-x_i)$$
Understand this result.
(c1) What is the number of terms in this product? Give a
very simple expression in terms of $n$. No proof required.
(c2) Use this result to prove that the Vandermonde matrix
is singular if and only if two of the generators are equal.
Comment regarding the due date. [Added April 11, 11:30pm]
HW2.7(d) (Bonus) is due Thursday,
April 16, as stated above. On the Canvas site I made the erroneous
announcement, twice, that it is due Tuesday. Thank you to the two
students who warned me about this discrepancy.
If there is a conflict between this website and any other source of
information, then this website rules. If I become aware of a mistake
on this website, I will announce it here.
(a) Prove: If the vectors $v_1,\dots,v_k$ are linearly
dependent then their Gram matrix is singular.
(b) (Bonus) Prove the converse: If the vectors
$v_1,\dots,v_k$ are linearly independent then their Gram matrix
is non-singular.
Remark. Combining (a) and (b) we obtain a characterisation of linear
independence over $\rrr$:
The vectors $v_1,\dots,v_k\in\rrr^n$
are linearly independent if and only if
their Gram matrix is non-singular.
(b) Construct a finite probability space
$(\Omega,P)$ and three pairwise independent events of probability
$1/2$ in it. Make your sample space as small as possible.
(c) Prove that your sample space is smallest possible. You may use
an exercise stated above.
Solution. The sample space $\Omega$ is the set of all permutations
of the hats, so $|\Omega|=n!$. Let $X$ denote the number of
lucky customers and $Y_i$ the indicator that the $i$-th customer
is lucky, so $Y_i=1$ if the $i$-th customer is lucky and
$Y_i=0$ otherwise. So $X=\sum_{i=1}^n Y_i$. Therefore, by the
linearity of expectation, $E(X)=\sum_{i=1}^n E(Y_i)$.
But $E(Y_i)$ is the probability that the $i$-th customer
is lucky, which is $1/n$ by symmetry (each hat has an equal
chance of being handed to the $i$-th customer). So
$E(X)=n\cdot (1/n)=1$. The expected number of lucky
customers is 1.
Remark. Avoiding collisions is a principal goal when constructing
hash functions.
Pick $f\in B^A$ at random (under the uniform distribution).
(a) Calculate the expected number of collisions. Your answer should be
a simple formula in terms of $m$ and $k$. Show all your work.
Half the credit goes for an accurate definition of the random
variables you use.
(b) State, for what value of $k$ (as a function of $m$) is the
expected number of collisions exactly 1.
Homework set #1, due Thursday, April 9, by noon
View the instructor's
class material from previous years
Return to the
Department of Computer Science home page
Course home
Go to top