Material covered:   The spectral gap. Isoperimetric ratio: edge-boundary and vertex-boundary. Laplacian and adjacency eigenvalues. Expanders. Ramanujan graphs. Expander mixing lemma. Finite Markov Chains. Convergence of the naive random walk on a regular graph.

18.10 A lecture about spanning trees and the law.   See above.

18.20 Notation   Let $G=(V,E)$ be a graph of order $n$ with adjacency matrix $A$ and Laplacian $L$ (see Def 5.125). Let the adjacency eigenvalues be $\lambda_1\ge\lambda_2\ge\dots\ge\lambda_n$ and the Laplacian eigenvalues $\kappa_0=0 \le \kappa_1 \le \dots\le \kappa_n$. Recall that $G$ is connected if and only if $\kappa_1 > 0$. Moreover, if $G$ is connected then $\lambda_2 < \lambda_1$.
Henceforth in this section we assume $G$ is connected.

18.30 DEF (vertex and edge-boundary, isoperimetric ratio, expanders)   For $X,Y\subseteq V$ let $E(X,Y)=\{(x,y)\mid x\in X, y\in Y, x\sim y\}$.
Note: If $X$ and $Y$ are disjoint then $|E(X,Y)|$ counts the edges that connect $X$ and $Y$. If $X$ and $Y$ overlap than the edges within the intersection are counted twice. In particular, $|E(X,X)|=2|E(G[X])|$.
The edge-boundary of $X\subseteq V$ is the set $\delta(X) = E(X,\Xbar)$ where $\Xbar = V\setminus X$ is the complement of $X$.
The vertex-boundary of $X\subseteq V$ is the set $$\partial X = \{y\in\Xbar\mid (\exists x\in X)(x\sim y)\}= \left(\bigcup_{x\in X} N(x)\right)\setminus X\,.$$ The edge-isoperimetric ratio is defined as   $\displaystyle{\frac{|\delta X|}{|X|}}$.   The vertex-isoperimetric ratio is defined as   $\displaystyle{\frac{|\partial X|}{|X|}}\,.$

$G$ is an $\epsilon$-expander if for all subsets $X\subseteq V$ of size $1\le |X|\le n/2$ we have $|\partial X|/|X| \ge 1+\epsilon$.

18.40 DEF   Let $I\subseteq\nnn$ be an infinite set of natural numbers. An infinite sequence of graphs, $(G_n \mid n\in I)$, where $G_n$ has order $n$, is a family of expanders, if there exists $\epsilon > 0$ such that all members of the family are $\epsilon$-expanders.
Of particular interest to the Theory of Computing are bounded-degree expanders. If these graphs are explicitly constructed, they are important derandomization tools.

18.45 THEOREM (Pinsker)   For every $d\ge 3$ there exists a family of degree-$d$ expanders. (These expanders are regular graphs of degree $d$.)
This result was proved in the 1970s by Mark Semënovich Pinsker, using the probabilistic method: we set up a model of "random $d$-regular graphs" and prove that almost all graphs in this model expand.

18.48 THEOREM (Margulis)   There exist explicit families of bounded-degree expanders.
This result was proved in the 1970s by Pinsker's colleague Grigory Aleksandrovich Margulis, Fields medalists and Abel prize laureate for his work on arithmetic subgroups of Lie groups. Margulis's construction is very simple and elegant, but the proof that it expands requires deep mathematics.
Many other constructions of explicit families of bouded-degree expanders followed, using more elementary but always nontrivial tools.

18.55 (eigenvalue gap)   We call the quantity $\lambda_1-\lambda_2$ the adjacency eigenvalue gap and $\kappa_1$ the Laplacian eigenvalue gap. A further important type of eigenvalue gap is $\lambda_1-\max(|\lambda_i|\,:\, i\ge 2)$. These eigenvalue gaps control the expansion rate. Below we state results, proved in class, that show that large eigenvalue gaps imply large expansion rates.

18.58 history   The relation of the quantity $\kappa_1$ to graph connectivity was first considered by Czech mathematician Miroslav Fiedler who named $\kappa_1$ the algebraic connectivity of the graph.

18.61 DO   If $G$ is regular then $\kappa_1=\lambda_1-\lambda_2$.

18.65 DO (edge expansion from Laplacian eigenvalue gap)   $$(\forall X\subseteq V, X\neq\emptyset)\left(\frac{|\delta X|}{|X|} \ge \kappa_1\cdot \frac{|\Xbar|}{n}\right).$$ In particular, if $|X|\le n/2$ then $|\delta X|/|X| \ge \kappa_1/2$.
The proof uses the Rayleigh quotient of $L$.

18.68 DO (vertex-expansion for regular graphs)   If $G$ is $d$-regular and $X\subseteq V$, $1\le |X|\le n/2$, then $$ \frac{|\partial X|}{|X|} \ge \frac{1}{2}\cdot\left(1-\frac{\lambda_2}{d}\right)\,.$$ This is an immediate consequence of the preceding result.

18.75 DEF Let $A\in\rrr^{r\times s}$. The operator norm of $A$ is defined as $$ \|A\| = \max_{\bfx\in\rrr^s\setminus\{0\}} \frac{\|A\bfx\|}{\|\bfx\|}\,.$$ (Here $\|\bfx\| = \sqrt{\bfx^T\bfx}$ denotes the Euclidean norm.)

18.78 DO   (a)   Let $A\in \rrr^{r\times s}$. Prove:   $\|A\|=\sqrt{\lambda_1(A^TA)}$, where $\lambda_1(B)$ denotes the largest eigenvalue of the symmetric real matrix $B$.
(b)   Let $A$ be a symmetric $n\times n$ real matrix with eigenvalues $\lambda_1\ge\dots\ge\lambda_n$. Then $\|A\|=\max(|\lambda_i|\,:\,1\le i\le n)\,.$

18.XX  

18.85 (Expander mixing lemma, Noga Alon and Fan R. K. Chung)   Let $G$ be a $d$-regular graph and let $\xi = \max(|\lambda_i|\,:\, i\ge 2)$. Let $X,Y\subseteq V$. Then $$ \left||E(X,Y)| - \frac{d}{n}\cdot |X|\cdot |Y|\right| \le \xi\sqrt{|X|\cdot |Y|}\,.$$ This means if $\frac{\xi}{d}$ is small compared to $\frac{\sqrt{|X|\cdot |Y|}}{n}$ then the density between $X$ and $Y$, $\frac{|E(X,Y)|}{|X|\cdot |Y|}$, is about the same as the overall density of the graph, $\frac{m}{\binom{n}{2}}$. Graphs that have this property for all $X,Y\subseteq V$ such that $|Y|,|Y|\ge \epsilon n$, are called quasirandom.

18.XX  

18.XX  

18.XX  

More to follow. Please check back later.

Material covered:   Strongly regular graphs. Hoffman--Singleton Theorem (proved). $k$-universal graphs, $k$-extendability. Erdős's probabilistic bound (stated). Paley graphs and Paley tournaments. Graham--Spencer Theorem: large enough Paley graphs $k$-extendable (stated). André Weil's character sum estimates.

Material covered:   Exercise 7.32 (BON05): deducing Hall's Marriage Theorem from Kőnig's Duality Theorem. Menger's Theorem: 4 versions stated (directed/undirected, edge/vertex connectivity versions), see Ex.15.126 and the sequence 15.100--15.145 below. Network flows, cuts, the Max-flow-min-cut theorem (Ford--Fulkerson 1956), proof: augmenting paths. Perfect graphs (Claude Berge 1954), Perfect graph theorem (László Lovász 1975) and Strong perfect graph theorem (Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas 2006) stated.

16.XX  

More to follow. Please check back later.

Material covered:   Comments on the solution to Exercise 05.109 (counting trees with prescribed degrees). Log-concave, strongly log-concave sequences. The coefficients of real-rooted polynomials are strongly log-concave (Newton). Generating function of counting random variables, their multiplicativity. Generating function of sum of independent 2-valued random variables is real-rooted with non-positive roots. The converse. Application to asymptotic normality of the coefficients of real-rooted polynomials with non-positive roots under certain conditions. Berry--Esséen Theorem. $k$-universal graphs.

15.20 DEF   The finite or infinite sequence $a_0,a_1,\dots$ of real numbers is unimodal if there exists $j$ such that $a_{i-1} \le a_i$ for $i\le j$ and $a_i\ge a_{i+1}$ for $i\ge j+1$.   Here we also permit $j=\infty$, meaning that the sequence is non-decreasing.
The sequence is strictly unimodal if there exists $j$ such that $a_{i-1} < a_i$ for $i\le j$ and $a_i > a_{i+1}$ for $i\ge j+1$.   The finite sequence $a_0,a_1,\dots,a_n$ of positive numbers is strongly unimodal if the sequence $\displaystyle{\left(\frac{a_k}{\binom{n}{k}}\,:\, 0\le k\le n\right)}$ is unimodal.
Updated May 17 at 22:10: the sentence "Here we also permit $j=\infty$ etc." was added.

15.23 DO   Prove that the sequence $\left(\binom{n}{k}\,:\, 0\le k\le n\right)$ is strictly unimodal.

15.26 DO   Prove that a strongly unimodal finite sequence of positive numbers is strictly unimodal.

15.30 DEF   The (finite or infinite) sequence $a_0,a_1,\dots$ of real numbers is log-concave if for all $i$ we have $a_{i-1}a_{i+1} \le a_i^2$. The sequence is strictly log-concave if for all $i$ we have $a_{i-1}a_{i+1} < a_i^2$. A finite sequence $a_0,a_1,\dots,a_n$ of real numbers is strongly log-concave if the sequence $\displaystyle{\left(\frac{a_k}{\binom{n}{k}}\,:\, 0\le k\le n\right)}$ is log-concave.

15.31 DO   Prove: the sequence $a_0,a_1,\dots, a_n$ of real numbers is strongly log-concave if and only if for all $i$ we have $a_{i-1}a_{i+1} \le \frac{i}{i+1}\cdot\frac{n-i}{n-i+1}\cdot a_i^2$.
(b) Every strongly log-concave sequence is log-concave.
(c) Every strongly log-concave sequence of non-zero real numbers is strictly log-concave.

15.32 ORD (7 points)   Prove that a log-concave sequence of positive numbers is unimodal.

15.34 DO   Prove: if $a_0,a_1,\dots$ is a finite or infinite log-concave sequence then there exist $j\le k$ such that $a_{i-1} < a_i$ for all $i\le j$, then $a_{i-1} = a_i$ for $j < i \le k$ (we call this segment, $a_j=\dots = a_k$, consisting of $k-j+1$ terms, the plateau), and $a_i > a_{i+1}$ for $i\ge k$. Moreover, if the sequence is strictly log-concave then the plateau cannot have more than two terms of the sequence, i.e., $k\le j+1$.

15.36 DO   Prove: If the finite sequence $a_0,\dots,a_n$ of positive numbers is strongly log-concave then it is strongly unimodal.

15.40 Bonus (12 points)   Let $f(x)=a_0+a_1x+\dots+a_n x^n =\prod_{i=1}^n (x+\alpha_i)$ where $\alpha_i\ge 0$. (So this is a real-rooted polynomial where all roots are non-positive.) Prove that the sequence $a_0,a_1,\dots,a_n$ is strongly log-concave. Follow the strategy described in class.
Update, May 15, 19:20. The condition of non-positivity is not needed, and indeed the same strategy proves the result if we permit positive roots. (However, unimodality of the coefficients no longer follows, but this is another issue.)

15.44 ORD (9 points)   Let $m_k$ denote the number of $k$-matchings in the graph $G$ (see notation 12.40). Prove that the sequence $(m_k \mid 0\le k\le \nu(G))$ is strongly log-concave.

15.48 DEF   Let $X$ be a random variable. We shall say that $X$ is a counting variable if range$(X) \subset \nnn_0$. In other words, $X$ takes non-negative integer values.
This is not standard terminology. The explanation of the term is that we typically encounter such variables when the variable counts certain events, such as the number of Heads in a sequence of coin flips or the number of Kings in a poker hand.

15.50 DEF   Let $X$ be a counting random variable. The generating function of $X$ is the polynomial $f_X(t) = \sum_{k\in\nnn_0} P(X=k)t^k$.

15.52 DO   Observe that $f_X(1) = 1$.

15.54 ORD (6 points)   Observe that $f_X'(1)$ is an important parameter of $X$. What is it? (Here $f_X'$ is the derivative of $f_X$.)

15.56 ORD (10 points)   Express $\var(X)$ as a closed-form expression in terms of $f_X(1)$, $f_X'(1)$, and $f_X''(1)$. Make your expression simple.

15.58 DO   Let $c\in\nnn$ be a positive integer. Prove:   $f_{cX}(t) = f_X(t^c)$.

15.62 ORD (8 points)   Prove: If $X$ and $Y$ are independent counting variables then $f_{X+Y} = f_X\cdot f_Y$.

