20.1 DO: (a) $K_k\cdot K_{\ell} = K_{k\ell}$ and $\overline{K_k}\cdot\overline{K_{\ell}} = \overline{K_{k\ell}}$. (b) Prove: $\overline{G\cdot H}\supseteq {\barG}\cdot{\barH}$. (c) Determine all pairs of graphs $G,H$ such that $\overline{G\cdot H} = {\barG}\cdot{\barH}$.

20.2 DO: Prove: $\Theta(G)\le \chi^*({\barG})$. Here $\Theta(G)$ denotes the Shannon capacity of the graph $G$ and $\chi^*$ denotes the fractional chromatic number. Hint: prove that (a) $\alpha(G)\le \chi^*(\barG)$ and (b) $\chi^*(\overline{G\cdot H})\le \chi^*(\barG) \chi^*(\barH)$ (for all graphs $G,H$).

20.3 DO: Let $d(G)$ denote the smallest dimension such that the graph $G$ has an orthonormal representation (ONR) in dimension $d$. Prove: $\Theta(G)\le d(G)$.

20.4 DO: (a) Prove: $d(G)=1$ if and only if $G=K_n$. (b) $d(G)\le 2$ if and only if $\barG$ is bipartite. (c) Prove: $d(G) \le \chi(\barG) \le 2^{d(G)-1}$. (d) CH: Find a graph $G$ such that $d(G) < \chi(\barG)$. (e) CH: Prove: $(\exists c>1)(\forall d\ge 2)(\exists G)(d(G)\le d$ and $\chi(\barG)\ge c^d)$.

20.5 DO: Prove: if $G$ is self-complementary (isomorphic to its complement) then $\Theta(G) \ge \sqrt{n}$.

20.6 DO: Prove: $\chi^*(G)\le \chi(G)$ for every graph $G$ where $\chi^*(G)$ is the fractional chromatic number.

20.7 DO: Prove: for every graph $G$ we have $\alpha(G)\chi^*(G)\ge n$.

20.8 DO (due Tue June 3, before the office hour): Prove: for any $k,g$ there exists a graph $G$ of girth $\ge g$ and fractional chromatic number $\chi^*(G)\ge k$.

20.9 DO (due Tue June 3, before the office hour): Prove: for every $\epsilon >0$, for almost all graphs, every vertex has degree between $(1-\epsilon)n/2$ and $(1+\epsilon)n/2$.

14.1 DO (projective plane over a field, homogeneous coordinates): In class we constructed the following incidence geometry, called $PG(2,\fff)$, for any field $\fff$: Take the set $S=\fff^3\setminus\{0\}$ (the non-zero triples over $\fff$). Consider the following equivalence relation on $S$: two vectors $x,y\in S$ are equivalent if $(\exists c\in\fff^{\times})(y=cx)$. Let $P=L=S/\fff^{\times}$ be the set of equivalence classes. Let $[x]$ denote the equivalence class of the vector $x=(x_1,x_2,x_3)\in \fff^3\setminus\{0\}$. We say that $x$ is the representation of the point $[x]$ by \emph{homogeneous coordinates}. So the homogeneous coordinates of a point are unique up to scaling. Homogeneous coordinates of lines are defined analogously. We define the incidence relation as follows: we say that the point $[x]$ and the line $[y]$ are incident if $x\perp y$. (Notice that this definition is sound: incidence only depende on the equivalence class $[x]$ and not on the particular representative $x$ chosen.) Prove: $PG(2,\fff)$ is a projective plane (satisfies the three axioms listed in ex. 13.14).

14.2 DO: Prove that $PG(2,\fff_q)$ is a projective plane of order $q$. Verify it directly that every line has $q+1$ points. (These planes are called Galois planes because they are defined over the "Galois fields" $\fff_q$. This also explain the terminology of the "order" of a finite projective plane.)

14.3 DO: Prove: Every Galois plane is isomorphisc to its dual.

