10.1 DO (Fekete's Lemma): Let $a_1,a_2,\dots$ be a sequence of positive real numbers. Assume $(\forall k,\ell)(a_{k+\ell}\ge a_ka_{\ell})$. Prove: the limit $\lim_{n\to\infty} a_n^{1/n}$ exists and is equal to $\sup_{n} a_n^{1/n}$.

10.2 DO: Recall that a Steiner Triple System (STS) is a 3-uniform hypergraph such that for every pair $\{x,y\}$ of distinct vertices there is exactly one edge that contains both $x$ and $y$. We call the edges "lines" from the geometric analogy that every pair of points determines a unique line. The vertices are referred to as "points" to emphasize the geometric analogy. The number of points is called the order of the STS.   (a) Prove: a STS is a regular hypergraph, i.e., every point has the same degree. What is the degree (as a function of $n$, the order of the STS)?   (b) What is the number of lines?   (c) Prove: if a STS of order $n$ exists then $n\equiv 1$ or $3 \pmod 6$.

10.3 CHALLENGE: The condition on $n$ in the previous exercise is necessary and sufficient: if $n\equiv 1$ or $3 \pmod 6$ then there exists a STS of order $n$.

10.4 DO: Recall that the Fano plane is the (unique) STS with 7 points. It has 7 lines. Prove: it has 168 automorphisms.

10.5 DO: In class we constructed STSs of orders 1, 3, 7, 9. Construct a STS of order 13. Hint: your STS should have a cyclic automorphism of order 13 (the point can be arranged on a circle such that the rotation by $2\pi/13$ will be an automorphism).

10.6 DO: Let ${\cal L}_d$ denote the set of affine lines in the space $\fff_3^d$. (Here $\fff_3$ denotes the field of order 3, i.e., the modulo 3 residue classes under the natural operations of addition and multiplication. $\fff_3^d$ is the $d$-dimensional vector space over $\fff_3$. An affine line in a vector space $V$ over the field $\fff$ is a translate of a 1-dimensional subspace, i.e., it is a set of the form $\{u+tv\mid t\in\fff\}$ where $u, v\in \fff$ and $v\neq 0$. Here $\fff$ is the field of scalars; in our case $\fff=\fff_3$; but the definition remains the same for affine lines over $\fff = \rrr$ and any other field.) Note that each affine line over $\fff_3$ has 3 points, so the hypergraph $A(d,3) = (\fff_3^d,{\cal L}_d)$ is 3-uniform.
(a) Prove that $A(d,3)$ is a STS. (Note: $|A(d,3)|=3^d$.)
(b) Prove that $\aut(A(d,3))$ is doubly transitive, i.e., if $x\neq y$ and $x'\neq y'$ are points then $(\exists \sigma\in\aut(A(d,3))$ such that $\sigma(x)=x'$ and $\sigma(y)=y'$.

10.7 DO: Let $x,y,z\in \fff_3^d$. Prove: $x+y+z=0$ if and only if either $x=y=z$ or $\{x,y,z\}$ form an affine line.

10.8 DO: The SET card-game consists of 81 cards; certain triples of cards are called SETs. (a) Prove that these SETs form a STS.   (b) Prove: this STS is isomorphic to $A(4,3)$.   (c) generalize the SET cards to $d$ dimensions and show that the STS you get is isomorphic to $A(d,3)$.

10.9 DO: Let $\alpha_d = \alpha(A(d,3))$ (the independence number of the hypergraph $A(d,3)$). Verify: $\alpha_1=2$,   $\alpha_2=4$,  $\alpha_3=9$. It is known further that $\alpha_4 = 20$ (this is relevant to the card-game SET), $\alpha_5 = 45$, and $112\le\alpha_6\le 114$. (Find these results on the web.)

10.10 HW: (a) Prove: $\alpha_{k+\ell}\ge \alpha_k\alpha_{\ell}$.   (b) So by Fekete's Lemma (Ex. 10.1), the limit $L = \lim_{n\to\infty} \alpha_n^{1/n}$ exists. Prove: $2 < L \le 3$. Give an explicit lower bound for $L$; make it as large as you can. You may use the results of Ex. 10.9. (Note: it is a major open question whether or not $L=3$. Roy Meshulam proved in 1995 that $\alpha_d \le (2/d)3^d$.)     (10+6 points)

10.11 DO (due Monday, April 28): Let $S=(V,E)$ be a STS. For $x,y\in V$ let $x*x=x$ and if $x\neq y$ then let $x*y$ denote the third point of the line through $x$ and $y$. Note that $x*y=y*x$ and $x*(x*y)=y$.
A subset $W\subseteq V$ defines a subsystem of $S$ if $W$ is closed under the $*$ operation (i.e., either $W$ is empty or the subhypergraph induced by $W$ is also a STS). This subsystem is proper if $W\neq V$. Prove: if $S$ has order $n$ then every proper subsystem has order $\le (n-1)/2$.

10.12 DO (due Monday, April 28): We say that a subset $A\subseteq V$ generates the STS $S=(V,E)$ if no proper subsystem of $S$ contains $A$. Prove: If $S$ has order $n$ then $S$ is generated by $\le \log_2(n+1)$ elements.

10.13 DO (due Monday, April 28): Prove: an STS of order $n$ has $\le n^{\log_2(n+1)}$ automorphisms.

9.1 HW ($k$-paradoxical tournaments): Let $T = (V,E)$ be a tournament. Here $E\subset V\times V$ is the set of directed edges, and we write $x\to y$ if $(x,y)\in E$. Using the analogy from sports, we say in this case that $x$ beat $y$. For a subset $A\subset V$ and a vertex $x\notin A$ we write $x\to A$ if $(\forall y\in A)(x\to y)$, i.e., $x$ beat all members of $A$. For a positive integer $k\le n-1$ we say that $T$ is $k$-paradoxical if for all subsets $A\subset V$ of size $|A|=k$ there is a player who beat all members of $A$, i.e., $(\exists x\in V)(x\to A)$. Prove that for every $k$ there exists a $k$-paradoxical tournament. Estimate the smallest number of vertices for which you can prove that a $k$-paradoxical tournament exists. Your estimate should be of the form $n \le ak^b c^k$ where $a,b,c$ are constants. State your values of $b$ and $c$. (You don't need to calculate $a$.) Find the smallest possible value of $c$ (but you don't need to prove it is smallest).     (16 points)

9.2 DO: A regular tournament on $n$ vertices exists if and only if $n$ is odd. (A directed graph is regular if all vertices have the same in-degree and all vertices have the same out-degree.)

9.3 DO: study equivalence relations. How does a partition of a set give rise to an equivalence relation? Prove: every equivalence relation arises from a (unique) partition. So equivalence relations define partitions.   A partition of a set $A$ is a representation of $A$ as the disjoint union of non-empty subsets (the blocks of the partition). The blocks of the partition are called the equivalence classes of the equivalence relation. For instance, in a set of colored objects, each having just one color, "having the same color" is an equivalence relation, and all the red object form one of the equivalence classes (assuming there is at least one red object).

9.4 DO: (a) Let $G=(V,E)$ be a graph. We say that vertex $x$ is accessible from vertex $y$ if there exists a path between $x$ and $y$. Prove: accessibility is an equivalence relation. (Note: paths of length zero count. Explain the significance of this comment.) The equivalence classes are called the connected components of the graph.
(b) Let $G=(V,E)$ be a digraph. We say that vertex $x$ is accessible from vertex $y$ if there exists a directed path from $x$ to $y$. Prove: (b1) Accessibility is not necessarily an equivalence relation. (b2) Mutual accessibility is an equivalence relation. (Vertices $x$ and $y$ are mutually accessible if each is accessible from the other.) The equivalence classes are called the strong components of the graph.

9.5 DO (by Friday): Suppose a set of $k$ transpositions generates the symmetric group $S_n$. Prove: $k\ge n-1$.

9.6 DO: Fix the integer $m\ge 1$. Prove: congruence modulo $m$ is an equivalence relation on the set of integers. The equivalence classes of this equivalence relation are called residue classes modulo $m$. What are the residue classes modulo 5? (Warning: these are infinite sets.) What is the number of residue classes modulo $m$?

9.7 DO: One can add, subtract, and multiply mod $m$ residue classes by performing these operations on representatives of each residue class. What do we need to prove about congruences to justify this statement? Prove.

9.8 DO (by Friday): REVIEW the "Number theory" chapter of the instructor's Discrete Mathematics online lecture notes. Pay special attention to the greatest common divisor, congruences, the Chinese Remainder Theorem, and Fermat's little theorem.

9.9 DO (by Friday): Prove: $(\forall a,b)(\exists u,v)(\gcd(a,b)=au+bv)$ (the greatest common divisor is a linear combination with integer coefficients).

9.10 DO: A multiplicative inverse of the number $a$ modulo $m$ is a number $x$ such that $ax \equiv 1 \pmod m$. Prove: A multiplicative inverse of $a$ mod $m$ exists if and only if $a$ and $m$ are relatively prime (i.e., $\gcd(a,m)=1$).

9.11 DO: Prove: For every $m$, the following two statements are equivalent. (a) Every non-zero residue class mod $m$ has a multiplicative inverse. (b) $m$ is a prime number.

9.12 DO: Let $p$ be an odd prime number. Def: the number $a$ is a quadratic residue mod $p$ if $a\not\equiv 0 \pmod p$ and $(\exists x)(a\equiv x^2\pmod p)$. The number $a$ is a (quadratic) non-residue if $(\forall x)(a \not\equiv x^2\pmod p)$. For instance, $-1$ is a quadratic residue modulo 5 because $-1\equiv 2^2 \pmod 5$, but $-1$ is a non-residue modulo 7 (verify!).
The Legendre symbol $\left(\frac{a}{p}\right)$ is defined to take the value $1$ if $a$ is a quadratic residue; $-1$ if $a$ is a non-residue, and $0$ is $p\mid a$. For instance, $\left(\frac{-1}{5}\right)=1$ and $\left(\frac{-1}{7}\right)=-1$ and $\left(\frac{35}{7}\right)=0$.
Prove: among the $p$ residue classes mod $p$, there are $(p-1)/2$ that are quadratic residues and $(p-1)/2$ that are non-residues. Equivalently, prove: $$\sum_{a=0}^{p-1} \left(\frac{a}{p}\right) = 0.$$

9.13 DO: Prove: If $p$ is a prime and $p\equiv -1\pmod 4$ then $-1$ is a non-residue mod $p$. (Hint: Fermat's little theorem.)

9.14 DO$^+$ (by Friday): Prove: If $p$ is a prime and $p\equiv 1\pmod 4$ then $-1$ is a qudratic residue mod $p$. (Hint: use the fact that there exists a primitive root mod $p$ (look it up).)

9.15 DO: Prove that the Legendre symbol is multiplicative: $$\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right).$$ (Hint: counting.)

9.16 DO: Let $p$ be a prime such that $p\equiv -1\pmod 4$. Define the Paley tournament on the vertex set $\{0,1,\dots,p-1\}$ as follows: we set $a\to b$ if $b-a$ is a quadratic residue mod $p$. Prove that this indeed defines a tournament. What is the significance of the condition on $p$?

9.17 DO (by Friday): Prove that the Paley tournament is (a) vertex-transitive   (b) edge-transitive. ("Edge-transitive" means for every pair $e,f$ of edges there is an automorphism $\sigma$ such that $\sigma(e)=f$.)

9.18 DO (by Friday): Let $G\le\sym(\Omega)$ be a permutation group. Let us say that $y\in\Omega$ is $G$-accessible from $x\in\Omega$ if $(\exists \sigma\in G)(\sigma(x)=y)$. Prove: $G$-accessibility is is an equivalence relation on $\Omega$. The equivalence classes are called the orbits of $G$.

9.19 HW (due Friday, April 25) (orbit counting lemma): Prove: the number of orbits of a permutation group $G$ is equal to the average number of fixed points of the elements of $G$.     (10 points)

9.20 DO (by Friday): Prove: For almost every graph $G$ we have $\chi(G) > \omega(G)^{100}$. Here $\omega(G)$ denotes the clique number of $G$ (size of largest clique), so $\omega(G)=\alpha({\overline G})$.

9.21 DO (by Friday) (second moment method): Let $X$ be a nonnegative random variable. Suppose $0< \var(X) \le \epsilon (E(X))^2$. Prove: $P(X > 0) \ge 1 - \epsilon$.

9.22 CHALLENGE(G): Prove: almost every graph on $n$ vertices has a clique of size $\ge (2-o(1))\log_2 n$.   (Hint: second moment method.)

8.1 DO (Turán's Theorem): Let $t\ge 3$. Let $G$ be a graph with $n$ vertices and $m$ edges. Assume $G$ does not contain $K_t$. Prove that $m$ is not greater than the number of edges of the complete $(t-1)$-partite graph with nearly equal parts (the sizes of every pair of parts differs in at most 1).

8.2 DO: Review asymptotic notation from the online Discrete Mathematics lecture notes: big-Oh, big-Omega, big-Theta, little-oh notation. Solve the exercises of the "Asymptotic notation" chapter.

8.3 HW (Köváry-Turán-Sós): If $G$ is a graph on $n$ vertices with no 4-cycles then $m = O(n^{3/2})$ where, as usual, $n$ is the number of vertices and $m$ is the number of edges. The big-Oh notation means there exists a constant $c$ such that for all sufficiently large $n$ we have $m\le cn^{3/2}$. Estimate your value of $c$. (Hint: review the Cauchy-Schwarz proof of the Mantel-Turán theorem.)     (12 points)

8.4 CHALLENGE: This result is tight apart from the value of $c$, i.e., there exists $c' >0$ such that for all sufficiently large $n$ there exists a graph with $n$ vertices, no 4-cycles, and with at least $c'n^{3/2}$ edges.

8.5 Def: Recall that the symmetric group $\sym(\Omega)$ consists of all permutations of the set $\Omega$, so if $|\Omega|=n$ then $|\sym(\Omega)|=n!$. A permutation group acting on $\Omega$ is a subgroup $G\le \sym(\Omega)$. A permutation group $G\le \sym(\Omega)$ is transitive if $(\forall x,y\in\Omega)(\exists \sigma\in G)(\sigma(x)=y)$. We say that a (hyper)graph $H=(V,E)$ is vertex-transitive if its automorphism group $\aut(H)\le \sym(V)$ is a transitive permutation group.

8.6 DO: If $H$ is a vertex-transitive graph then $H$ is regular (every vertex has the same degree).

8.7 HW: Find the smallest graph that is regular but not vertex-transitive. You don't need to prove that it is smallest. (Smallest means it has the smallest number of vertices, and among the graphs with the same number of vertices, it has the smallest number of egdes.) Give a very clear drawing, state the parameneters (number of vertices, degree). Give a very simple reason why your graph is not vertex-transitive.     (7 points)

8.8 DO: Prove: Petersen's graph has no Hamilton cycle.

8.9 DO: Prove: Petersen's graph is vertex-transitive.   (Note: only 4 graphs are known that are connected, vertex-transitive, have at least 3 vertices, and are not Hamiltonian. Petersen's graph is the smallest of the four.)

8.10 DO: Prove: If a hypegraph is non-empty (has at least one edge), $r$-uniform (every edge has $r$ vertices) and regular (every vertex has the same degree) and every pair of edges intersects then $r \ge \sqrt{n}$.

8.11 CHALLENGE (LB): Prove: If $G$ is a connected vertex-transitive graph then $G$ has a cycle of length $\ge \sqrt{n}$. (Hint: use the preceding exercise.)

8.12 DO: Let $\pet$ denote the Petersen graph. Prove: (a) $|\aut(\pet)|=120$   (b) (DO$^+$) $\aut(\pet)\cong S_5$   (c) $\aut(\pet)$ is transitive on oriented paths of length three, i.e., if $(x_0,x_1,x_2,x_3)$ and $(y_0,y_1,y_2,y_3)$ are paths of length 3 in $\pet$ then $(\exists \sigma\in\aut(\pet))$ such that $(\forall i)(\sigma(x_i)=y_i)$.

8.13 DO (Mario Szegedy): Prove: If $G$ is a vertex-transitive graph then $\alpha(G)\chi(G)\le n(1+\ln n)$. The same is true for hypergraphs. (Note: this shows that the general lower bound $\alpha(G)\chi(G)\ge n$ is nearly tight for vertex-transitive graphs.)

8.14 DO: Let $g_n$ denote the number of non-isomorphic graphs with $n$ vertices. Prove: $$ \frac{2^{\binom{n}{2}}}{n!} < g_n < 2^{\binom{n}{2}}.$$

8.15 DO: Infer from the previous problem: $\log_2 g_n \sim n^2/2.$

8.16 DO: Prove: $$\sum \frac{1}{|\aut(G)|} = \frac{2^{\binom{n}{2}}}{n!}$$ where the summation is over all non-isomorphic graphs on $n$ vertices (so the sum has $g_n$ terms).

8.17 CHALLENGE: (a) Prove that for almost all graphs $G$ we have $|\aut(G)|=1$.   (b) Prove: for a random graph $G$ we have $E(|\aut(G)|)=1+o(1)$. Here $o(1)$ indicates a quantity that goes to zero as $n\to\infty$; the "random graph" is generated by unbiased coin flips (from the Erdös-Rényi distribution ${\mathbf G}_{n,1/2}$).

8.18 DO: Infer from part (b) of the preceding exercise that $g_n\sim \frac{2^{\binom{n}{2}}}{n!}$.

8.19 DO: Recall: a transposition is a permutation that swaps two elements and fixes everything else. Prove: the transpositions generate the symmetric group. In fact, if the elements are lined up in a single line (like books on a long shelf) then the neighbor-swaps already generate the symmetric group.

8.20 DO$^+$: Prove: The product of an odd number of transpositions is never the identity.

8.21 DO: A permutation is even if it is a product of an even number of transpositions and it is odd if it is the product of an odd number of transpositions. Prove: no permutation is both even and odd.

8.22 DO: Prove: for $n\ge 2$, the number of even permutations is the same as the number of odd permutations.

8.23 DO: The even permutations form a group called the alternating group an denoted by $\alt(\Omega)$ or $A_n$ if $\Omega=[n]$. Prove: for $n\ge 3$, the group $A_n$ is generated by the 3-cycles (permutations that move 3 elements in a cycle and fix everything else).

8.24 DO: Prove: for $n\ge 2$, the alternating group $A_n$ is the only subgroup of index 2 in $S_n$.

8.25 CHALLENGE: Let $F_n$ denote the number of fixed-point-free permutations of $[n]$. Are there more even permutations or more odd permutations amoung the fixed-point=free permutations?   (Hint: Compute $|F_n\cap A_n|-|F_n\setminus A_n|$. You should get a very simple closed-form expression.)

8.26 DO: A tournament is an orientation of the complete graph (every edge is an arrow). Prove: (a) all tournaments have a Hamilton path.   (b) All strongly connected tournaments have a Hamilton cycle.  (A digraph is strongly connected if $(\forall x,y\in V)(\exists x\to\to y$ path$)$.

7.1 HW (explicit Ramsey graphs by Zsigmond Nagy, 1973): Nagy gave the following simple explicit construction to demonstrate that $\binom{k}{3}\not\to (k+1,k+1)$. Let $k\ge 3$ and $n=\binom{k}{3}$. Nagy's graph has the vertex set $V=\binom{[k]}{3}$ (the set of 3-subsets of $[k]$). (So $|V|=n$). For $A, B$ two distinct 3-subsets of $[k]$, let $A\sim B$ if $|A\cap B|=1$. Here $\sim$ means adjacency in Nagy's graph. Prove that this graph does not contain either (a) a clique of size $k+1$, nor (b) an independent set of size $k+1$. (Note: you need to prove these for every $k$.) You may use previously assigned HW and DO exercises without proof. Clearly state what you are using. Based on these, your proof in each case should be just a few lines.      (7+7 points)

7.2 DO: Prove: is $n=\binom{k}{3}$ then $k\sim (6n)^{1/3}$. (Here, $\sim$ refers to asymptotic equality.)    So 7.1 gives a significantly stronger explicit Ramsey construction than our previous easy construction that demonstrated $n\not\to (1+\sqrt{n}, 1+\sqrt{n})$.

7.3 DO: We have seen that for every graph (indeed, every hypergraph) $\alpha\cdot \chi \ge n$. How large can the quantity $\alpha\cdot \chi$ be for graphs? For ever $n$, find $\max \alpha(G)\chi(G)$ where the maximum is over all graphs with $n$ vertices. Find the exact value of this maximum. Your answer should be a simple closed-form expression of quadratic order of magnitude.

7.5 More problems to follow. Check back later.

6.1 HW (random permutations): For a permutation $\pi :[n]\to[n]$ and $1\le i\le n$ let $c(i,\pi)$ denote the length of the $\pi$-cycle passing through $i$. Let us choose $\pi$ uniformly at random from the $n!$ permutations of the set $[n]$. (a) Prove: for every $k$ in the range $1\le k\le n$ we have $P(c(1,\pi)=k)=1/n.$   (b) Let $f(\pi)$ denote the number of cycles of the permutation $\pi$. Note that this includes cycles of length 1 (fixed points). Prove: $E(f(\pi)) \sim \ln n$. (Here $\sim$ denotes asymptotic equality.) Note: Clarity of the definition of the random variables you introduce in the proof accounts for a large part of the credit.           (8+12 points)

Exercises 6.2 - 6.9 represent an introduction to Ramsey Theory that grew out of a lemma Frank P. Ramsey (1903--1930) proved in a 1928 paper titled "On a problem of formal logic." The lemma is referred to as "Ramsey's theorem."
The Erdös-Rado arrow symbol $N\to(k,\ell)$ means the following statement: "No matter how we color the edges of the complete graph $K_N$ red and blue, there will be an all-red $K_k$ or and all-blue $K_{\ell}$."
A very special case of Ramsey's theorem asserts that for every $k$ and $\ell$ there exists $N$ such that $N\to(k,\ell)$. The smallest value of $N$ for which this is true is called the "Ramsey number" $R(k,\ell)$. Erdös and Szekeres began the study of the Ramsey numbers in 1934.

6.2 DO (baby Ramsey): (a) $6\to (3,3)$   (b) $5\not\to (3,3)$.

6.3 DO: Define the arrow symbol for more than two colors. Prove: (a) $17\to (3,3,3)$   (b) $\lceil k!\eee\rceil \to (3,\dots,3)$ ($k$ colors).

6.4 DO (Erdös-Szekeres): Prove that for all $r,s\ge 1$ $$\binom{r+s}{r}\to (r+1, s+1).$$ (Hint: Trivial when $r=1$ or $s=1$. Proceed by induction on $r+s$.)

6.5 DO: Prove: $$\frac{4^k}{\binom{2k}{k}} \sim c\sqrt{k}$$ for some constant $c$. Determine the value of $c$.

6.6 DO: (a) Prove: $4^r \to (r+1,r+1)$.   (b) Prove: for all sufficiently large $r$ we have $4^r \to (r+10,r+10)$.  (c) Prove: for all sufficiently large $n$ we have $$n\to ((1/2)\log_2 n,(1/2)\log_2 n).$$

6.7 DO: Recall: we proved by explicit construction that $n \not\to (1+\sqrt{n}, 1+\sqrt{n})$ assuming $n$ is a square. Prove for every $n$ that $n \not\to (1+\lceil\sqrt{n}\rceil, 1+\lceil\sqrt{n}\rceil).$

6.8 DO: In class we proved the following. Review the proof.
Lemma: If $$\frac{\binom{n}{t}}{2^{\binom{t}{2}}}\le 1/2$$ then $n \not\to (t,t)$.

6.9 DO (Erdös, 1950): Infer from the previous exercise: $n \not\to (1+2\log_2 n,1+2\log_2 n)$.  
Your proof sould be very simple -- just a few lines, no messy formulas.

The next two problems are also due to Paul Erdös.

6.10 DO: Let $\calH$ be an $r$-uniform hypergraph with $m\le 2^{r-1}$ edges $(r\ge 2)$. Prove: $\calH$ is 2-colorable (i.e., $\chi(\calH)\le 2$). ($r$-uniform means every edge has $r$ vertices.)   Hint: color the vertices at random.

6.11 CHALLENGE: There exists a constant $c$ such that for every $r\ge 2$ there exists an $r$-uniform hypergraph with $m\le cr^2 2^r$ edges such that $\calH$ is not 2-colorable.   (Hint: here again, use the probabilistic method. Fix a set of $n=r^2$ vertices and select $cr^2 2^r$ edges ($r$-subsets) at random. Prove that with high probability, the hypergraph obtained is not 2-colorable.)

5.1 DO (Handshake theorem for hypergraphs): Let $\calH=(V,\calE)$ be a hypergraph where $\calE=\{A_1,\dots,A_m\}$. Prove: $$\sum_{x\in V} \deg(x) = \sum_{i=1}^m |A_i|.$$

5.2 DO (independent set): A subset $S\subseteq V$ is independent is $S$ does not contain any edge: $(\forall i)(A_i\not\subseteq S)$.     $\alpha(\calH)$ denotes the maximum size of independent sets in $\calH$.
Find a graph $\calG$ which has a maximal independent of size 1 yet $\alpha(\calG)=n-1$.

5.3 DO (legal coloring): A legal coloring of a hypergraph is an assignment of "colors" to the vertices such that no edge is monochromatic. Prove: a legal coloring exists if and only if every edge has at least two vertices. $\calH$ is $k$-colorable if there exists a legal coloring with $\le k$ colors.

5.4 DO (chromatic number): The minimum number of colors required for a legal coloring is the chromatic number of the hypergraph, denoted $\chi(\calH)$. Prove: $$ \alpha(\calH)\chi(\calH) \ge n$$ where $n=|V|$ is the number of vertices.

5.5 DO: A graph is bipartite if it is 2-colorable. Prove: (a) the cycle $C_n$ is bipartite if and only if $n$ is even.   (b) Prove: the graph $\calG$ is bipartite if and only if $\calG$ contains no odd cyle.

5.6 CHALLENGE$^{**}$ (Erdös - Hajnal, 1964): Prove: if $\calG$ is an infinite graph with uncountable chromatic number then $\calG$ contains a 4-cycle. In fact it contains the complete bipartite graph $K_{r,\aleph_1}$ for every finite $r$.

5.7 DO (Grötzsch's graph): Construct a graph that is not 3-colorable and has no triangle. Your graph should have 11 vertices and 5-fold rotational symmetry if drawn appropriately.

5.8 DO$^+$: For every $k$ there exists a triangle-free graph of chromatic number $\ge k$.

5.9 DO: The girth of a graph is the length of its shortest cycle. The odd-girth is the length of the shortest odd cycle. Which graphs have (a) infinite girth (b) infinite odd-girth?

5.10 CHALLENGE: $(\forall k,\ell)(\exists \calG)(\chi(\calG)\ge k$ and odd-girth$(\calG)\ge \ell).$   Note: In a landmark 1959 paper, Paul Erdös proved that "odd-girth" can be replaced by "girth" in this statement.

5.11 DO: Prove: the maximum number of edges of a bipartite graph is $\lfloor n^2/4\rfloor$. (Note: this is a much easier statement than problem 3.12.)

5.12 DO (greedy coloring): The greedy coloring algorithm for graphs proceeds as follows. Assume $V=[n]$.

          for $i=1$ to $n$
                 color $i$ by the smallest available positive integer.

(A positive integer $t$ is not available (as a color for vertex $i$) if $t$ has already been assigned as the color of some neighbor $j$ of $i$ with $j < i$.)

(a) (greedy coloring is good) Prove: if $(\forall x)(\deg(x)\le k)$ then the greedy coloring algorithm uses at most $k+1$ colors.
(b) (greedy coloring is bad) Assume $n$ is even. Prove: there exists a bipartite graph such that the greedy coloring algorithm uses $n/2$ colors.
(c) CHALLENGE(G): Let the "random-greedy coloring" first permute the vertices at random, and then apply greedy coloring. For a graph $\calG$, let $f(\calG)$ denote the expected number of colors used by random-greedy. Let $g(n)$ denote the maximum of $f(\calG)$ over all bipartite graphs with $n$ vertices. Determine the rate of growth of $g(n)$. In particular, is $g(n)=\Omega(n)$? (The instructor does not know the answer.) This is a probably not too difficult research problem. Give upper and lower bounds on $g(n)$. Can you prove $g(n)\to\infty$?    The "CHALLENGE(G)" designation indicates that this is a priority problem for those who seek graduate credit.

5.13 DO: Prove: If $\calG$ is a triangle-free graph then $\chi(\calG)\le 2\sqrt{n}+1$.

5.14 DEF: For a directed graph (digraph) $\vec{\calG}=(V,E)$, the set of edges is a subset $E$ of $V\times V$. The directed line-graph $\vec{L}(\vec{\calG})$ has vertex set $E$; and for $(x,y)\in E$ and $(v,w)\in E$ there is a directed edges from $(x,y)$ to $(v,w)$ in $\vec{L}(\vec{\calG})$ if $y=v$.

5.15 DO: If $\chi(\vec{L}(\vec{\calG})=k$ then $\chi(\vec{\calG})\le 2^k$.

5.16 DO: If $\vec{\calG}$ has no oriented triangle then $\vec{L}(\vec{\calG})$ does not have any triangles.

5.17 DO: Use 5.15 and 5.16 to prove 5.8. (But also prove 5.8 independently.)

4.1 DO: Prove: Every subset of a set of independent random variables is independent.

4.2 DO: Prove: the events $A_1,\dots,A_k$ are independent if and only if their indicator variables are independent.

4.3 HW: (a) Construct a probability space and 3 events, each with probability $1/2$, that are pairwise but not fully independent. Make your sample space as small as possible. (You don't need to prove that it is the smallest.)       (b) Construct a probability space and $k$ events, each with probability $1/2$, that are $(k-1)$-wise but not fully independent. Make your sample space as small as possible. (You don't need to prove that it is the smallest.)     (4+10 points)

4.4 DO: Prove: if there exist $k$ nonrtivial independent events over a probability space $(\Omega,P)$ then $|\Omega|\ge 2^k$.

4.5 CHALLENGE: (a) If $n=2^k-1$ then construct $n$ pairwise independent events, each with probability $1/2$, over a sample space of size $n+1$.       (b) If $n=2^k$ then construct $n$ 3-wise indeoendent events, each with probability $1/2$, over a sample space of size $2n$.

4.6 CHALLENGE: If $X_1,\dots,X_k$ are $t$-wise independent non-constant RVs (random variables) then $$ |\Omega| \ge \binom{k}{\lfloor t/2\rfloor}$$

4.7 DO: Prove: if $X_1,\dots,X_k$ are independent RVs then $$ E(\prod X_i) = \prod E(X_i) $$

4.8 HW: Construct random variables $X,Y$ that are uncorrelated but not independent. Minimize the size of the sample space.       (10 points)

4.9 DO (Markov's Inequality): Let $X$ be a nonnegative random variable. Prove: $(\forall a>0)\left(P(X\ge a)\le \frac{E(X)}{a}\right)$. The proof should be one line.

4.10 DO (Variance): The variance of the random varoable $X$ is defined as $\var(X)=E((X-E(X))^2)$. Prove: $\var(X)=E(X^2)-(E(X))^2$.

4.11 DO (Cauchy-Schwarz): (a) Prove: $E(X^2)\ge (E(X))^2$. (b) Determine when these two quantities are equal. (c) Show that this inequality is equivalent to the inequality $|x\cdot y|\le ||x||\cdot ||y||$ where $x,y\in\rrr^n$, their dot product is defined as $x\cdot y =\sum_{i=1}^n x_iy_i$, and $||x||=\sqrt{x\cdot x}$ is the Euclidean norm.

4.12 DO (Chebyshev's Inequality): Prove: for any $b>0$, $$P(|X-E(X)|\ge b)\le \frac{\var(X)}{b^2}.$$

4.13 DO: The covariance of the random variables $X,Y$ is defined as $\cov(X,Y)=E(XY)-E(X)E(Y)$. We say that $X$ and $Y$ are positively correlated, uncorrelated, and negatively correlated if their covariance is positive, zero, or negative, respectively. Let $Y=\sum_{i=1}^k X_i$ where the $X_i$ are random variables. Prove: $$\var(Y)=\sum_{i=1}^k\sum_{j=1}^k \cov(X_i,X_j).$$

4.14 DO: Prove: if the random variables $X_1,\dots,X_k$ are pairwise independent the $\var\left(\sum X_i\right) = \sum \var(X_i)$.

4.15 DO: Let $Y$ be the indicator variable of "heads" a biased coin flip where $P($heads$)=p$ and $P($tails$)=1-p$. ($Y$ is called a Bernoulli trial with parameter $p$. "$Y=1$" represents a "success" of the Bernoulli trial, so $p$ is its probability of success.) So $E(Y)=p$. Prove: $\var(Y) = p(1-p)$.

4.16 DO: Let $X$ be the number of successes in a sequence of $k$ independent Bernoulli trials with parameter $p$. Prove: (a) $E(X)=kp$ (b) $\var(X)=kp(1-p)$.

4.17 DO (Weak Law of Large Numbers): Let $X_k$ denote the number of successes in a sequence of $k$ independent Bernoulli trials with parameter $p$ where $0 < p < 1$. Prove: for all $\epsilon >0$ $$ \lim_{k\to\infty} P(|X_k - pk| \ge \epsilon k)\to 0.$$

Exercise set #3 (Due Monday, April 7, before class)

Exercise set #2 (Due Friday, April 4)

Exercise set #1 (Due Wednesday, April 2)