15.65 Bonus (14 points)   Show that the converse is false. Find a probability space and counting random variables $X, Y$ such that $f_{X+Y} = f_Xf_Y$ but $X,Y$ are not independent. State the size of your sample space; make it as small as you can. Label the elements of your sample space $1,\dots,n$ and define your random variables as explicit functions whose domain is the sample space. You do not need to prove that your sample space is smallest possible.
Updated May 14, 23:40. The claim that the example should be uncorrelated turned out to be false and was removed. (See 15.69.)

15.67 Challenge   Find the smallest possible sample space for the preceding problem; prove that it is smallest possible.

15.69 Challenge (William Spencer)   Prove: If $X$ and $Y$ are counting variables and $f_{X+Y} = f_X\cdot f_Y$ then $X$ and $Y$ are uncorrelated.

15.71 DO   Observe that if $\alpha$ is a real root of $f_X$ then $\alpha \le 0$.

15.78 ORD (9 points)   Recall that a random variable $Z$ is an indicator variable if range$(Z)\subseteq \{0,1\}$. Let $X_1,\dots, X_k$ be independent indicator variables. Let $Y = \sum_{i=1}^k X_i$. Prove that $f_Y$ is real-rooted. What are its roots?

15.81 Bonus (14 points) (the converse of the preceding exercise)   Let $g(t)= d_0+d_1t+\dots+d_kt^k$ be a real-rooted polynomial with non-negative coefficients; assume $d_k$ is positive. Prove that there exists a probability space and independent indicator variables $X_1,\dots,X_k$ such that $\displaystyle{\frac{g(t)}{g(1)}=f_Y(t)}$ where $Y = \sum_{i=1}^k X_i$. State $E(X_i)$ in terms of the roots $\lambda_i$ of $g$. State the size of your sample space.

15.83 Challenge   Let $(g_k \mid k\in\nnn_0)$ be a sequence of polynomials as in the previous exercise, one polynomial for each $k$, so $\deg(g_k)=k$. Let $X_{ik}$ $(i=1,\dots,k)$ denote the random variables corresponding to $g_k$ as in the previous exercise, and let $Y_k = \sum_{i=1}^k X_{ik}$. Assume the roots of the polynomials $g_k$ are bounded and bounded away from zero (share common bounds). Prove that the variables $Y_k$ are asymptotically normally distributed. Use the Berry--Esséen Theorem (see Wikipedia).
Updated May 20 at 13:00. Added condition that that the roots are bounded away from zero.

15.100 DEF   In a graph or digraph, two paths connecting vertices $u$ and $v$ are internally disjoint if they do not share any vertices other than $u$ and $v$. We say that two $u-v$ paths are edge-disjoint if they do not share any edges.

15.103 DEF   Let $s$ and $t$ be two distinct vertices of the graph or digraph $G$. We say that the $s-t$-vertex-connectivity of $G$ is $k$ if $k$ is the maximum number of internally disjoint paths from $s$ to $t$ is $k$. In the case of a digraph, here we speak of directed paths, directed from $s$ to $t$. This value $k$ is denoted $\kappa(G;s,t)$. ($\kappa$ is the l.c. Greek letter kappa, denoted \kappa in LaTeX.)
Updated May 13, 15:35: the previous version said "directed paths, oriented from $s$ to $t$." The term "oriented" gave rise to a potential misunderstanding.

15.106 DEF   Let $s$ and $t$ be two distinct vertices of the graph or digraph $G$. We say that the $s-t$-edge-connectivity of $G$ is $\ell$ if $\ell$ is the maximum number of edge-disjoint paths from $s$ to $t$. In the case of a digraph, here we speak of directed paths, directed from $s$ to $t$. This value $\ell$ is denoted $\lambda(G;s,t)$.
Updated May 14 at 1pm: originally, both $k$ and $\ell$ were used to denote the $s-t$-edge-connectivity. This notational confusion has now been eliminated. Also, the expression "directed paths, oriented from $s$ to $t$" has been replaced by "directed path, directed from $s$ to $t$" to avoid a potential misunderstanding.

15.109 DO   Let $s$ and $t$ be two distinct vertices of the graph or a digraph $G$. Prove:   $\kappa(G;s,t)\le \lambda(G;s,t)$.

15.111 ORD (8 points)   Find a connected graph $G$ and two distinct vertices, $s$ and $t$, such that $\kappa(G;s,t)=1$ and $\lambda(G;s,t)= 100$. Make your graph as small as you can; state its order and size.

15.114 DO   Let $s,t$ be two distinct vertices of the graph $G$. Verify:   (a)   if $G=K_n$ then $\kappa(G;s,t)=n-1$   (b)   if $G=C_n$ then $\kappa(G;s,t)=2$.   (c)   determine the possible values of $\kappa(G;s,t)$ if $G=K_{k,\ell}$.
Updated May 15, 2:50: fixed typo in part (c).

15.XX  

15.120 DEF   Let $G=(V,E)$ be a graph or digraph and let $s,t\in V$ be distinct vertices. An $s-t$ vertex cut is a set $C\subseteq (V\setminus\{s,t\})\cup E$ such that every $s-t$ path includes some element of $C$. An $s-t$ edge cut is a set $D\subseteq E$ such that every $s-t$ path includes some element of $D$.

15.123 DO   Let $G$ be a graph or digraph and $s,t$ two distinct vertices. Prove:   (a)   $\kappa(G;s,t) \le \min\{|C|\,:\, C$ is an $s-t$ vertex cut$\}$ and $\lambda(G;s,t) \le \min\{|D|\,:\, D$ is an $s-t$ edge cut$\}$.

15.126 MENGER'S THEOREM (Karl Menger, 1928)     Let $G$ be (a) a directed or (b) an undirected graph and $s,t$ two distinct vertices. Then
  (1) $\lambda(G;s,t)= \min\{|D|\,:\, D$ is an $s-t$ edge cut$\}$.
  (2) $\kappa(G;s,t)= \min\{|C|\,:\, C$ is an $s-t$ vertex cut$\}$.

15.130 ORD (12 points)   Use the directed vertex version of Menger's Theorem (version (a2)) to prove Kőnig's Duality Theorem ($\tau = \nu$ for bipartite graphs).

15.135 Bonus (16 points)   Deduce version (a2) (directed vertex version) of Menger's Theorem from version (a1) (directed edge version).

15.140 Bonus (14 points)   Deduce version (b1) (undirected edge version) of Menger's Theorem from version (a1) (directed edge version). Make it clear in every statement whether you are talking about a graph or a digraph. Remember that in a digraph, an edge is an odered pair $(u,v)$, and in an undirected graph an edge is an unordered pair $\{u,v\}$. You can also talk about a $u\to v$ edge in the directed case, and a $u-v$ edge in the undirected case. Avoid the ambiguous term "vertices $u$ and $v$ are connected" and say "vertices $u$ and $v$ are adjacent" in the undirected case; and "vertex $u$ is adjacent to vertex $v$" if there is a $u\to v$ edge. You can also say "there is an edge from $u$ to $v$" both in the directed and in the undirected case.

15.145 ORD (14 points)   Deduce version (b2) (undirected vertex version) of Menger's Theorem from version (a2) (directed vertex version). Make it clear in every statement whether you are talking about a graph or a digraph. Read the caveats in the preceding exercise.

15.XX  

15.XX  

More to follow. Please check back later.

Material covered:   Solution to Exercise 02.28 ($\gcd$ of Fibonacci numbers).   Abigail Ward's proof that orthogonal polynomials are real-rooted with no multiple roots and interlace (see handout below, Ex. 14.35).   Hao Huang's spectral lower bound on the max-degree of induced subgraphs of the $d$-cube (full proof).

14.20 DO (generating the Fibonacci numbers) (solution to Exercise 02.20).   Consider the matrix   $A= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \,.$   Prove: $$A^k= \begin{pmatrix} F_{k+1} & F_k \\ F_k & F_{k-1} \end{pmatrix} \,.$$

14.24 DO (Fibonacci number identity)   Prove:   $F_{k+\ell}=F_{k+1}F_{\ell}+ F_kF_{\ell-1}$.
Hint for elegant proof:   Consider the identity $A^{k+\ell} = A^k\cdot A^{\ell}$ where $A$ is the $2\times 2$ matrix defined in 14.20. Compare the top right entries on both sides.

14.28 DO (gcd of Fibonacci numbers)   Let $d=\gcd(k,\ell)$. Prove:   $\gcd(F_k,F_{\ell})=F_d$.
Use Exercise 14.24 and the following facts.   (1)   (Euclid) for all pairs $(a,b)$ of integers, $\gcd(a,b)=\gcd(a-b,b)$   (2)   $\gcd(F_n,F_{n+1})=1$ (proof by easy induction).

Material covered:   Max number of edges of $C_4$-free graphs. Chromatic polynomial is a polynomial: two proofs. The contraction-deletion recurrence. Orthogonal polynomials: using the 3-term recurrence to prove real-rootedness and interlacing. Adapting this proof to the matchings polynomials. Significance of real-rootedness.

13.20 DO   Recall: if the graph $G$ contains no $K_{2,2}$ then $m=O(n^{3/2})$ (Ex. 02.130) (note that $K_{2,2}=C_4$). This is the simplest case of the Kővári--Sós--Turán Theorem. Review the proof given in class today.

13.23 Bonus (15 points) Kővári--Sós--Turán Theorem (1954), next case.   Let $G$ be a graph with no $K_{3,3}$ subgraphs. Prove:   $m=O(n^{5/3})$. (DO NOT LOOK IT UP.) State the smallest constant your proof gives. Elegance counts.

13.26 DEF   Let $V$ be a finite subset of $\rrr^2$. The unit-distance graph on $V$ is the graph $G=(V,E)$ where two points are adjacent if their (Euclidean) distance is 1. We say that $G$ is a unit-distance graph in the plane if there exists a finite set $V\subseteq \rrr^2$ such that $G$ is the unit-distance graph on $V$.

13.29 DO   Let $G$ be a unit-distance graph in the plane. Prove:   $G$ does not contain a $K_{2,3}$ subgraph.

13.32 Bonus (15 points)   Prove: every unit-distance graph in the plane satisfies $m=O(n^{3/2})$.

13.34 Comment.   This bound is not optimal. The best bound known is $O(n^{4/3})$. Erdős (1946) gave a lower bound of the form $n^{1+c/\log\log n}$ and conjectured that this bound is tight, except for the value of the positive constant $c$. For references, see the Wikipedia entry "Unit distance graph."

13.37 Reward   Let $G$ be a unit-distance graph in the plane. Prove:   $\chi(G)\le 7$.

13.40 ORD (12 points)   Prove: not all unit-distance graphs in the plane are 3-colorable. Make the number of vertices of your example as small as you can.

Material covered:   Hermite polynomials. The matchings polynomials. 3-term recurrence for matchings polynomials.

12.20 DEF (Hermite polynomials)   The Hermite polynomials (discovered by Laplace in 1810 and studied by Chebyshev in 1859 before Hermite wrote about them in 1864) are defined as $$ He_n(t) = (-1)^n \eee^{t^2/2}\frac{d^n}{dt^n} \eee^{-t^2/2} \,.$$

12.23 DO   The Hermite polynomials are orthonogal (Def 8.30) with respect to the weight function $w(t) = \eee^{-t^2/2}$. Prove that $w$ is indeed a weight function in the sense of Def. 8.25.

12.25 DO   The first few Hermite polynomials are
  $He_0(t) = 1$
  $He_1(t) = t$
  $He_2(t) = t^2-1$
  $He_3(t) = t^3-3t$
  $He_4(t) = t^4-6t^2+3$
  $He_5(t) = t^5-10t^3+15t$

12.28 DO (3-term recurrence for the Hermite polynomials)   $$ He_n(t) = t\cdot He_{n-1}(t) - (n-1)\cdot He_{n-2}(t)\,.$$

12.40 Notation (number of $k$-matchings)   For a graph $G$, let $m_k(G)$ denote the number of $k$-matchings, i.e., matchngs of $G$ consisting of $k$ disjoint edges.
So $m_0(G)=1$ and $m_1 =m$. The largest $k$ for which $m_k\neq 0$ is is $k=\nu(G)$,the matching number. For even $n$, the number $m_{n/2}$ counts perfect matchings.

Notation 12.43 (Matching generator function)   $m_G(t) = \sum_{i=0}^{\nu(G)} m_i(G)t^i$.

The central result of the theory of this function was discovered in 1972 by statistical physicists Ole Heilmann and Elliot H. Lieb and published in their paper titled “The theory of monomer-dimer systems.”

12.50 Theorem (Heilmann and Lieb, 1972). The matching generator function is real-rooted.

The reality of these roots is at the heart of Heilmann and Lieb’s proof of the absence of phase transitions in the physical systems named in the title of their paper.

For reasons that will soon become evident, a variant of this generating function is the preferred object of study.

12.60 DEF   The matchings polynomial of the graph $G$ is the polynomial $\mu(G,t) = \sum_{k=0}^{\nu(G)} (−1)^k m_k t^{n−2k} = t^n − m_1 t^{n−2} + m_2 t^{n−4} − \dots$.