HW 14.4: Verify that the Fano plane is a Galois plane by putting homogeneous coordinates on the Fano plane (over $\fff_2$). Make your picture large so as to make it easily intelligible; next to every point and next to every line, you need to display a triple $[x_1,x_2,x_3]$ where $x_i\in\{0,1\}$. If you can, please use two colors, one for the coordinates of the points and another for the coordinates of the lines. To standardize the picture, make the vertices of the triangle [1,0,0], [0,1,0], [0,0,1].     (8 points)

HW 14.5: Prove that the Köváry-Turán-Sós Theorem (Ex. 8.3) is essentially tight: (a) for some positive constant $c$ and inifinitely many values of $n$, construct graphs with $n$ vertices, $m\ge cn^{3/2}$ edges, and no 4-cycles. Your solution should be very simple based on what we've just learned. State, for what values of $n$ your construction works. (b) Same as before but for every value of $n$.     (10+6 points)

13.1 DO$^+$: Let $\fff$ be a (finite or infinite) field. Let $G\le\fff^{\times}$ be a finite subgroup of the multiplicative group of $G$. Prove: $G$ is cyclic (i.e., $G$ consists of all powers of one of its elements).

13.2 DO: Use 13.1 to prove that if $q$ is a prime power and $q\equiv 1\pmod 4$ then $-1$ is the square of some element in the field $\fff_q$, i.e. $(\exists x\in\fff_q)(x^2=-1)$.

13.3 CHALLENGE: Recall the result from Ramsey theory that $17\to(3,3,3)$. Prove that this result is sharp: $16\not\to (3,3,3)$. Hint: use the field $\fff_{16}$.

13.4 DO: (a) Let $\fff$ be a field of characteristic $p$ ($p$ is a prime). The map $x\mapsto x^p$ is called the Frobenius endomorphism of $\fff$. Prove: if $a,b\in\fff$ then $(a+b)^p = a^p+b^p$.   (b) Prove: if $\fff=\fff_q$ for $q=p^k$ then the Frobenius endomorphism is an automorphism (i.e., the map $x\mapsto x^p$ is a bijection).

13.5 DO: Let $q=2^k$. Prove that every element of $\fff_q$ is a square.

13.6 DO: Let $q$ be an odd prime power. The quadratic character $\chi_2$ over the field $\fff_q$ is defined like the Legendre symbol: $$\chi_2(a)=\cases{1 & if $a\neq 0$ and $(\exists x)(x^2=a)$ \cr -1 & if $(\not\exists x)(x^2=a)$ \cr 0 & if $a=0$ } $$ Prove: $\chi_2$ is not the principal character.