12.62 DEF (reciprocal polynomial)   Let $f(x)=a_0+a_1x+\dots+a_nx^n$ be a polynomial of degree $n$. (So $a_n\neq 0$.) Assume $a_0\neq 0$. Define the polynomial $f^*(x) = a_n+a_{n-1}x+\dots+a_0x^n = x^n f(1/x)$ (the coefficients come in reverse order). $f^*$ is called the reciprocal polynomial of $f$.

12.64 DO   If the roots of $f$ are $\lambda_1,\dots,\lambda_n$ then the roots of $f^*$ are $1/\lambda_1,\dots,1/\lambda_n$. (Note that $\lambda_i\neq 0$ because $a_0\neq 0$ and $\deg(f^*)=n$ for the same reason.)

12.67 DO (connection between the matchings polynomial and the matching generator function)   Prove: $$\mu(G,t) = (-1)^{\nu(G)}t^{n-2\nu(G)} m_G^*(-t^2)\,,$$ where $m_G^*$ is the reciprocal polynomial of $m_G$.
Updated May 17 at 9:10: factor $(-1)^{\nu(G)}$ was missing.
Updated May 3 at 18:55: factor 2 was missing from the exponent $n-2\nu(G)$.

12.70 ORD (8 points)   Prove: $m_G(t)$ is real-rooted if and only if $\mu(G,x)$ is real-rooted. (Do not use Theorem 12.50.)

12.73 DO (recurrence for matching counting numbers)   Let $G$ be a graph and $u$ a vertex of $G$. Prove: for $k\ge 1$ we have   $$m_k(G) = m_k(G-u) + \sum_{v\sim u} m_{k-1}(G-u-v)$$ where $G-u$ denotes the induced subgraph $G[V\setminus\{u\}]$ and $G-u-v := (G-u)-v = G[V\setminus\{u,v\}]$.

12.76 Bonus (9 points, due May 15) (3-term recurrence for matchings polynomials)   Let $G$ be a graph and $u$ a vertex. Prove: $$ \mu(G,x) = x\cdot\mu(G-u,x) - \sum_{v\sim u} \mu(G-u-v,x)\,.$$

12.80 ORD (11 points)   Prove:   If $G$ is a forest (cycle-free graph) then $\mu(G,t) = f_G(t)$ where $f_G$ is the characteristic polynomial of the adjacency matrix of $G$.

12.82 DO   Prove:   $\mu(P_n,t) = U_n(t/2)$. where $U_n$ denotes the degree-$n$ Chebyshev polynomial of the second kind.

12.85 ORD (11 points)   Prove:   $\mu(C_n,t) = 2\cdot T_n(t/2)$ where $T_n$ denotes the degree-$n$ Chebyshev polynomial of the first kind.
Updated May 5 at 18:30. The right-hand sides of 12.82 and 12.84 were switched.

12.88 ORD (11 points)   Prove:   $\mu(K_n,t) = He_n(t)$.

More to follow. Please check back later.

Material covered:   Spectrum of circulant matrices. Spectrum of cycles. Chebyshev polynomials of the first and second kind. 3-term recurrence. Roots. Orthogonality. Recurrence for the characteristic polynomial of a graph with a vertex of degree 1. The characteristic polynomials of paths are scaled Chebyshev polynomials.

11.10 STUDY   the Chebyshev polynomials on Wikipedia.

11.15 DEF   The Chebyshev polynomials of the first kind are defined by the identity   $T_n(\cos \vt)=\cos(n\vt)$.

11.18 DO   Prove, using high school trigonometry:   $T_0(x)=1$,   $T_1(x)=x$,   $T_2(x)=2x^2-1$,   $T_3(x) = 4x^3-3x$.   Verify, using the recurrence below:   $T_4(x)=8x^4-8x^2+1$,   $T_5(x)=16x^5-20x^3+5x$.

11.21 DO (Chebyshev recurrence)   Prove:   For $n\ge 2$ we have   $$T_n(x) = 2x\cdot T_{n-1}(x)-T_{n-2}(x)\,.$$ Use only the addition rules of the cosine function:   $\cos(\alpha+\beta)=\cos(\alpha)\cos(\beta)-\sin(\alpha)\sin(\beta)$ and $\cos(\alpha-\beta)=\cos(\alpha)\cos(\beta)+\sin(\alpha)\sin(\beta)$.

11.25 DO   Prove that the roots of $T_n$ are $x_k = \cos\frac{(2k-1)\pi}{2n}$ for $k\in [n]$. Show that all roots are distinct.

11.28 DO   Show that $T_n$ and $T_{n-1}$ strictly interlace (see Def 4.60).

11.31 DO (extrema)   (a)   Prove that the maximum value of $T_n(x)$ on the interval $-1\le x\le 1$ is $1$ and it is attained at $x_k = \cos(2k\pi/n)$ for $0\le k\le n/2$.   (b)   Prove that the minimum value of $T_n(x)$ on the interval $-1\le x\le 1$ is $-1$ and it is attained at $x_k = (2k-1)\pi/n$ for $1\le k\le (n-1)/2$.

11.40 DEF   The Chebyshev polynomials of the second kind are defined by the identity   $\displaystyle{U_n(\cos \vt)=\frac{\sin((n+1)\vt)}{\sin(\vt)}}$.

11.43 DO   Prove, using high school trigonometry:   $U_0(x)=1$,   $U_1(x)=2x$,   $U_2(x)=4x^2-1$.   Verify, using the recurrence below:   $U_3(x) = 8x^3-4x$,   $U_4(x)=16x^4-12x^2+1$,   $U_5(x)=32x^5-32x^3+6x$.

11.46 ORD (4+7 points)   Calculate   (a)   $T_n(1)$   and   (b)   $U_n(1)$.
Your answers should be a very simple closed-form expression. Use the definitions of $T_n(x)$ and $U_n(x)$ only; do not use the recurrence below.

11.50 ORD (7 points)   Prove the recurrence: for $n\ge 2$ we have $$ U_n(x) = 2x\cdot U_{n-1}(x) - U_{n-2}(x)\,.$$ Note that this is identical with the recurrence for $T_n(x)$. Use only the addition formulas for the sine function: $\sin(\alpha+\beta)=\sin(\alpha)\cos(\beta)+\cos(\alpha)\sin(\beta)$ and $\sin(\alpha-\beta)=\sin(\alpha)\cos(\beta)-\cos(\alpha)\sin(\beta)$.

11.53 DO   Prove that the roots of $U_n$ are $x_k = \displaystyle{\cos\frac{k\pi}{n+1}}$ for $k\in [n]$.

11.56 DO (extrema)   Prove that the local extrema (maxima and minima) of $U_n(x)$ on the interval $-1\le x\le 1$ occur at $x_k = \cos(k\pi/n)$.

11.58 Bonus (10 points, due May 8)   Prove:   $U_n(3/2)$ is a Fibonacci number. Which one?

11.61 DO (spectrum of graph with vertex of degree 1)   Let $f_G(t)$ denote the charactistic polynomial of the adjacency matrix of the graph $G$. Assume $u$ is a vertex of degree $1$ in $G$ and $v$ is its sole neighbor. Prove: $$ f_G(t) = t\cdot f_{G-u}(t) - f_{G-u-v}(t)\,,$$ where $G-u$ denotes the subgraph induced on $V(G)\setminus\{u\}$ and $G-u-v$ denotes the subgraph induced on $V(G)\setminus\{u,v\}$.

11.64 ORD (5+5+5+5 points)   (a) State and prove a recurrence for $f_{P_n}(t)$.   (b)   State $f_{P_0}(t)$ and $f_{P_1}(t)$. Your value for $f_{P_0}$ should be consistent with the recurrence. Argue why this is also consistent with the definition of the determinant.   (c)   Prove:   $f_{P_n}(t) = U_n(t/2)$.   (d)   Determine the spectrum of $P_n$. You need to state $n$ distinct values.

11.XX  

11.XX  

11.XX  

More to follow. Please check back later.

Material covered:   Erdős's proof that small triangle-free graphs of large chromatic number exist.

Material covered:   Random graphs, the Erdős--Rényi $\bfG(n,p)$ model. Meaning of the phrase "almost all graphs" and "with high probability" (whp). Upper bound on the independence number of graphs in the $\bfG(n,p)$ model whp. Erdős's exponential lower bound on the diagonal Ramsey numbers.

Material covered:   Finite Probability Spaces. Added exercises not covered in class: orthogonal polynomials and additonal exercises in spectral graph theory, chromatic graph theory, and extremal graph theory.

08.10 REVIEW/STUDY   PROB (Finite Probability Spaces):  Review all chapters previously assigned in 05.10; study all remaining chapters.

08.22 ORD (8 points)   Let $f\in\ccc[t]$ be a polynomial with complex coefficients. We say that $\lambda\in\ccc$ is a multiple root of $f$ if $(t-\lambda)^2 \mid f(t)$. Prove: $\lambda\in\ccc$ is a multipe root of $f$ if and only if $f(\lambda)=f'(\lambda)=0$.   ($f'$ denotes the derivative of $f$.)

08.25 DEF (weight functions)   We say that the real function $w: \rrr\to\rrr$ is a weight function on $\rrr$ if it satisfies the following conditions.
  (i)   $w$ is Lebesgue measurable. (If you are not familiar with this concept, just assume $w$ is piecewise continuous, i.e., there is a finite set of real numbers, $a_1 < a_2 <\dots < a_k$, such that $w$ is continuous on each open interval $(a_{i-1},a_i)$ for $i=0,1,\dots,k+1$, where $a_0=-\infty$ and $a_{k+1}=\infty$.)
  (ii)   $w(t)\ge 0$ for all $t\in\rrr$
  (iii)   $\int_{-\infty}^{\infty} w(t)\,dt > 0$
  (iv)   $(\forall k\in \nnn)( \int_{-\infty}^{\infty} t^{2k}w(t)\,dt < \infty)\,.$

08.27 DO (examples of weight functions)   Prove that the following functions are weight functions in the sense of Def 08.25.
  (a)   $w(t)=1$ for $|t| < 1$ and $w(t)=0$ for $|t| \ge 1$.
  (b)   (Chebyshev 2)   $w(t)=\sqrt{1-t^2}$ for $|t| < 1$ and $w(t)=0$ for $|t| \ge 1$.
  (c)   (Chebyshev 1)   $\displaystyle{w(t)=\frac{1}{\sqrt{1-t^2}}}$ for $|t| < 1$ and $w(t)=0$ for $|t| \ge 1$.
  (d)   (Hermite)   $w(t) = \eee^{-t^2/2}$   (the bell curve)

08.29 NOTATION   $\rrr[t]$ denotes the space of polynomials in the variable $t$ with real coefficients. This is an infinite-dimensional vector space with basis $1,t,t^2,\dots$.

08.30 DEF (inner products for polynomials)   Let $w$ be a weight function. We define the inner product of the polynomials $f,g\in\rrr[t]$ with respect to $w$ by $$\langle f,g\rangle = \int_{-\infty}^{\infty} f(t)g(t)w(t)\,dt\,.$$ We say that the polynomials $f,g$ are orthogonal (with respect to this inner product) if $\langle f,g\rangle = 0\,.$

08.32 DO   Prove that the formula given in 8.30 defines a positive definite inner product on $\rrr[t]$ (see LinAlg Def 19.1).

In the following sequence of exercises we fix a weight function $w$ and consider the inner product on $\rrr[t]$ with repsect to this weight function.

08.35 Bonus (Abigail Ward's lemma) (20 points, due May 1)   Let $f\in\rrr[t]$ be a polynomial of degree $n\ge 1$. Prove: if $f$ is orthogonal to all polynomials of degree $\le n-2$ then $f$ has $n$ distinct real roots. (Recall that the degree of the zero polynomial is $-\infty$.)
Note.   Although this result has probably been known since the 19th century, I learned it in 2015 from Abigail Ward, then a UChicago senior who was one of my TAs for an REU course. She discovered this result and used it as a lemma to an unusual and suprisingly elegant proof for the problem I had assigned, the real-rootedness and interlacing property of orthogonal polynomials (see below), to which luckily no hint was provided (luckily because my hint would have suggested a more common, and less elegant, proof). The following sequence of exercises follows Ward's proof.

08.40 DO   Let $f_0,f_1,f_2,\dots$ be a sequence of real polynomials ($f_n\in\rrr[t]$) such that   $(\forall n\in\nnn_0)(\deg(f_n)=n)$. Prove that the $f_n$ a basis of $\rrr[t]$.

08.43 DEF (orthogonal polynomials)   Let $f_0,f_1,f_2,\dots$ be a sequence of real polynomials ($f_n\in\rrr[t]$). We say that the $f_n$ form a sequence of orthogonal polynomials if
  (a)   $(\forall n\in\nnn_0)(\deg(f_n)=n)$   (recall that we denoted the set of non-negative integers by $\nnn_0$) and
  (b)   $(\forall k,\ell\in\nnn_0)(k\neq\ell\Rightarrow \langle f_k,f_{\ell}\rangle = 0)$.

08.45 DO   Prove: given the weight function $w$, there exists a sequence of orthogonal polynomials, and this sequence is unique up to scaling (i.e., we can replace $f_n$ only by $c_nf_n$ for some $c_n\neq 0$).
Hint.   For the proof of existence, apply Gram--Schmidt orthogonalization to the sequence $1,t,t^2,\dots$, the standard basis of $\rrr[t]$.

08.48 ORD (8+3 points) (real-rootedness of orthogonal polynomials)   Let $(f_n\mid n\in \nnn_0)$ be a sequence of orthogonal polynomials. For all $n\in\nnn_0$, prove:   (a)   for any scalar $c\in\rrr$, the polynomial $f_{n+1}-cf_n$ has $n+1$ distinct real roots   (b)   $f_n$ has $n$ distinct real roots.

08.52 Bonus (15 points, due May 1)   Let $(f_n\mid n\in \nnn_0)$ be a sequence of orthogonal polynomials. For all $n\in\nnn_0$, prove that $f_{n+1}$ and $f_n$ are relatively prime (they have no common root).

08.55 Challenge (expires on May 1) (interlacing property of orthogonal polynomials)   Let $(f_n\mid n\in \nnn_0)$ be a sequence of orthogonal polynomials. For all $n\in\nnn_0$, prove that the roots of $f_{n+1}$ and $f_n$ interlace. Use the preceding exercises; do not use the "3-term recurrence".

08.XX  

08.60 DEF   Let $a_1,\dots,a_n\in\rrr$. The arithmetic mean of the $a_i$ is $$A(a_1,\dots,a_n):=\frac{\sum_{i=1}^n a_i}{n}\,.$$ The quadratic mean of the $a_i$ is $$Q(a_1,\dots,a_n):=\sqrt{A(a_1^2,\dots,a_n^2)}= \sqrt{\frac{\sum_{i=1}^n a_i^2}{n}}\,.$$ If all the $a_i$ are non-negative then the geometric mean of the $a_i$ is $$G(a_1,\dots,a_n):=\left(\prod_{i=1}^n a_i\right)^{1/n}\,.$$ If all the $a_i$ are positive then the harmonic mean of the $a_i$ is $$H(a_1,\dots,a_n):=\frac{1}{A(1/a_1,\dots,1/a_n)}=\frac{n}{\frac{1}{a_1}+ \dots + \frac{1}{a_n}}\,.$$

08.62 DO   (a)   Prove: $$\min a_i \le H(a_1,\dots,a_n)\le G(a_1,\dots,a_n)\le A(a_1,\dots,a_n) \le Q(a_1,\dots,a_n)\le \max a_i\,$$ where for each inequality make the assumption that both sides are defined.   (b)   Assume all $a_i$ are positive. Prove that in each of these inequalities, equality holds if and only if $a_1=\dots=a_n$.

08.66 ORD (7 points) (rational roots)   Let $f(t)=a_0+a_1t+\dots+a_nt^n$ be a polynomial with integer coefficients. Assume $a_0a_n\neq 0$. Let $p,q$ be relatively prime integers ($\gcd(p,q)=1$) and $q\neq 0$. Prove: if   $\displaystyle{f\left(\frac{p}{q}\right)=0}$   then   $p\mid a_0$ and $q\mid a_n$.

In the following sequence of exercises, $G$ is a graph with eigenvalues $\lambda_1\ge\lambda_2\ge \dots \ge \lambda_n$ and degrees $d_1,\dots,d_n$.

08.68 ORD (8 points)   Prove: if $G$ is not empty then   $\lambda_n \le -1$.

08.70 Bonus (13 points)   We have seen that $\lambda_1\ge A(d_1,\dots,d_n)$. Strengthen this lower bound: prove that   $\lambda_1\ge Q(d_1,\dots,d_n)$.

08.74 ORD (Herbert Wilf) (9 points)   Prove:   $\chi(G) \le 1+\lambda_1$.   DO NOT LOOK IT UP.

08.78 Challenge (Alan J. Hoffmann)   Assume $G$ is not empty. Prove:   $\chi(G) \ge 1-\frac{\lambda_1}{\lambda_n}$.

08.82 Bonus (12+12 points, due May 1)   (a)   Let $n=2^d$ and let $A=(a_{ij})$ denote the adjacency matrix of $Q_d$, the $d$-dimensional cube. Find a real symmetric $n\times n$ matrix $B=(b_{ij})$ such that $(\forall i,j\in [n])(|b_{ij}|=a_{ij})$ and $B^2 = dI$.   (b)   Let $S$ be subset of the set of vertices of $Q_d$ such that $|S|=n/2+1$. Consider the induced subgraph $Y:=Q_d[S]$. Prove:   $\deg_{\max}(Y) \ge \sqrt{d}$.
This exercise cancels Challenge problem 02.63. DO NOT LOOK IT UP.

08.86 Bonus (14 points)   Prove: if $G$ does not contain $C_5$ then $\chi(G) = O(\sqrt{n})$.

08.90 DEF (chromatic polynomial, George David Birkhoff, 1912) Let $G$ be a graph. For $x\in \nnn_0$, let $P_G(x)$ denote the number of legal colorings of $G$ using $[x]$ as a set of permitted colors. (We are not required to use all the $x$ colors.) This function is called the chromatic polynomial of $G$ for a reason to be clarified in a moment.
Examples:  the chromatic polynomial of the empty graph is $P_{\Kbar_n}(x)=x^n$.   The chromatic polynomial of the clique is $P_{K_n}(x)=x(x-1)\dots (x-n+1)$.

08.93 ORD (6 points)   Let $T$ be a tree of order $n$. Determine $P_T(x)$. Your answer should be a very simple closed-form expression.

08.96 Bonus (12 points)   Prove: for every graph $G$, the function $P_G(x)$ is a monic polynomial of degree $n$ in the variable $x$.
("Monic" means its leading coefficient is 1.)   DO NOT LOOK IT UP.

08.99 STUDY   the "Greedy coloring" handout (go to the course homepage, click "Text, online source" on the banner, then scroll down to "Handouts" and click "Greedy coloring."

08.101 DO   Solve problems (a) and (c) from the "Greedy coloring" handout ("Greedy coloring is not so bad" and "Greedy coloring can be optimal").

08.103 ORD (6 points)   Solve problem (b) from the "Greedy coloring" handout ("Greedy coloring is terrible")

08.106 Challenge (Tamás Kővári--Vera T. Sós--Paul Turán, 1954, see 02.130)   Prove: for every bipartite graph $H$ there exists $c > 0$ such that if $G$ does not contain any subgraph isomorphic to $H$ then $m = O(n^{2-c})$. Here $n$ is the number of vertices of $G$ and $m$ is the number of edges of $G$. The constant hidden in the big-Oh notation must only depend on $H$. State the value of $c$ you get; make it as large as you can.

Material covered:   Mycielski's graphs (1955) constructed (triangle-free graphs of high chromatic number), graphs of large chromatic number and large girth (Erdős 1959) (stated), Hall's Marriage Theorem, perfect matching, $k$-factor, $s$-$t$ connectivity (vertex/edge), Menger's Theorems (stated), regular bipartite graph 1-factorable (Kőnig 1916), $K_n$ 1-factorable for even $n$, edge-coloring (Tait coloring), chromatic index, Vizing's Theorem (stated)

07.10 DO (Mycielski's graphs, 1955)   (a)   Given a triangle-free graph $G$ with $n$ vertices, construct a triangle-free graph $G'$ with $2n+1$ vertices such that $\chi(G')=\chi(G)+1$.
If you have difficulty constructing $G'$, look up the entry "Mycielskian" in Wikipedia. Read the construction only, and give your own proof that the chromatic number grows.   (b)   Define Mycielski's graphs $M_k$ recurively as follows: let $M_2 = K_2$ and for $k\ge 3$, let $M_k=M_{k-1}'$. Check that $M_3=C_5$ and $M_4$ is Grötzsch's graph with 11 vertices, constructed in 02.73. Observe, by induction, that $M_k$ is triangle-free and $\chi(M_k)=k$.   (c)   Let $n_k$ denote the number of vertices of $M_k$. So $n_2=2$ and for $k\ge 3$ we have $n_k=1+2n_{k-1}$. Prove:   $n_k = 3\cdot 2^{k-2}-1.$

07.13 THEOREM (Erdős, 1959)   There exists $C$ such that for every $k\ge 2$ there exists a triangle-free $k$-chromatic graph with at most $k^C$ vertices.
Note.   Observe that the order of Mycielski's graphs grows exponentially as a function of the target chromatic number. Erdős's result shows that polynomial growth suffices. However, Erdős's proof is a probabilistic proof of existence, he did not construct such graphs. An explicit construction was found by Margulis and by Lubotzky--Phillips--Sarnak in 1988; their graphs are called "Ramanujan graphs" which we shall discuss later. They are defined by a spectral inequality.

07.16 THEOREM (graphs with large chromatic number and large girth, Erdős, 1959)   For every $g$ and $k$ there exists a graph of girth $\ge g$ and chromatic number $\ge k$.  

07.20 TERMINOLOGY   Let $G$ be a bipartite graph with $V_1$ and $V_2$ the two parts of the vertex set. Let $M$ be a matching in $G$. We say that a set $W\subseteq V_1$ is matched by $M$ if each element of $W$ is incident with some edge in $M$. We say that $W$ can be matched if there exists a matching $M$ such that $W$ is matched by $M$.
Updated April 23 at 0:59. Typo: "each element of $V_1$ matched" $\to$ "each element of $W$ matched".

07.22 NOTATION   Let $G=(V,E)$ be a graph and let $W\subseteq V$. We write $N_G(W)$ to denote the set of neighbors of $W$, i.e., $N_G(W)=\{v\in V\mid (\exists w\in W)(v\sim w)\}$.

07.25 DEF (Hall conditions)   Let $G$ be a bipartite graph with $V_1$ and $V_2$ the two parts of the vertex set. We say that a set $W\subseteq V_1$ satisfies the Hall condition if $|N(W)|\ge |W|$. So there are $2^{|V_1|}$ Hall conditions.

07.28 Philip Hall's Marriage Theorem (1935)   Let $G$ be a bipartite graph with $V_1$ and $V_2$ the two parts of the vertex set. $V_1$ can be matched if and only if $|N(W)|\ge |W|$ holds for all subsets $W\subseteq V_1$, i.e., all subsets of $V_1$ satisfy the Hall condition.

07.32 Bonus (12 points)   Deduce the Marriage Theorem from Kőnig's duality theorem $(\tau = \nu)$ (04.180).

07.35 ORD (10 points) (Kőnig, 1916)   Let $G$ be a non-empty regular bipartite graph. Use the Marriage Theorem to prove that $G$ has a perfect matching (a matching of size $n/2$).

07.XX  

07.XX  

07.XX  

More to follow. Please check back later.

Material covered:   Turán's Theorem in extremal graph theory. Ramsey's Theorem for graphs, the Erdős--Rado arrow symbol, Ramsey numbers, the Erdős--Szekeres upper bound (proof sketched). Erdős's lower bound stated, Zsigmond Nagy's explicit Ramsey graph defined.

06.XX  

06.15 DEF (Erdős-Rado arrow symbol). We write $n\to (k,\ell)$ to mean that no matter how we color the edges of $K_n$ red and blue, there will either be a red $K_k$ or a blue $K_{\ell}$.

06.17 DO   Prove: the statement "$n\to (k,\ell)$" is equivalent to the following statement:   "For every graph with $n$ vertices, either $\alpha(G) \ge k$ or $\omega(G)\ge \ell$. (Recall that $\alpha(G)$ denotes the independence number and $\omega(G)$ the clique number.)

06.20 DO   (Baby Ramsey)   (a)   $6\to (3,3)$.   (b)   $5\not\to (3,3)$.

06.23 ORD (4+7 points)   (a)   Define the symbol $n\to (q,r,s)$.   (b)   Prove:   $17 \to (3,3,3)$.

06.26 CH   Prove:   $16\not\to (3,3,3)$. Your construction should be convincing, easy to verify.   Hint.   Use the field of order 16. Make your 3-coloring of the edges have a lot of symmetry.

06.29 ORD (4 points)   For $k\ge 2$ prove:   $k \to (k,2)$.

06.32 Theorem (Erdős-Szekeres, 1934)   Let $k,\ell \ge 1$. Then $$ \binom{k+\ell}{k} \to (k+1,\ell+1) \,. $$

06.35 DEF (Ramsey numbers)   The Ramsey number $R(k,\ell)$ is the smallest $n$ such that $n \to (k,\ell)$.

06.36 DO   (a)   Show that $R(k,\ell)=R(\ell,k)$.
  (b)   Show that $R(k,2)=k$ for all $k\ge 1$ and $R(3,3)=6$.
  (c)   Show that the Erdős-Szekeres Theorem can be restated as   $R(k,\ell) \le \binom{k+\ell-2}{k-1}$.

06.38 DO   Prove the Erdős-Szekeres Theorem.   Hint.   Proceed by induction on $k+\ell$. Warning: there will be infinitely many "bases cases" (defined as cases not covered by the inductive step). What are they?
For $k, \ell\ge 3$, prove the recurrence $$R(k,\ell)\le R(k-1,\ell)+R(k,\ell-1)\,.$$ This takes care of the inductive step, using Pascal's identity.

06.42 Bonus (15 points)   The Erdős-Szekeres Theorem shows that $10\to (4,3)$. Improve this to $9\to (4,3)$. Your proof should be short and convincing. Elegance counts.

06.45 DO   Infer from the Erdős-Szekeres Theorem that   $4^k \to (k+1,k+1)$, i.e., $R(k+1,k+1)\le 4^k$.

06.48 DO   Prove:   $n^2 \not\to (n+1,n+1)$.

06.53 DO (Oddtown Theorem, Elwyn Berlekamp, 1969)   Let $A_1,\dots,A_m\subset [n]$ such that
  (i)   $(\forall i\in [m])(|A_i|$ is odd$)$, and   (ii)   $(\forall i,j\in [m])(i\neq j\Rightarrow |A_i\cap A_j|$ is even$)$.
Prove:   $m\le n$.
Hint.   The incidence vector of a set $A\subseteq [n]$ is the vector $\bfv_A=(v_1,\dots,v_n)$ where $v_j=1$ if $j\in A$ and $v_j=0$ if $j\notin A$.
Show that under the Oddtown conditions, the incidence vectors of the $A_i$ are linearly independent over the field $\fff_2$.

06.56 DO (Fisher--Bose Theorem, 1940/1949)   Let $A_1,\dots,A_m\subseteq [n]$ and $\lambda\in\nnn$ such that   $(\forall i,j\in [m])(i\neq j\Rightarrow |A_i\cap A_j|=\lambda)$. Prove:   $m\le n$.
Hint. Show that under the conditions of the Theorem, the incidence vectors of the $A_i$ are linearly independent over $\rrr$.

06.59 ORD (12 points) (Zsigmond Nagy's Ramsey graph, 1973)   Prove that $\binom{k}{3}\not\to (k+1,k+1)$. Use Nagy's graph, ZN, defined as follows:   $V(ZN)=\binom{[k]}{3}$, and two vertices $A,B\in V(ZN)$ are adjacent if and only if $|A\cap B|=1$.

06.XX  

06.XX  

06.XX  

06.XX  

06.XX  

06.XX  

06.XX  

More to follow. Please check back later.

Material covered:   The multinomial theorem. Automorphisms. Counting the copies of a graph in $K_n$. Counting spanning trees in $K_n$. Cayley's formula (stated, proved for $n\le 6$). The Laplacian of a graph. Counting the spanning trees of any graph: Kirchhoff's Theorem stated. Kneser's graph.

05.10 STUDY   PROB (Finite Probability Spaces) Chapters 7.1 (notation), 7.2 (finite probability spaces, events), 7.3 (conditional probability), 7.8 (random variables, expected value, indicator variables).

05.XX  

05.30 DEF   A multiset $M$ is a set $S$ together with a function $m:S\to \nnn$ (so the codomain is the set of positive integers). For $x\in S$ we say that $m(x)$ is the multiplicity of $x$ in $M$. We call $S$ the support of $M$. The size of $M$ is $\sum_{x\in S}m(x)$. Sometimes we write the multiplicities as superscripts, like $M=\{a^3,b,c^2\}$. We also denote multisets by double braces; in such cases we write each element of the support as many times as its multiplicity. Example: $M=\{\{a,a,a,b,c,c\}\}=\{a^3,b,c^2\}$. The order of the elements does not matter: $M=\{\{c,a,a,b,c,a\}\}$.
WARNING.   This notation conflicts with basic set notation. In basic set notation, $\{\{a,a,a,b,c,c\}\}$ means a set that has just 1 element, and that element is the set $\{a,b,c\}$. To avoid confusion, when using the double brace notation, we must always make it clear in the context that we are talking about multisets. One such example is spectra of matrices (below).

05.32 Convention  We extend the definition of the muliplicity function $m$ to objects that do not belong to $S$ by saying $m(x)=0$ for all $x\notin S$.

05.34 DEF   Let $M=(S,m)$ and $N=(T,n)$ be multisets (so $S$ and $T$ are their respective supports and $m$ and $n$ the corresponding multiplicity functions). We say that $M\subseteq N$ if $S\subseteq T$ and $(\forall x\in S)(m(x)\le n(x))$. We say that $M$ and $N$ are disjoint if their supports are disjoint.

05.36 Terminology   Let $A$ be a complex $n\times n$ matrix with characteristic polynomial $f_A(t)=\prod_{i=1}^n (t-\alpha_i)$. Then we say that the spectrum of $A$ is the multiset $\{\{\alpha_1,\dots,\alpha_n\}\}$. If $G$ is a graph then we define its spectrum as the spectrum of its adjacency matrix. We sometimes say this is the adjacency spectrum of $G$, to emphasize the distinction from the spectra of other matrices associated with $G$.
GRAMMAR: The pural of "spectrum" is spectra.

05.40 DO   Let $J_n$ be the $n\times n$ all-ones matrix. Show that the spectrum of $J_n$ is $\{n,0^{n-1}\}$.
Hint   Show that $\rank(J_n)=1$. Infer from this, using Rank-Nullity, that $0$ has multiplicity at least $n-1$. Now to determine the last eigenvalue, either use the fact that $\trace(J_n)=n$, or observe that the all-ones vector $\boe$ is an eigenvector to eigenvalue $n$.

05.43 DO   Let $A$ be an $n\times n$ complex matrix and $c\in \ccc$ a scalar. Let $\{\{\lambda_1,\dots,\lambda_n\}\}$ be the spectrum of $A$. Show that the spectrum of $A+cI$ is $\{\{\lambda_1+c,\dots,\lambda_n+c\}\}$. (Note that this observation does not require $A$ to be diagnalizable.)

05.46 DO   Infer from the preceding two exercises that the spectrum of $K_n$ is $\{\{n-1,(-1)^{n-1}\}\}$.

05.49 DO   Prove: the spectrum of a triangular matrix is the multiset of its diagonal entries.

05.53 Bonus (9 points)   Let the spectrum of the graph $G$ be $\{\{\lambda_1,\dots,\lambda_n\}\}$ and the spectrum of the graph $H$, $\{\{\mu_1,\dots,\mu_k\}\}$. Prove that the spectrum of $G\Box H$ is $\{\{\lambda_i+\mu_j \mid i\in [n], j\in [k]\}\}$.

05.56 ORD (10 points)   Determine the spectrum of the graph $Q_d$ (the $d$-dimensional cube): determine its support and the multiplicity of each member of the support. Check that the multiplicities add up to $2^d$, the order of $Q_d$. (Use the preceding exercise.)

05.60 Reward   Prove: if two graphs are isomorphic then they have the same spectrum.

05.63 Challenge   Prove that converse is false: find two non-isomorphic graphs that are isospectral (have the same spectrum).

05.68 Bonus (converse of Rayleigh's Principle) (14 points, due April 24)   Prove the following converse of Rayleigh's Priciple (4.98).
Let $A$ be a symmetric $n\times n$ real matrix with largest eigevalue $\lambda_1$. Let $x\in\rrr^n$ be a non-zero vector such that $R_A(x)=\lambda_1$. Prove that $x$ is an eigenvector of $A$ to eigenvelue $\lambda_1$. (Here $R_A$ denotes the Rayleigh quotient of $A$, see Def. 5.133.)

In the following sequence of exercises, $G$ is a graph with eigenvalues $\lambda_1\ge\lambda_2\ge \dots \ge \lambda_n$. Do not use the Perron-Frobenius Theorem in any of the exercises about graphs; your tools should be the Spectral Theorem and its consequences, including Rayleigh's Principle, its converse, and the Courant-Fischer max/min characterization of the eigenvalues.

05.70 ORD (10 points)   Prove:   $(\forall i)(\lambda_1\ge |\lambda_i|)$. Use Rayleigh's Principle (4.98).

05.73 Bonus (7+7 points)   (a)   Prove that $G$ has a non-negative eigenvector to the eigenvalue $\lambda_1$ (i.e., an eigenvector all coordinates of which are non-negative).   (b)   If $G$ is connected then $G$ has an all-positive eigenvector to the eigenvalue $\lambda_1$.
Use (a) to prove (b). Do not use (b) to prove (a). Use Rayleigh's Principle (4.98) and its converse (5.68). Make it clear where you are using which result.
Updated April 15 at 15:15. Originally only (b) was assigned, and 5.68 was not yet posted. 5.68 will add clarity and structure to the proof.

05.76 Bonus (14 points)   If $G$ is connected then $\lambda_1 > \lambda_2$. In other words, $\lambda_1$ is a simple eigenvalue (has multiplicity 1).

05.79 ORD (6 points)   Find a disconnected graph such that $\lambda_1 > \lambda_2$. Compute the spectrum of your graph. Make your graph as small as you can. (Smallest order, then smallest size for that order.) Do not prove that your graph is smallest.
Note.  Remember that this cannot happen for regular graphs (2.160).

05.82 ORD (7 points)   Assuming 5.73(b), give a very simple proof of 5.73(a) (just a few lines). Use determinants. Do not use Rayleigh's Principle or its converse.
Updated 04-15 at 15:15. The instructions in the last two sentences were added.

05.85 ORD (8 points)   Find a graph for which $\lambda_1$ has no all-positive eigenvector. Make your graph as small as you can. (Smallest order, then smallest size for that order.) Do not prove that your graph is smallest.

05.88 DEF   We say that a vector $(x_1,\dots,x_n)\in\rrr^n$ is invariant under the permutation $\pi$ of the set $[n]$ if $(\forall i\in [n])(x_{\pi(i)}=x_i)$.

05.90 Bonus (8 points)   Let $G$ be connected and let $\bfx$ be an eigenvector to $\lambda_1$. Prove that $\bfx$ is invariant under all automorphisms of $G$.

05.93 Bonus (5+10 points)   (a)   Determine the rank of the adjacency matrix of the complete bipartite graph $K_{r,s}$.   (b)   Determine the spectrum of $K_{r,s}$.
Your solution to (b) should not take more than four lines.

05.95 Bonus (8+12 points)   (a)   Let $H$ be a subgraph of $G$ with eigenvalues $\mu_1\ge\mu_2\ge\dots\ge \mu_k$ where $k$ is the number of vertices of $H$. Prove:   $\lambda_1 \ge \mu_1$.   (b)   The inequality $\lambda_2\ge \mu_2$ is not necessarily true. Prove that $G=K_n$ and $H=K_n^-$ are a counterexample for all $n\ge 2$, where $K_n^-$ is $K_n$ minus an edge (but we do not delete vertices, so $K_n^-$ is a spanning subgraph of $K_n$).
Updated 5-5 (after deadline): points were listed in wrong order: 12+8 $\to$ 8+12.

05.100 DO (Multinomial Theorem)   Prove: $$ (x_1+\dots + x_t)^n = \sum_{k_i\ge 0, \sum k_i=n} \binom{n}{k_1,\dots,k_t} \prod_{i=1}^t x_i^{k_i}\,,$$ where $$ \binom{n}{k_1,\dots,k_t} = \frac{n!}{\prod_{i=1}^t k_i!}\,.$$

Note that with this notation, $\binom{n}{k} = \binom{n}{k,n-k}$.

05.102 ORD (6 points)   Determine the number of terms in the Multinomial Theorem. Your answer should be a simple closed-form expression in terms of $n$ and $t$.

05.104 DO   Let $G$ be a graph with $n$ vertices. Prove that the number of subgraphs of $K_n$ isomorphic to $G$ is $\frac{n!}{|\aut(G)|}$. Here $\aut(G)$ denotes the automorphism group of $G$ (see 02.80).

05.106 DO   (a)   For $1\le n\le 6$, list all non-isomorphic trees of order $n$.   (b)   With each tree listed, determine the order of its automorphism group (i.e., count its automorphisms).   (c)   With each tree $T$ listed, determine the number of copies of $T$ in $K_n$.   (d)   Use this information to compute the number of spanning trees of $K_n$ for $1\le n\le 6$. Verify that this numberis $n^{n-2}$.

05.109 ORD (12 points) (counting trees with prescribed degrees)   Let $d_1,\dots,d_n$ be positive integers such that $\sum_{i=1}^n d_i = 2n-2$. Consider all trees on the vertex set $[n]$ satisfying the condition that $\deg(i)=d_i$. Prove that the number of such trees is $$\frac{(n-2)!}{\prod_{i=1}^n (d_i-1)!}\,.$$ Proceed by induction on $n$.
Updated April 10, 21:15:   This problem was stated correctly in class but incorrectly on this website (it mistakenly had $\prod d_i!$ in the denominator).

05.112 DO (Cayley's formula)   Prove: the number of spanning trees of $K_n$ is $n^{n-2}$. Use the previous exercise and the Multinomial Theorem.

Material covered:   Distance metric, diameter. Girth. Chromatic number as conflict model. Polynomials, degree. Real-rooted polynomials. Interlacing. Rayleigh quotient of real symmetric matrix. Extremal values of Rayleigh quotient. Courant--Fischer max-min characterization of eigenvalues. Interlacing eigenvalues. Consequences to subgraphs. Matchings, coverings in graphs. Dénes König's Theorem: for bipartite graphs, matching number = covering number (proved).

04.10 REVIEW   LinAlg Chap 8 (eigenvalues), especially Section 8.3 (polynomials)

04.15 STUDY   LinAlg Chap 10 (Spectral Theorem, Rayleigh's Principle, Courant--Fischer max/min characterization o eigenvalues).

04.15 REVIEW   DMmini Terminology 6.1.42, especially distance, diameter, girth, Hamiltonicity.

04.25 DO   (a)   Verify:   $\diam(K_n)=1$, $\diam(P_n)=n-1$, $\diam(C_n) = \lfloor n/2\rfloor$, $\diam(K_{r,s})=2$.

04.26 DO if you are familiar with finite projective planes:   What is the diameter of the incidence graph of a finite projective plane (2.142)?

04.27 Bonus (9 points)  Let $G,H$ be connected graphs. Prove:   $\diam(G\Box H)=\diam(G) + \diam(H)$.

04.31 DO   Prove: for a connected graph $G=(V,E)$, distance is a metric on the set of vertices. This means
  (a)   $(\forall u\in V)(\dist(u,u)=0)$
  (b)   (symmetry) $(\forall u,v\in V)(\dist(u,v)=\dist(v,u))$
  (c)   (triangle inequality) $(\forall u,v,w\in V)(\dist(u,v)+\dist(v,w)\ge \dist(u,w))$

04.33 DO   Let $G$ be a graph. Prove: either $\diam(G)=\diam(\Gbar)=3$ or $\min\{\diam(G),\diam(\Gbar)\}\le 2$.

04.35 DO   (a)   Let $H$ be a spanning subgraph of $G$. Prove:   $\diam(H) \ge \diam(G)$.   (b)   For every $n$, give an example of a connected graph $G$ of order $n$ and a spanning tree $T$ of $G$ such that $\diam(T)=(n-1)\diam(G)$. So the diameter of a spanning tree can be much greater than the diameter of the graph.

04.37 Bonus (13 points)   Prove: every connected graph $G$ has a spanning tree $T$ such that $\diam(T) \le 2\diam(G)$.

04.39 ORD (5+5 points)   (a)   Determine the diameter of $Q_d$, the $d$-dimensional cube (Def 02.43(c)).   (b)   Let $u,v$ be two vertices at maximum distance in $Q_d$. Count the shortest paths between them. Your answer should be a simple closed-form expression in terms of $d$.

04.41 ORD (12 points)   Let $G$ be a graph with $\deg_{\min}(G) \ge 3$. Prove:   $\girth(G) = O(\log n)$. The big-Oh notation hides a constant; state the smallest valid constant your proof yields, assuming the base of the logarithm is 2. (If you use natural logarithms, please write "\ln". In any case, make sure you clarify the base of the logarithm used.)
Updated Apr 10 at 1:00: comments about the base of the logarithm added.

04.43 DEF   The oddgirth of a graph $G$ is the length of the shortest odd cycle. For bipartite graphs, the oddgirth is $\infty$.

04.45 ORD (9 points)   For infinitely many values of $n$, construct a graph $G_n$ that is not bipartite, has $\deg_{\min}(G_n)\ge 100$, and $\oddgirth(G_n)=\Omega(n)$. The big-Omega notation hides a constant; state the largest valid constant your proof yields.

04.47 ORD (7 points)   Prove: if $k\ell$ is odd then the $k\times\ell$ grid is not Hamiltonian (does not have a Hamilton cycle). Your proof should be at most two lines.

04.50 NOTATION Let $\fff$ be a field. (If you are not familiar with the general concept of fields, let $\fff=\rrr$ or $\ccc$.) Then $\fff[t]$ denotes the set of polynomials over $\fff$ (i.e., the set of polynomials with coefficients from $\fff$). This is an infinite-dimensional vector space over $\fff$. The set $\{1,t,t^2,\dots\}$ is a basis of this vector space. Of particular importance to us is $\rrr[t]$, the set the polynomials with real coefficients; we refer to them as real polynomials.

04.53 DO   Let $f_0,f_1,\dots\in\fff[t]$ be an infinite sequence of polynomials such that $(\forall k)(\deg(f_k)=k)$. Prove: these polynomials form a basis of $\fff[t]$, i.e., every polynomial can be uniquely represented as a finite linear combination of the $f_i$.

04.56 DEF   Let $f(t)=\sum_{i=0}^n a_it^i\in\rrr[t]$ be a real polynomial of degree $n$ (so $a_n\neq 0$). We say that $f$ is real-rooted if all complex roots of $f$ are real. (Note: $\rrr\subseteq\ccc$.) This is equivalent to saying that $f$ can be factored into linear factors over $\rrr$:   $f(t)=a_n\prod_{i=1}^n (t-\alpha_i)$ where $\alpha_i\in\rrr$.
Examples: $t^2-1$ and $t^4-5t^2+6$ are real-rooted, $t^2+1$ and $t^3-1$ are not. (Verify!)

04.60 DEF (interlacing)   Let $a_1\ge a_2\ge\dots\ge a_n$ and $b_1\ge b_2\ge\dots\ge b_{n-1}$ be two sequences of real numbers. We say that the $b_j$ interlace the $a_i$ if $a_1\ge b_1\ge a_2\ge b_2\ge a_3\ge\dots\ge a_{n-1}\ge b_{n-1}\ge a_n$. We say that the $b_j$ strictly interlace the $a_i$ if $a_1 > b_1 > a_2 > b_2 > a_3 >\dots > a_{n-1} > b_{n-1} > a_n$. If $f(t)=c_n\prod(t-a_i)$ and $g(t)=d_{n-1}\prod(t-b_j)$, where $c_nd_{n-1}\neq 0$, then we say that $g$ (strictly) iterlaces $f$.

04.63 Bonus (12 points)   Let $f$ be a real-rooted real polynomial of degree $n\ge 1$. Prove that $f'$ (the derivative of $f$) is also real-rooted and its roots interlace the roots of $f$.

04.65 DO   Show that if the polynomial $f$ is real-rooted and all of its roots are distinct then $f'$ strictly interlaces $f$.

04.68 THEOREM   The characteristic polynomial of a real symmetric matrix is real-rooted.
(This is part of the Spectral Theorem and can be proved in a few lines.)

04.70 DO   Prove 04.68 without using the Spectral Theorem.
Hint. For a complex number $z$, let $\zbar$ denote its complex conjugate. For a complex matrix $B=(b_{ij})$, let $B^*=(\bbar_{ji})$ denote the conjugate-transpose of $B$. Observe that $(AB)^*=B^*A^*$. If $x\in\ccc^n$ (a column vector) then $x^*x=0$ if and only if $x=0$.
Let now $A$ be an $n\times n$ real symmetric matrix and let $x\in\ccc^n$ be a complex eigenvector to eigenvalue $\lambda\in \ccc$, so $Ax=\lambda x$. Compare the $1\times 1$ matrix $x^*Ax$ with its conjugate-transpose.

04.75 THEOREM (Interlacing Theorem for real symmetric matrices)   (LinAlg Theorem 10.2.8.)   Let $A$ be a real symmetric $n\times n$ matrix. Let $B$ denote the matrix obtained by removing the $i$-th row and the $i$-th column of $A$ for some $i\in [n]$. So $B$ is a real symmetric $(n-1)\times (n-1)$ matrix. Then the eigenvalues of $B$ interlace the eigenvalues of $A$.

04.78 ORD (8 points)   Let $G$ be a graph with $n$ vertices and $H$ an induced subgraph of $G$ on $h$ vertices. Let the eigenvalues of $G$ be $\lambda_1\ge\lambda_2\ge\dots\ge\lambda_n$ and the eigenvalues of $H$ be $\mu_1\ge\mu_2\ge\dots\ge \mu_h$. Use the Interlacing Theorem to prove: for all $i\in [h]$, $$\lambda_i \ge \mu_i \ge \lambda_{n-h+i}$$

The next two exercises give immediate consequences of this result.

04.80 ORD (6 points)   Let $G$ be a graph. Prove:   $\alpha(G) \le $ the number of non-negative eigenvalues of $G$.

04.82 ORD (6 points)   Let $G$ be a graph and let $r$ be the number of eigenvalues of $A$ that are $\le -1$. Prove:   $\omega(G) \le r+1$. (Recall that $\omega(G)$ denotes the clique number of $G$.)

The next sequence of exercises leads to a proof of the Interlacing Theorem.

04.88 DEF   (LinAlg Def 10.2.5) Let $A$ be an $n\times n$ symmetric real matrix. The Rayleigh quotient of $A$ is a function $R_A:\rrr^n\setminus\{0\}\to\rrr$ defined by $$ R_A(x) = \frac{x^TAx}{x^Tx} \qquad (x\in\rrr^n\setminus\{0\})\,.$$

04.90 DO   Prove that $R_A(x)$ is bounded and attains its maximum and minimum, i.e., $(\exists y,z\in \rrr^n\setminus\{0\}) (\forall x\in\rrr^n\setminus\{0\})(R_A(y)\le R_A(x)\le R_A(z))$.
Hint.   Observe that for any $c\in\rrr\setminus\{0\}$, we have $R_A(cx)=R_A(x)$.

04.92 DO   Let $A$ be a symmetric real matrix and $x$ an eigenvector to eigenvalue $\lambda$:   $Ax=\lambda x$. Then $R_A(x)=\lambda$.

04.95 DO   Let $A$ be a real symmetric $n\times n$ matrix and let $b_1,\dots,b_n$ be an orthonormal eigenbasis for $A$, i.e., $b_1,\dots, b_n$ is an orthonormal basis of $\rrr^n$ and $Ab_i=\lambda_i b_i$. (Such a basis exists by the Spectral Theorem.) Let $x\in\rrr^n\setminus\{0\}$ be expressed as $x=\sum_{i=1}^n \beta_i b_i$. Then $$ R_A(x) = \frac{\sum_{i=1}^n \lambda_i\beta_i^2}{\sum_{i=1}^n \beta_i^2}\,.$$

04.98 DO (Rayleigh's Principle)   LinAlg 10.2.6 (the maximum of the Rayleigh quotient is $\lambda_1$ and the minimum is $\lambda_n$).

04.100 Reward (Courant--Fischer)   LinAlg 10.2.7 (max/min characterization of the eigenvalues of a symmetric real matrix)

04.102 Bonus (15 points)   Deduce the Interlacing Theorem (4.60) from Courant--Fischer.

04.120 DEF   A matching in a graph $G$ is a set $M\subseteq E$ of disjoint edges. (Clearly, $|M|\le n/2$.) A vertex $v$ is matched by $M$ if $v$ belongs to one of the edges in $M$. The matching number of $G$, denoted $\nu(G)$, is the size of a maximum matching (the maximum number of disjoint edges). ($\nu$ is the Greek letter "nu", coded as \nu in LaTeX). A perfect matching is a matching of size $n/2$ (all vertices are matched).

04.123 DO   Verify:  $\nu(K_n)=\nu(C_n)=\nu(P_n)=\lfloor n/2\rfloor.$

04.126 DO   For every $n\ge 2$, find a graph with $n$ vertices and $n-1$ edges such that $\nu(G)=1$.

04.129 DO   Let $M$ be a maximal matching. Prove:   $|M| \ge \nu(G)/2$.

04.135 DEF   A cover of a graph $G$ is a a set $C\subseteq V$ of vertices that "hits" every edge: $(\forall e\in E)(C\cap e\neq\emptyset)$. A cover is also called a vertex cover. In computer science, a cover is usually called a hitting set. The covering number, denoted $\tau(G)$, is the size of a minimum cover. (It is also called the hitting number.) ($\tau$ is the Greek letter tau, coded in LaTeX as \tau.)

04.138 DO   $C\subseteq V$ is a cover if and only if its complement, $V\setminus C$, is an independent set. Therefore $$ \alpha(G) + \tau(G) = n\,.$$ It follows that computing $\tau(G)$ is NP-hard (because it is equivalent to computing $\alpha(G)$).

04.141 DO   Prove:   $\nu(G) \le \tau(G)$.

04.143 ORD (5 points)   Let $M$ be a maximal matching. Prove:   $\tau(G) \le 2|M|$.

In particular, we have   $\tau(G)\le 2\nu(G)$.

04.146 ORD (6 points)   Find infinitely many graphs $G$ without isolated vertices such that $\tau(G) = 2\nu(G)$. The description of your graphs should only take one line.

04.150 The greedy matching algorithm   This algorithm finds a maximal matching.
 01   input: the graph $G=(V,E)$
 02   output: a maximal matching $M$
 03   initialize   $M:= \emptyset$, $W:=V$
 04  while $E(G[W])\neq \emptyset$
 05     pick $e\in E(G[W])$
 06     $M:=M\cup \{e\}$
 07     $W:=W\setminus e$
 08  end(while)
 09  return $M$

04.152 Comment on terminology   The defining feature of greedy selection is that we never revise our previous choices.

04.154 DO   Verify that the greedy matching algorithm indeed returns a maximal matching.

04.156 Comments on computational complexity.   Computing $\tau(G)$ is NP-hard because, by 4.138, it is equivalent to computing $\alpha(G)$.

On the other hand, $\nu(G)$ is known to be computable in polynomial time (Edmonds, 1965). This highly nontrivial result was critical in establishing the notion of "polynomial time" as a central concept in the theory of computing. It elevated the design of algorithms from art to science, with rigorous mathematical criteria of analysis. It paved the way for the celebrated notion of NP ("nondeterministic polynomial time").

04.158 Approximation factor.   Solving a maximization problem (such as finding $\alpha(G)$) within a factor of $r > 1$ means finding an instance of the quantity to be maximized (such as an independent set) that is not smaller than $(1/r)$ times the optimum (such as an independent set $A\subseteq V$ of size $|A| \ge (1/r)\alpha(G)$).
Solving a minimization problem (such as finding $\tau(G)$) within a factor of $r > 1$ means finding an instance of the quantity to be maximized (such as a cover) that is not greater than $r$ times the optimum (such as a cover $C\subseteq V$ of size $|C| \le r\cdot\tau(G)$).

04.160 Comments on the complexity of approximation.   It is known that computing $\alpha(G)$ approximately is NP-hard even within factors as large as $n^{1-\epsilon}$ (for every constant $\epsilon > 0$) (Håstad 1996).

In contrast, we have an easy and very efficient (linear-time) algorithm that approximates $\tau(G)$ within a factor of 2: find a maximal matching $M$ via the greedy algorithm; let $C$ be the set of vertices matched by $M$; this is a cover. Given that $|M|\le \tau(G) \le 2|M|$, this is a factor-2 approximation.

04.163 Question for contemplation:   We have $\alpha+\tau = n$ (4.138). So how is it possible that $\tau$ is easy to approximate within a factor of 2, while $\alpha$ is hard to approximate within much larger factors?

04.166 ORD (6 points).   Prove:   $\tau(C_n)=\lceil n/2\rceil$. For the lower bound, use the method of linear relaxations. Proof by other methods will not be accepted.

04.169 DO   Verify:   $\tau(K_n)=n-1$, $\tau(P_n)=\lfloor n/2\rfloor$.

04.172 ORD (8 points, due April 17)   Find the size of the smallest maximal matching in $C_n$.

04.180 (Dénes Kőnig's Duality Theorem, 1931)   If $G$ is a bipartite graph then $\nu(G)=\tau(G)$.
Note that this is a "good characterization": if we found a matching and a cover of equal size then both are optimal. So we can certify the optimality of a matching in a bipartite graph by providing a cover of the same size and vice versa.

04.183 Historical comments.   Dénes Kőnig (1884-1944) was a professor at the Budapest University of Technology. In 1936 he published the first monograph on graph theory (in German). This book was largely responsible for establishing the field as an area of research in its own right. Dénes Kőnig's lectures made a strong impression on young Paul Erdős, Paul Turán, and Tibor Gallai. Within a decade, Turán, an analyst and number theorist, would produce "Turán's theorem," the result that established the field of extremal graph theory which would became one of Erdős's lifelong passions. Gallai became a prominent graph theorist and mentor of László Lovász.

Within weeks of Kőnig's announcement of his result, Jenő Egerváry, his collague at the Budapest Technical University, extended it to weighted graphs. Their papers appeared in the same issue of a Hungarian mathematical journal (in Hungarian). These results pioneered the area of combinatorial optimization and the concept of combinatorial duality. Their work anticipated the primal-dual methods subsequently developed. In 1955, American mathematician Harold Kuhn translated the papers to English and gave the method the name "Hungarian method."

Material covered:   Induced subgraphs. Independence number, clique number, chromatic number. Cone of a graph. Linear relaxation. Bipartite graphs. Automorphisms.

03.XX  

03.20 DO   The 2-coloring of a connected bipartite graph is unique (up to the naming of the colors).

03.23 ORD (8 points)   Let $G$ be a non-empty regular bipartite graph. Prove:   $\alpha(G) = n/2$. Here $\alpha(G)$ denotes the independence number of $G$.

03.26 ORD (8+7 points, due April 10)   (a)   For every $\epsilon > 0$, find a connected bipartite graph $G$ with an even number of vertices such that the unique 2-coloring of $G$ is balanced (the two parts have equal size, i.e., the number of red vertices is equal to the number of blue vertices), yet $\alpha(G) > (1-\epsilon)n$.   (b) Determine the minimum number of vertices of such a graph $G$ (as a function of $\epsilon$). Prove that your number is minimum.

03.29 DO   $\omega(G)=\alpha(\Gbar)$. Here $\omega(G)$ denotes the clique number (order of largest clique in $G$).

03.32 ORD (5 points)   Let $n=k\ell$. Find a graph on $n$ vertices satisfying $\alpha(G)\le k$ and $\omega(G)\le \ell$.

03.34 Challenge   Let $G$ be a vertex-transitive graph. Prove:   $\alpha(G)\cdot\omega(G) \le n$.
Updated 3-30 at 20:40. The typo was $\ne$ instead of $\le$.

03.37 Bonus (independence number of odd toroidal grid) (12 points)   Let $r \ge s \ge 3$ be odd numbers. Determine $\alpha(C_r\Box C_s)$. Your answer should be a simple closed-form expression in terms of $r$ and $s$.
Updated Wed 3-29 at 14:20. Bad typo fixed.

03.39  

03.XX  

03.XX  

More to follow. Please check back later.

Material covered:   Degree, Handshake Theorem. Regular graphs. Asymptotic equality of sequences. Tail predicates. Eventually non-zero sequences. Using limsup, liminf. Unique paths in trees. Spanning subgraphs, spannig trees. Cartesian product of graphs.

02.05 STUDY   Review STUDY material assigned in 01.10--01.36

02.10 STUDY   DMmini Chap 4.1 (divisibility, congruences, gcd, etc.)

02.11 Terminology and LaTeX codes:   divisibility:   $a\mid b$   LaTeX:   "a \mid b"   verbally: "$a$ divides $b$" or "$a$ is a divisor of $b$" or "$b$ is divisible by $a$" or "$b$ is a multiple of $a$"
   congruence $a\equiv b \pmod{m}$   LaTeX:   "a\equiv b \pmod{m}"   "$a$ is congruent to $b$ modulo $m$" or "$a$ is congruent to $b$ mod $m$"

02.13 STUDY   DMmini Chapters 2.3 and 2.4 (further asymptotic notation: little-oh, little-omega, big-oh, big-Omega, big-Theta)

02.15 STUDY   DMmini Chapter 4 (convex functions and Jensen's inequality) [pronounced "Yensen"]

02.17 STUDY   Petersen's graph (Ex. 2.145 below)

02.20 DO   Let   $A= \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} \,.$ For $k\in\nnn$, determine the matrix $A^k$. Describe each entry of the matrix $A^k$ as a very simple expression in terms of a familiar sequence.

02.22 DO   Understand why   $\gcd(0,0)=0$.

02.24 ORD (9+8 points, due April 10)   All parameters in this problem are integers.   (a)   Let $a=5k+7$ and $b=8k+3$. Prove: $\gcd(a,b)=1$ or $41$. Elegance counts heavily; the problem has a solution in one line.   (b)   Find all values of $k$ for which $\gcd(a,b)=41$. Describe your answer in the form "the set of solutions is the set of integers of the form $k\equiv q \pmod m$." Find the right values of $q$ and $m$.

02.26 DO   DMmini 4.1.22(d)   ($\gcd(a^m-,a^n-1)$)

02.28 Bonus (10 points, due April 10)   DMmini 4.1.22(c)   ($\gcd$ of Fibonacci numbers)

02.30 DO   The number of graphs with $m$ edges on a given set of $n$ vertices is $$ \binom{\binom{n}{2}}{m}\,.$$ This is true even if $m > \binom{n}{2}$ (in which case the number of such graphs is zero, which is consistent with the fact that for $k > n$, by definition, $\binom{n}{k}=0$. (The definition of $\binom{n}{k}$ is "the number of $k$-subsets of an $n$-set.")

02.33 DEF   An isolated vertex is a vertex of degree zero (it has no neighbors).   Example: In the empty graph (no edges) every vertex is isolated.

02.36 Bonus (14 points, due April 10)   Let $NI(n)$ denote the number of graphs without isolated vertices on a given set of $n$ vertices. Prove:   $NI(n)\equiv n+1 \pmod 2$. In other words, $NI(n)$ is odd if and only if $n$ is even.

02.37 DEF (decision tree complexity)   We call the set $\Omega:= \{0,1\}^n$ the Boolean domain and a predicate $f:\Omega\to \{0,1\}$ a Boolean function. We wish to evaluate a known Boolean function $f$ at a hidden input $x=(x_1,\dots,x_n)\in\Omega$ by asking questions of the form "$x_i =1$?" to which the oracle gives YES/NO answers. (The oracle is truthful.) For each question we have to pay one aureus (golden coin in ancient Rome). The questions we ask are deterministic and adaptive: each question is determined by the history of the interaction so far. We stop when we know the value $f(x)$. (So the number of questions asked depends on our strategy and on the hidden input.) (The is essetially the "animal, vegetable, mineral" game.) The cost of our protocol (questioning strategy) is the number of questions asked (aurei paid) on the worst input. (Which input is worst depends on the protocol.) The decision tree complexity of $f$, denoted $D(f)$, is the cost of the optimal protocol (the minimum over all protocols of the maximum over all inputs of the number of questions asked). We say that the function $f$ is evasive if $D(f)=n$ (on some input $x$ we need to learn the entire input to find the value $f(x)$).

02.39 Reward   Consider the following predicate on the set of graphs with a given set of vertices: "the graph has no isolated vertices." Prove: if the number of vertices is even then this predicate is evasive.
Explanation. Let the input graphs have $k$ vertices; then $n=\binom{k}{2}$, and adjacency is represented by a $(0,1)$-sequence $x$ of length $n$ -- so $x$ encodes the graph. $f(x)=1$ if the graph has no isolated vertices.

02.41 DEF   Let $G=(U,E)$ and $H=(W,F)$ be graphs. We define the Cartesian product graph $K=G\Box H$ by setting $V(K)=U\times W$ and defining $(u_1,w_1)\sim_K (u_2,w_2)$ if either ($u_1=u_2$ and $w_1\sim_H w_2$) or ($w_1=w_2$ and $u_1\sim_G u_2$).   (Here $v_i\in V$ and $w_i\in W$.)

02.43 DEF/DO   (a)   For $k,\ell\ge 1$, we define the $k\times \ell$ grid graph as $P_k\Box P_{\ell}$.

                

It has $n=k\ell$ vertices. Count its edges. How many vertices have degree less than 4 ?
  (b)   For $k,\ell\ge 3$, we define the $k\times \ell$ toroidal grid graph as $C_k\Box C_{\ell}$.

                

It has $n=k\ell$ vertices. It is regular of degree 4. Count its edges.
  (c)   For $d\ge 1$ we define the $d$-dimensional cube graph $Q_d$ as the $d$-th Cartesian power of $K_2$. So $Q_d$ has $2^d$ vertices, labeled with the $2^d$ $(0,1)$-sequences, and vertices $(a_1,\dots,a_d)$ and $(b_1,\dots,b_d)$ are adjacent exactly if $\sum_{i=1}^d |a_i-b_i|=1$. (Here $a_i,b_i\in\{0,1\}$.) Verify: $Q_d$ is regular of degree $d$. Count its edges.

02.46 ORD (7 points)   DMmini 6.1.49 (count shortest paths between opposite corners of the $k\times\ell$ grid). The answer should be a simple closed-form expression. For our definition of closed-form expressions, read PROB Chap. 7.1.

02.50 NOTATION Let $G$ be a graph. The maximum degree of $G$ is $\deg_{\max}(G)=\max\{\deg(v)\mid v\in V\}$. The minimum degree, $\deg_{\min}(G)$, is defined analogously. The average degree is $$\deg_{\avg}(G) = \frac{\sum_{v\in V} \deg(v)}{n} = \frac{2m}{n}\,.$$

02.52 ORD (9+8 points)   (a)   Let $G$ be a non-empty graph (i.e., $m > 0$). Prove that $G$ has a subgraph $H$ such that $\deg_{\min}(H) > (1/2)\deg_{\avg}(G)\,.$   (b)   Prove that the factor $1/2$ is tight in the following sense. For every $\epsilon > 0$, there exist infinitely many graphs $G$ such that for every subgraph $H\subseteq G$ we have $\deg_{\min}(H) < (1/2+\epsilon)\deg_{\avg}(G)$.

02.55 Challenge   Let $G$ and $H$ be graphs with $n$ vertices. Assume $\deg_{\max}(G)\cdot\deg_{\max}(H) < n/2$. Prove: $H$ is isomorphic to some subgraph of the complement of $G$.   DO NOT LOOK IT UP.

02.57 ORD (8 points, due April 10)   Prove that the strict upper bound $n/2$ in Challenge problem 2.55 is tight in the following sense. For every even value of $n\ge 2$, find a pair of graphs, $G_n$ and $H_n$, of order $n$, such that $\deg_{\max}(G_n)\cdot\deg_{\max}(H_n) = n/2$ and $H_n$ is not isomorphic to any subgraph of the complement of $G_n$. Make the total number of edges of $G_n$ and $H_n$ as small as possible. The smaller the better. Do not prove that your example gives the smallest possible total number of edges.

02.60 DEF (induced subgraph)   See DMmini, Terminology 6.1.16.

WARNING:   You don't have to solve the Challenge problems, but you have to understand them and appreciate their significance in our context.

02.63 Challenge   Let $Q_d$ be the $d$-dimensional cube graph (Def. 2.43 above) where $d\ge 2$. So $n=2^d$. Let $A$ be subset of the set of vertices of $Q_d$ such that $|A|=n/2+1$. Consider the induced subgraph $Y:=Q_d[A]$. Prove:   $\deg_{\max}(Y) \ge \sqrt{d}$.   DO NOT LOOK IT UP.

02.65 Remark   The bound $\sqrt{d}$ (rounded up) is tight. This is another difficult result.

02.67 ORD (7 points)   Let $G$ be a graph. Prove:   $\chi(G) \le 1+\deg_{\max}(G)$.   (Here $\chi$ denotes the chromatic number.)

This bound shows that graphs of small degree have small chromatic number. The next exercise shows that the converse fails badly.

02.68 DO   For every even $n$, find a regular bipartite graph of degree $n/2$.

02.70 ORD (9 points)   Let $G$ be a non-empty regular graph. Prove:   $\alpha(G) \le n/2$.   ($\alpha(G)$ denotes the independence number of $G$.)

02.71 DO   Prove: $\chi(G) \ge \omega(G)$.   ($\omega(G)$ denotes the clique number of $G$, see DMmini Terminology 6.1.42.)

We shall see that the chromatic number can be much greater than the clique number; in fact, the chromatic number can be arbitrarily large even while the clique number is 2. On the other hand, there is an important class of graphs where the chromatic number and the clique number are equal.

02.72 DO   Find a graph with 6 vertices such that $\chi(G)=4$ but $\omega(G)=3$.

02.73 ORD (8 points) (Grötzsch's graph)   DMmini 6.1.59 (triangle-free graph of chromatic number 4 with 11 vertices). You don't need to prove that your graph is triangle-free, but you have to prove that your graph is not 3-colorable.

02.74 Challenge   DMmini 6.1.60 (triangle-free graphs of large chromatic number)

02.76 ORD (6 points)   Let $G$ be a graph. Prove:   $\alpha(G)\cdot\chi(G) \ge n$.

02.78 ORD (6+6 points)   (a)   For every $k,\ell\ge 1$ find a graph $G$ with $n=k\ell$ vertices such that $\alpha(G)=k$ and $\chi(G)=\ell$. So the inequality in the previous exercise is tight for every pair $(k,\ell)$.
  (b)   Find infinitely many graphs $G$ such that $\alpha(G)\cdot\chi(G) =\Omega(n^2)$. So for many graphs, there is a big gap between the two sides of the inequality in the previous exercise.
Below (02.90) we shall see that for "nice" graphs, the gap is much smaller.

02.80 DEF   An automorphism of a graph $G=(V,E)$ is an isomorphism of $G$ to itself. So this is a permutation of $V$ that preserves adjacency. The automorphisms form a group under composition of permutations (in the sense of abstract algebra). We denote the set (and group) of automorphisms $\aut(G)$.

02.81 Reward (counting automorphisms)   Verify that the graphs listed below have the number of automorphisms stated:   $P_n$ ($n\ge 2)$ 2 ;   $C_n$ ($n\ge 3$) $2n$ ;   $K_n$ $(n\ge 1)$ $n!$ ;   $Q_d$ ($d$-dimensional cube) $2^d\cdot d!$ ;   dodecahedron 120 ;   Petersen's graph 120 [this was misstated in class].

02.83 Reward Prove: the automorphism groups of the dodecahedron and the Petersen graph are not isomorphic, but they share isomorphic subgroups of order 60.

Material covered:   Basic structure of proofs. Relations. Partitions, Fundamental Theorem of Equivalence Relations. Graphs. Adjacency relation, adjacency matrix. Cliques (complete graphs), paths, cycles. Complement of a graph. Subgraphs. Accessibility: an equivalence relation on the set of vertices; its equivalence classes: connected componence. Connected graphs. Cycle-free graphs: forests. Connected forest: tree. Triangle-free graphs. Isomorphism of graphs.

01.10 Structure your proofs.   Define your variables. State your assumption(s) and the desired conclusion. Translate them as needed by interpreting the concepts via the definitions. In proving an "if and only if" statement, it is especially important to clearly distinguish between the $\Rightarrow$ and the $\Leftarrow$ part of the proof, and to state in each part what is the assupmtion and what is the desired conclusion. Avoid "proof by contradiction" when your argument is easily stated as a direct proof. State standalone Lemmas instead of long rolling text, delineate where the proof of the Lemma ends.

01.15 STUDY   REAS, Classes 6 and 7:  Relations, partitions, Fundamental Theorem of Equivalence Relations. Deadline: immediate.

01.18 STUDY   DMmini, Chap 1 (Logic, quantifiers). Deadline: immediate.

01.21 STUDY   PROB Chap. 7.1 (Notation: sets, functions, strings, closed-form expressions). Deadline: immediate.

01.24 STUDY   DMmini, Chap 5 (Counting). Deadline: Tuesday, March 28, before class.

01.27 STUDY   DMmini, Chap 6.1 (Graph theory terminology). Deadline: immediate.

01.30 STUDY   ASY (Asymptotic equality and inequality), entire set of notes. Deadline: Friday, March 24, before the discussion session.

01.33 STUDY   LinAlg Chapters 1-4 (matrices, systems of linear equations). This should be review. Deadline: March 24.

01.36 STUDY   LinAlg Chapters 6-7 (determinant). Chapter 8 (eigenvectors and eigenvalues). Deadline: March 30.
WARNING:   over the weekend (March 25-26), LinAlg was revised, especially Chapter 8. The date on the front cover should show the date March 26. If it shows an earlier date, please refresh your browser, clear your browser's cache, or try another browser.

01.38 NOTATION   If $A,B$ are sets then $B^A$ denotes the set of functions $f:A\to B$ (functions with domain $A$ and codomain $B$).

01.39 DO   If $A,B$ are finite sets then $|B^A|=|B|^{|A|}$.

01.40 ORD (6+8 points)   (a) REAS 6.97 (see REAS Def 6.94: Bell numbers).   (b) REAS 6.98.

01.43 ORD (10 points)   Use the previous exercise to prove that $\ln B(n) \sim n \ln n$. (Here $\sim$ refers to the asymptotic equality relation among sequences, see ASY Chap 5.) Use the liminf and limsup concepts in your proof (see ASY Chap 4).

In all exercises below, $n$ denotes the order (number of vertices) of the graph under consideration, and $m$ denotes its number of edges.

01.46 DO   Prove:   $0\le m \le \binom{n}{2}$. Show that the upper bound is tight for every $n$.

01.49 ORD (6 points)   Count the paths of length $k$ in the complete graph $K_n$. Give your answer in a simple closed-form expression (see PROB, Chap. 7.1 for our concept of a closed-form expression). (A path of length $k$ in a graph $G$ is a $P_{k+1}$ subgraph.)

01.52 ORD (6+6 points)   (a) Find two non-isomorphic regular graphs of the same order and the same degree. (The order of a graph is its number of vertices.) Describe your graphs in terms of the types of graphs we have named in class (we introduced notation for them). The description should be very simple, just one line. No pictures are needed (but you may attach hand-drawn pictures to your solution if you wish). Find the smallest pair of examples: smallest number of vertices, and given that number of vertices, smallest number of edges. You need to prove that your graphs are not isomorphic. Do not prove that they are smallest.   (b) Same as (a) with the added requirement that both graphs be connected. Again, your description of the graphs should be very simple, no more than a line and a half.

01.55 ORD (6+6 points)   REAS 24.82(a)(b) (self-complementary graphs).

01.56 DEF (maximal vs. maximum)   An object is maximal if it cannot be extended. An object is maximum if it is largest (among the set of objects under consideration). For example, a path in a graph is maximal if it cannot be extended to a longer path; and it is maximum if it is a longest path. A maximum object is always maximal, but usually the converse is not true.

01.57 DO   In a vector space, every maximal independent set is maximum (i.e., it is a basis).

01.58 DO   Find a tree in which the longest paths have length 100, but there exist maximal paths of length 2.

01.59 DO   Let $T$ be a tree of order $n\ge 2$. Then the endpoints of every maximal path have degree 1. In particular, every tree of order $\ge 2$ has at least two vertices of degree 1.

01.60 DO   REAS 24.88 (number of edges of a tree and of a forest).

01.62 DEF   Let $G=(V,E)$ be a graph. We say that vertex $v$ is accessible from vertex $u$ if there is a path in $G$ (a subgraph that is a path) connecting $u$ and $v$ (these two vertices are the endpoints of the path). We define $u$ to be accessible from itself by the path $P_1$. (So accessibility is a reflexive relation even in the empty graph.)

01.64 DO   Given a graph $G=(V,E)$, observe that accessibility is a symmetric relation on $V$.

01.66 ORD (8 points)   Given a graph $G=(V,E)$, prove that accessibility is a transitive relation on $V$. Use the definition of accessibility given in 01.62 above. Proofs based on other definitions will not be accepted. Clarity of the proof matters. DO NOT LOOK IT UP.

01.70 Bonus (10+4 points)   (a) Prove: a triangle-free graph has at most $\lfloor n^2/4\rfloor$ edges.   (b) Prove that this bound is tight for every $n$, i.e., the upper bound can be attained.
Hint for part (a): induction on $n$ in steps of 2: delete an edge.
Clarity of the proof is paramount. DO NOT LOOK IT UP.

01.74 Bonus (10+4 points)   (a) Let $G=([n],E)$ be a graph on the vertex set $[n]=\{1,2,\dots,n\}$. Let $A$ denote the adjacency matrix of $G$. Prove: $G$ is connected if and only if all entries of the matrix $(I+A)^{n-1}$ are positive. Here $I$ denotes the $n\times n$ identity matrix.
(b) Find a connected graph such that $(\forall m\ge 1)($not all entries of $A^m$ are positive$)$.

01.76 DO   Prove: a graph $G=(V,E)$ is a tree if and only if $(\forall u,v\in V)(\exists! u--v$ path$)$, i.e., every pair of vertices is connected by a unique path). "Unique" means there is exactly one.

01.78 ORD (14 points; lose 3 points for each mistake)   DM 6.1.34 (draw all 7-vertex trees). Number your trees for easy reference by the grader. State, how many trees you have found. No proofs are required. You can draw your trees by hand, there is no need to study graph drawing software.

01.81 Bonus (14 points)   Let $T$ be a tree. Prove: all longest paths in $T$ share a vertex.

01.82 Challenge   Find a connected graph in which the longest paths do not share a vertex. DO NOT LOOK IT UP (or if you did, do not hand it in). (This is a negative answer to a question asked by Tibor Gallai, 1966. The smallest known example has 12 vertices.)

01.83 OPEN PROBLEM   Is it true that in a connected graph, every three longest paths share a vertex? (Asked by Tudor Zamfirescu, 1980s.)

01.85 ORD (6 points)   Let $G$ be a graph. Prove: $G$ or $\Gbar$ (the complement of $G$) is connected.

01.88 DO   Let $V$ be an $n$-set (i.e., a set of $n$ elements). Prove: the number of graphs on vertex set $V$ (i.e., the number of graphs whose set of vertices is $V$) is $\displaystyle{2^{\binom{n}{2}}}$.

01.91 ORD (9+8 points)   DMmini 6.1.12(a)(b) (estimating the number of non-isomorphic graphs of order $n$).

01.94 Challenge (asymptotic number of non-isomorphic graphs of order $n$).   DMmini 6.1.12(c)

01.97 Challenge (maximum number of triangles for a given number of edges)   (a) For a graph $G$, let $m_G$ denote the number of edges and $t_G$ the number of triangles. Prove: For all graphs $G$ we have $t_G\le (\sqrt{2}/3)\cdot m_G^{3/2}$.   (b) Prove that this bound is asymptotically tight in the following sense: for every $n$ there is a graph $G_n$ with $n$ vertices such that $t_{G_n} \sim (\sqrt{2}/3)\cdot m_{G_n}^{3/2}$.

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

01.103 ORD (7 points)   ASY 5.12 (asymptotics of $\binom{2n}{n}$). Use Stirling's formula.

01.XX  

01.XX  

01.XX  

More to follow. Please check back later.