13.7 RECALL (André Weil's character sum estimate): Let $\chi$ be a multiplicative character of the field $\fff_q$. Assume $\chi$ has order $k$ (i.e., $k$ is the smallest positive integer such that $(\forall a\in\fff_q^{\times})((\chi(a)^k=1)$. Let $f\in \fff_q[x]$ be a polynomial over $\fff_q$ of degree $d$. Assume $(\forall c\in\fff_q)(\forall g\in\fff_q[x])(f\neq cg^k)$. Then $$\left|\sum_{x\in\fff_q}\chi(f(x))\right|\le (d-1)\sqrt{q}.$$

13.8 DO: Let $q$ be an odd prime power. Define the directed graph $\paley(q)$ on the vertex set $V=\fff_q$ by putting a directed edge $i\to j$ ($i\neq j \in \fff_q$) if $\chi_2(j-i)=1$. Prove: (a) if $q\equiv -1 \pmod 4$ then this is a tournament (i.e., $i\to j$ if and only if $j\not\to i$) (Paley tournament); (b) if $q\equiv 1 \pmod 4$ then this is an undirected graph (i.e., $i\to j$ if and only if $j\to i$) (Paley graph).

13.9 DO (Graham-Spencer Theorem): Complete the proof of the theorem that for prime powers $q\equiv -1\pmod 4$, if $q$ is slightly greater than $k^24^k$ then the Paley tournament is $k$-paradoxical, i.e., for every subset $A\subset \fff_q$ of size $|A|=k$ there is a player $x\in\fff_q$ such that $x\to A$ ($x$ beats all players in $A$). Quantify the statement "slightly greater" -- how much greater will suffice? (Comment added 5-4 2pm: Actually, $q\ge k^24^k$ suffices, and the proof of this requires only a tiny adjustment of the proof seen in class.)

13.10 HW: A graph $G$ on $n$ vertices is $k$-universal if for every graph $H$ on $k$ vertices, $G$ has an induced subgraph isomorphic to $H$. Let us say that $G$ is $t$-unconstrained if for every set $T$ of $\le t$ vertices and for every partition of $T$ into two (possibly empty) subsets $R$ and $S$ (so $T=R\dot\cup S$) there exists a vertex $x\notin T$ such that $x$ is adjacent to all vertices in $R$ and is not adjacent to any vertex in $S$. Prove: If $G$ is $(k-1)$-unconstrained then $G$ is $k$-universal.     (10 points)

13.11 HW: Prove: there exists a constant $c>0$ such that for all $k\ge 3$ there exists a $k$-universal graph on $n \le ck^2 2^k$ vertices.     (10 points)

13.12 HW: Prove: if $q$ is a prime power, $q\equiv 1\pmod 4$ and $q$ is slightly greater than $k^2 4^k$ then the Paley graph $\paley(q)$ is $k$-universal. Quantify the statement "slightly greater" -- how much greater will suffice?     (16 points)
CLARIFICATION (added 5-4 2pm): Use Weil's character sum estimate as stated above (13.7) and use Ex. 13.10 without proof. You need to prove all other essential steps, even if it looks pretty identical with what has been done in class. - Regarding "how much greater," see the comment added to Ex. 13.9: $q\ge k^24^k$ suffices, and to prove this requires only a tiny adjustment of the proof seen in class.

13.13 DEFINITION. An incidence geometry is a triple $\calG=(P,L,I)$ where $I\subseteq P\times L$. We refer to the elements of $P$ as "points", the elements of $L$ as "lines", and $I$ the incidence relation (when does a point belong to a line). Note that this is just another term for a bipartite graph.

The dual of $\calG=(P,L,I)$ is the incidence geometry $\calG'=(L,P,I')$ where $(\ell,p)\in I' \Leftrightarrow (p,\ell)\in I$. (We switch the roles of points and lines and preserve the incidence relation.)

13.14 RECALL: A finite projective plane is an incidence geometry $(P,L,I)$ satisfying the following axioms. We view the lines as sets of points, so we can write $p\in\ell$ instead of $(p,\ell)\in I$ to express that the point $p$ is incident with the line $\ell$. In this case we say $p$ is a point of $\ell$ and that $\ell$ passes though the point $p$. We say that a line $\ell$ connects the points $p,q$ if $\ell$ passes through both $p$ and $q$. Axioms:

• every pair of distinct points is connected by a unique line (i.e., $(\forall p_1\neq p_2\in P)(\exists! \ell\in L)(p_1,p_2\in L)$)
• every pair of lines intersects
• (non-degeneracy axiom): there exist four points such that no three of them are on a line.

13.15 DO: Prove: The Fano plane is the smallest finite projective plane.

13.16 DO: (c) Prove that the dual of a finite projective plane is a finite projective plane.   (b) In particular, in a finite projective plane, every pair of distinct lines shares exacly one point.   (a) What is the dual of the Fano plane?

13.17 DO: Let $(P,L)$ be a finite projective plane. (We view it as a hypergraph so we can omit the incidence relation.) Let $\ell \in L$ be a line, and let $n=|\ell|-1$ (the number of points on $\ell$ minus one). Prove:
(a) every line has $n+1$ points (so this hypergraph is uniform)
(b) every point has $n+1$ lines passing through it (so this hypergraph is regular)
(c) $|P|=|L|=n^2+n+1$
The number $n$ is called the order of the projective plane. So the Fano plane has order 2.

12.1 DO: Review linear algebra, with finite fields in mind for scalars.

12.2 DO: Let $\fff$ be an arbitrary field and $\fff^d$ the vector space of ordered $d$-tuples of elements of $\fff$. Let $x=(x_1,\dots,x_d)$ and $y=(y_1,\dots,y_d) \in\fff^d$. Define the dot product $xy$ as $xy=\sum_i x_i y_i$. We say that $a\in\fff^d$ is perpendicular to $b\in\fff^d$ if $ab=0$. We denote this circumstance by $a\perp b$. Let $a^{\perp} = \{b\in\fff^d \mid a \perp b\}$. For $S\subseteq \fff^d$ we set $S^{\perp} = \bigcap_{x\in S} x^{\perp}$. Prove: for every subset $S\subseteq \fff^d$, the set $S^{\perp}$ is a subspace of $\fff^d$.

12.3 HW: Prove: if $U\le \fff^d$ (subspace) then $\dim(U) + \dim(U^{\perp}) = d.$ Clearly state the results you use from linear algebra.    (12 points)

12.4 DO: A subspace $U\le \fff^d$ is totally isotropic if $U\subseteq U^{\perp}$, i.e., $(\forall x,y\in U)(x\perp y)$. Prove: if $U\le \fff^d$ is a totally isotropic subspace then $\dim(U) \le \lfloor d/2 \rfloor.$

12.5 DO (Eventown Theorem): Let $A_1,\dots,A_m$ be distinct subsets of $[n]$ such that $(\forall i,j\in[m])(|A_i\cap A_j|$ is even$)$. (Note that this includes the condition that each $|A_i|$ is even.) Prove: $m\le 2^{\lfloor n/2\rfloor}$. Hint: Use the preceding exercise.

12.6 DO: Construct a $k$-dimensional totally isotropic subspace in (a)   $\fff_5^{2k}$   (b)   $\ccc^{2k}$.

12.7: More problems to follow. Please check back later.

11.1 DO: Prove: almost every graph $G$ satisfies the inequality $\chi(G) \ge \omega(G)^{100}$ where $\omega(G)$ denotes the clique number (size of largest clique).

11.2 HW (due Wed, April 30): Let $p$ be an odd prime. Let $N$ denote the number of those residue classes $s$ modulo $p$ for which both $s$ and $s+1$ are quadratic residues mod $p$. Prove that $$N=\cases{(p-3)/4 & if $p\equiv -1 \pmod 4$ \cr (p-5)/4 & if $p\equiv 1 \pmod 4$ }$$ To understand the result, first verify it for $p\le 19$. (Warning: by definition, 0 is not a quadratic residue.)     (18 points)

11.3 DO: Let $p$ be an odd prime. Prove: $$\sum_{k=0}^{p-1} \left(\frac{k^2+k}{p}\right)= -1.$$ Here $\left(\frac{a}{p}\right)$ denotes the Legendre symbol.

11.4 DO: Recall: a complex number $z$ is an $n$-th root of unity if $z^n=1$. There are exactly $n$ of these. Prove: for $n\ge 2$, the sum of the $n$-th roots of unity is 0. -- Give several proofs: (1) a proof based on the sum of the geometric progressions; (2) a geometric proof based on rotational symmetry of the set of $n$-th roots of unity; (3) observing what happens when the sum is multiplied by $z$.

11.5 DO$^+$ ($\heartsuit$): Let $A_0,\dots,A_{n-1}$ be the vertices of a regular $n$-gon inscribed in the unit circle. Let $d_i$ denote the distance between $A_0$ and $A_i$. Prove: $\prod_{i=1}^{n-1} d_i = n$. (To understand the problem, first verify the statement directly for $n=3,4,6$.) (Hint: factor the polynomial $x^n-1$.)

11.6 DO (multiplicative characters): Let $p$ be a prime number. A function $\chi : \fff_p\to \ccc$ is called a multiplicative character if $\chi(0)=0$,   $\chi(1)=1$,   and $(\forall a,b\in\fff_p)(\chi(ab)=\chi(a)\chi(b))$. (a) Observe that the Legendre symbol $\chi(a)=\left(\frac{a}{p}\right)$ is a multiplicative character by a previous exercise. (b) Prove: if $\chi$ is a multiplicative character of $\fff_p$ then for all $a\in \fff_p^{\times}$, the number $\chi(a)$ is a $(p-1)$-st root of unity. Here $\fff_p^{\times} = \fff_p \setminus \{0\}$ is the set of nonzero elements of the field $\fff_p$.

11.7 HW (due Wed, April 30): Let $\chi$ be a multiplicative character of the field $\fff_p$. We call $\chi$ the principal character if $(\forall a\in\fff_p^{\times})(\chi(a)=1)$. Suppose $\chi$ is not the principal character. Prove: $$\sum_{a\in\fff_p} \chi(a) = 0.$$ Your proof should be very simple, just a couple of lines.     (10 points)

11.8 DO: Notation: $\ccc^{\times}$ denotes the set of non-zero complex numbers. Recall: the order of $z\in\ccc^{\times}$ is the smallest positive $k$ such that $z^k=1$. Notation: $k=\ord(z)$. If no such $k$ exists then we set $\ord(z)=\infty$.   Let $z\in\ccc^{\times}$. Prove: $(\forall z\in\ccc^{\times})(\forall m\in\zzz)(z^m = 1 \ \Leftrightarrow \ \ord(z) \mid m)$. (In a divisibility relation $a\mid b$ and in expressions $\gcd(a,b)$ and $\lcm(a,b)$, if $a$ or $b$ (or both) are the symbol $\infty$, this symbol should be replaced by $0$. Show that with this convention, the statement above remains true even if $z$ has infinite order, and the same is true for the subsequent exercises.)

11.9 DO: Let $z,w\in\ccc^{\times}$. Let $\ord(z)=k$ and $\ord(w)=\ell$. Let $x=zw$ and $\ord(x)=m$. Prove: (a)   $m \mid \lcm(k, \ell)$. (b)   if $\gcd(k,\ell)=1$ then $m =k\ell$.

11.10 DO$^+$: With the notation of the previous exercise, prove: $$ \frac{\lcm(k,\ell)}{\gcd(k,\ell)} \mid m.$$

11.11 DO: Prove: $$\ord(z^k) = \frac{\ord(z)}{\gcd(k,\ord(z))}.$$

11.12 DO: Recall: a complex number $z$ is a primitive $n$-th root of unity if $\ord(z)=n$. Prove: every $n$-th root of unity is a primitive $d$-th root of unity for some $d\mid k$.

11.13 DO: Prove: $z$ is a primitive $n$-th root of unity if and only if the powers of $z$ are exactly all $n$-th roots of unity.

11.14 DO: Let $v_1,\dots,v_n$ be $n$ unit vectors in the plane, pointing in random directions. Let $w=\sum_i v_i$. Prove: (a) $E(w)=0$.   (b) $E(|w|^2)=n$.

11.15 HW (Gauss sum, due Wed, April 30): Let $p$ be an odd prime and $z$ a primitive $p$-th root of unity. Let $Q(p)=\sum_{k=0}^{p-1} z^{k^2}$. Prove: $|Q(p)|=\sqrt{p}$. (Hint: multiply $Q(p)$ by its complex conjugate.) Philosophical comment: if we add up $n$ unit vectors in the plane that point in random directions, by the previous exercise we expect their sum to have absolute value about $\sqrt{n}$. The fact that $Q(p)$ has absolute value exactly $\sqrt{p}$ is an indication that the quadratic residues mod $p$ (the exponents in the Gauss sum) are an imitation of a random set.     (12 points)

11.16 DO (Euler's $\vf$ function): $\vf(n)$ denotes the number of those integers in $[n]$ that are relatively prime to $n$. Verify: $\vf(1)=1$; for a prime number $p$ we have $\vf(p)=p-1$; for prime powers we have $\vf(p^k)=p^k-p^{k-1} = p^k(1-1/p)$; and for distinct primes $p,q$ we have $\vf(pq)=(p-1)(q-1)$.

11.17 DO: An arithmetic function is a function of which the domain is the positive integers. We say that an arithmetic function $f$ is multiplicative if $f(ab)=f(a)f(b)$ whenever $a$ and $b$ are relatively prime (i.e., $\gcd(a,b)=1$). Prove: Euler's $\vf$ function is multiplicative.

11.18 DO: Prove: $\vf(n) = n\prod(1-1/p)$ where the product extends over all prime divisors of $n$.

11.19 DO: Prove: $\inf_n \vf(n)/n = 0$.

11.20 DO: Prove: The number of primitive $n$-th roots of unity is $\vf(n)$.

11.21 DO: Prove: $$\sum_{d\mid n} \vf(d) = n.$$ (Hint: previous ex.)

11.22 DO (Moebius function)): Let $n=p_1\dots p_k$ be the factorization of $n$ into primes. (So for $n=1$ we get $k=0$.) We say that $n$ is square-free all the $p_i$ are distinct. We define $\mu(n)$ to 0 if $n$ is not square-free, and $\mu(n)=(-1)^k$ if $n$ is square-free. So for instance $\mu(1)=1$,   $\mu(p)=-1$ for every prime $p$,   $\mu(p^2)=0$,   and $\mu(pq)=1$ for distinct primes $p,q$. (a) Prove: the Moebius function is multiplicative. (b) Determine $\sum_{d\mid n} \mu(d)$.

11.23 DO (Moebius inversion): Let $f$ be an arithmetic function. Let $g(n) = \sum_{d\mid n} f(n)$. Prove: $f(n) = \sum_{d\mid n} \mu(n/d)g(d)$.

11.24 CHALLENGE: Let $A=(\gcd(i,j))$ denote the $n\times n$ matrix of which the $(i,j)$ entry is $\gcd(i,j)$. Prove: $\det(A) = \vf(1)\vf(2)\cdots\vf(n)$.

11.25 DO: Let $f,g$ as in the Moebius inversion problem above. Prove: $f$ is multiplicative if and only if $g$ is multiplicative.

11.26 DO: Prove: the Moebius function is multiplicative.

11.27 DO: Let $S(n)$ denote the sum of the primitive $n$-th roots of unity. Prove: $S(n)=\mu(n)$. (Hint: Prove that $S(n)$ is multiplicative and determine $S(n)$ for prime power values of $n$.)

11.28 (cyclotomic polynomials): Let $\Phi_n(x)=\prod_z(x-z)$ where the product extends over all $z$ that are primitive $n$-th roots of unity. This is a polynomial of degree $\vf(n)$. (a) Prove:   $x^n-1 = \prod_{d\mid n} \Phi_d(x)$.   (b) Verify: $\Phi_1(x)=x-1$,   $\Phi_2(x)=x+1$,   $\Phi_3(x)=x^2+x+1$,   $\Phi_4(x)=x^2+1$,   $\Phi_5(x)=x^4+x^3+x^2+x+1$,   $\Phi_6(x)=x^2-x+1$.   (c) Prove: All coefficients of $\Phi_n$ are integers.  

11.29 THEOREM (look it up): The cyclotomic polynomials are irreducible (over the rationals).