Class #18, Thu, May 27
18.05 MATERIAL COVERED
Shannon capacity continued. Lovász: Orthonormal representation
of graphs. Def of the Lovász $\vartheta$ function
as a minimum. Proof that $\Theta(G)\le\vartheta(G)$.
Dual characterization, as maximum with respect to ONR of $\Gbar$.
Positive semidefinite matrix characterization.
Spectral characterization. Corollary: Hoffman's spectral lower bound
on chromatic number. Self-complementary graphs. For vertex-transitive
self-complementary graphs, $\Theta=\vartheta=\sqrt{n}$.
Hamiltonicity conjecture for connected vertex-transitive
graphs: only five counterexamples known. Guaranteed lower
bound on length of longest cycle: $\sqrt{3n}$ (LB 1977). Sketch of proof.
Local expansion of vertex-transitive graphs (LB 1980, LB-Szegedy 1982).
18.25 DEF The Kronecker product of vectors $v=(v_1,\dots,v_k)^T$ and $w=(w_1,\dots,w_{\ell})^T$ is the vector $v\otimes w=(v_iw_j | 1\le i\le k,\ 1\le j\le \ell)^T$. So this vector has $k\ell$ coordinates which we arrange lexicographically: $(v_1w_1,v_1w_2,\dots,v_1w_{\ell},v_2w_1,v_2w_2,\dots,v_2w_{\ell}, \dots,v_kw_1,v_kw_2,\dots,v_kw_{\ell})^T$.
18.27 DO Let $x,u\in \rrr^k$ and $y,v\in\rrr^{\ell}$. Then $(x\otimes y)^T(u\otimes v)=(x^Tu)(y^Tv)$.
18.30 DEF (László Lovász, 1979) An Orthonormal Representation (ONR) of a graph $G([n],E)$ is an assignment of unit vectors $u_1,\dots,u_n\in \rrr^d$ $(\|u_i\|=1)$ to the vertices such that if $i\neq j$ and $i\not\sim j$ then $u_i^T u_j=0$ ($u_i$ and $u_j$ are orthogonal). Let us call the smallest dimension $d$ for which an ONR exists the L-dimension of the graph. (This term is not standard.) For this sequence of problems we shall denote this quantity $\dim(G)$.
18.32 DO Verify: $\dim(K_n)=1$, $\dim(\Kbar_n)=n$.
18.34 ORD (9 points) Prove: $\dim(G)\le\chi(\Gbar)$.
18.36 Bonus (12 points) Prove: $\dim(G) \ge \Theta(G)$.
18.38 DO $\dim(C_5)=3$.
18.40 CH Determine $\dim(C_5^2)$. (I do not know the answer - LB.)
18.70 ORD (8 points) Let $\gamma(k,\ell)$ denote the number of independent sets in the grid $P_k\Box P_{\ell}$. Prove that for every $k\ge 1$, the limit $\lim_{\ell\to\infty} \gamma(k,\ell)^{1/\ell}$ exists. The proof should be very simple, with reference to a DO exercise. Complicated proofs will not be accepted.
More to follow. Please check back later.
UPDATE (05-26 04:30) This class was previously erroneously
labeled "Class #16". Labeling of exercises updated accordingly.
Final homework: all exercises are due Thu, Jun 3 23:00.
17.05 MATERIAL COVERED.
Analysis of Boolean functions: 2-colorings of $Q_d$. Complexity measures.
Sensitivity Conjecture (Noam Nisan - Mario Szegedy, $\sim$ 1992).
Gotsman-Linial (1992) equivalent version stated: minimum max degree
of induced subgraphs on more than half the vertices of $Q_d$.
Chung-Füredi-Graham-Seymour upper bound $\sqrt{n}$ (1988) stated.
Hao Huang: matching lower bound ($\sqrt{n}$) (2019) - settled
Sensitivity Conjecture. Proof: spectral analysis.
Graph minors. Wagner's Conjecture, now theorem by
Neil Robertson and Paul Seymour (1984-2006: 20 papers, 500 pages):
every minor-closed class of graphs characterized by a finite
set of excluded minors (stated).
17.25 STUDY the new handout "Weil's character sum estimates and the
universality of Paley graphs" (WEIL) (Click "Handouts" on the banner.
Make sure to refresh your browser.)
In solving an exercise from WEIL, you may use without proof
any of the lower-numbered exercises from WEIL. If you don't
feel comfortable with the concept of finite fields of
prime-power order, replace $q$ by $p$, a prime number.
17.30 DO Solve all exercises in WEIL.
17.33 ORD (7+5 points)
(a) WEIL 3.10 (character at primitive root).
(b) WEIL 3.11 (number of characters)
17.36 ORD (14 points) WEIL 4.2. (character sum at $a^2+1$ values)
17.39 ORD (6 points) Prove WEIL Theorem 4.3 (Weil's Theorem)
for the case $d=1$.
17.42 ORD (14 points) Prove WEIL Ex. 8.3 (e) (item (e) of the
"sketch of proof," Equation (8) on page 10.
17.45 Bonus (8 points) WEIL 9.1
(consecutive non-residues mod $p$). Do not repeat a lengthy proof;
instead, use a result proved in class and in WEIL.
17.47 ORD (7 points) WEIL 9.4 (Paley tournament of order 7 is
2-paradoxical)
17.60 ORD (9 points) Let $G$ be a graph with
average degree $d > 0$.
Prove: $G$ has a subgraph with minimum degree $> d/2$.
17.65 DEF Let us call a graph degree-critical
if the contraction of any edge decreases the average degree.
(This is not a standard term.)
17.67 DO (a) For $k\ge 4$, the cycle $C_k$ is not
degree-critical. (b) For $n\ge 2$, the clique $K_n$ is degree-critical.
(c) Every tree with $n\ge 2$ vertices is degree-critical.
17.70 ORD (16 points) Let $G$ be a degree-critical graph
with average degree $d$. Let $N(x,y)$ denote the set of
common neighbors of vertices $x$ and $y$. Prove: if $x\sim y$ then
$|N(x,y)|+1 > d/2.$
17.72 ORD (12 points) &bsp; Prove: If $G$ is a triangle-free connected
degree-critical graph then $G$ is a tree.
17.75 NOTATION Let $G$ and $H$ be graphs. We write
$H \preccurlyeq G$ if $H$ is a minor of $G$, i.e., if $H$ is
isomorphic to a contraction of a subgraph of $G$. (Contraction
means we repeatedly contract edges.) For instance,
$G$ is not planar if and only if $K_5\preccurlyeq G$ or
$K_{3,3} \preccurlyeq G$. We also know that $K_5\preccurlyeq$
Petersen's graph.
17.77 DEF The Hadwiger number $H(G)$ is the
greatest $h$ such that $K_h \preccurlyeq G$. For instance,
the Hadwiger number of a planar graph is $\le 4$ and the
Hadwiger number of the Petersen graph is at least 5.
17.80 Bonus (16 points) Prove that there exists a constant $C$
such that the following holds for all $k\ge 1$. If $G$ is a
graph with average degree $\ge C^k$ then $H(G)\ge k$.
State your value of $C$. Make it as small as you can.
17.100 DEF A Boolean function in $d$ variables
is a function $f:\{0,1\}^d\to\{0,1\}$.
17.102 EXAMPLES. (a) PARITY$_d(x_1,\dots,x_d)=\sum_{i=1}^n x_i \pmod 2$.
This is also called the "exclusive or" (XOR) function.
(Here $x_1,\dots,x_d$ are Boolean variables: $x_i\in\{0,1\}$.)
(b) MAJORITY$_d(x_1,\dots,x_d)=1$ if $\sum_{i=1}^n x_i > d/2$,
and 0 otherwise. (c) Let $d=\binom{n}{2}$ and let our
Boolean input encode the adjacency matrix of a graph. Let
$f(x_1,\dots,x_d)=1$ if the graph encoded by the Boolean string
$(x_1,\dots,x_d)$ is planar. (Of course, in this example
we could use any graph property, like "3-colorable" or "perfect,"
instead of "planar" to produce other Boolean functions.)
17.104 Notice that a Boolean function in $d$ variables
is the same as a 2-coloring of the vertices of the $d$-dimensional
cube $Q_d$, say red/blue, where "red" correspinds to
value 1 and "blue" to value zero. (The coloring need not
be legal in the sense of chromatic graph theory.)
17.106 DEF A multilinear monomial in the
real varlables $x_1,\dots,x_n$ is a product of a subset of
the variables: for $I\subseteq [n]$ we have the monomial
$x_I = \prod{i\in I} x_i$. Note that $x_{\emptyset}=1$.
So there are $2^n$ multilinear monomials.
17.108 DO Example:
$8\cdot x_1x_5x_6-\sqrt{2}\cdot x_2x_4x_5x_7$.
17.110 DEF
The degree of such a polynomial is the largest degree of
monomials appearing with nonzero coefficient. For instance,
in the previous example, the degree is 4. If all coefficients are zero
then the degree is $-\infty$.
17.112 DEF We say that a real polynomial $p$ in $d$ variables
represents the Boolean function $f$ in $d$ variables if
for all $(0,1)$-assignments to the variables, $x_i\mapsto a_i$
$(a_i\in \{0,1\})$, we have $f(a_1,\dots,a_d)=p(a_1,\dots,a_d)$.
In other words, $f$ is the restriction of $p$ to the cube $Q_d$.
17.114 DO Verify:
PARITY$_3(x_1,x_2,x_3)=x_1+x_2+x_3-2x_1x_2-2x_1x_3-2x_2x_3+4x_1x_2x_3$.
17.116 Bonus (14 points) Prove: every Boolean function is
uniquely representable as a multilinear polynomial.
In other words, for every Boolean function $f$ there
exists a unique (one and only one) multilinear polynomial $p$
such that $p$ represents $f$.
17.118 DEF The degree of a Boolean function $f$ is
the degree of the multilinear polynomial representing $f$.
17.120 DO Let $f$ and $g$ be Boolean functions
in $d$ variables. (a) Prove: $\deg(fg)\le \deg(f)+\deg(g)$.
(b) Find two Boolean functions, $f$ and $g$,
in $d$ variables, such that $\deg(fg) < \deg(f)+\deg(g)$.
17.122 DEF A decision tree to evaluate a given
Boolean function at a hidden input held by an "oracle" is
a strategy to ask yes/no questions of the form "$x_i\stackrel{?}{=}1$"
to the oracle with goal to learn the value of $f$ at the hidden
input with the minimum possible number of queries. The
decision tree complexity $D(f)$ is defined as the
minimum over all strategies of the maximum over all inputs
of the number of queries required.
17.124 CH Prove: the decision tree complexity of planarity
of a graph with $n$ vertices is $\binom{n}{2}$ (every strategy
needs to ask the adjacency of all pairs of vertices in the worst case).
17.126 CH Find an infinite sequence of
Boolean function $f_d$ in $d$ variables that
depends on each of the variables, yet $D(f_d)\sim \log_2 d$
(only a tiny fraction of the variables need to be queried).
Define what it means that a function depends on each of the
variables.
17.128 Bonus (15 points) Let $f$ be a Boolean function.
Prove: $\deg(f) \le D(f)$.
17.130 CH Let $f$ be a Boolean function. Prove:
Prove: $D(f) = O((\deg(f)^3)$.
17.132 DEF Let $f:\{0,1\}^d\to\{0,1\}$ be a Boolean function
and $x\in\{0,1\}^d$. The sensitivity of $f$ at $x$, denoted
$s(f,x)$, is the number of those inputs $x'$ that differ from $x$
in exactly one coordinate and $f(x')\neq f(x)$. (So $0\le s(f,x)\le d$.)
17.134 DO (a) Prove that $s($PARITY$_d,x)=d$
for every input $x\in\{0,1\}^d$. (b) Prove: if
$f$ is a Boolean function in $d$ variables and $s(f,x)=d$
for every input $x$ then $f$ is either PARITY$_d$ or its negation.
17.136 DO Let $d$ be odd. Prove:
for every input $x\in\{0,1\}$ we have $s($MAJ$_d, x)=(d+1)/2$ or $0$.
17.138 DEF The sensitivity of the Boolean
function $f$ is $s(f)=\max_x s(f,x)$ where $x$ ranges over
all inputs to $f$.
17.140 DEF Let us associate the following
spanning subgraph $H_f$ of $Q_d$ with the Boolean function
$f:\{0,1\}^d\to \{0,1\}$.
The set of vertices of $H_f$ is $V(H_f)=V(Q_d)=\{0,1\}^d$.
An edge $\{x,x'\}\in E(Q_d)$ belongs to $E(H_f)$ if
$f(x)\neq f(x')$.
17.141 DO $s(f,x) = \deg_{H_f}(x)$
and $s(f)=\deg_{\max}(H_f)$.
17.142 DEF We say that two functions $f,g"\Omega\to\rrr^+$
are polynomially related if
each of them if less than some polynomial of the other:
$(\exists$ polynomial $p)(\forall x\in\Omega)(f(x)\le p(g(x))$ and
$g(x)\le p(f(x))$.
17.143 COMMENT The degree, the decision tree complexity, and a number
of other complexity measures of Boolean functions have long been known
to be polynomially related (Nisan-Szegedy, see 17.128 and 17.130).
For a long time, sensitivity was notable exception.
17.144 ORD (12 points) For every Boolean function $f$ we have
$s(f)\le D(f)$.
17.150 Sensitivity Conjecture (Noam Nisan and Mario Szegedy, 1992)
There exists a constant $c$ such that for all Boolean functions $f$
we have $\deg(f) \le (s(f))^c$.
17.152 Theorem (Craig Gotsman-Nathan Linial, 1992). The Sensitivity
Conjecture is equivalent to the following statement.
In a major recent breakthrough, this statement was
verified by Hao Huang with $c=1/2$.
17.154 THEOREM (Hao Huang, 2019)
Let $H$ be an induced subgraph of $Q_d$ on more than half the vertices.
Then $\deg_{\max}(H)\ge \sqrt{d}$.
17.156 This bound is tight by a 1988 result by
Fan R. K. Chung, Zoltán Füredi, Ronald L. Graham,
and Paul Seymour: $Q_d$ has an induced subgraph on
more than half of its vertices with maximum degree
$\le \lceil\sqrt{d}\rceil$.
This result was recently generalized to Hamming graphs
(Cartesian powers of $K_t$) by UChicago undergraduate Dinding Dong
in her REU work directed by the instructor.
17.158 Theorem (Dingding Dong, 2020)
Let $G$ be the Hamming graph $H(t,d)$
($d$-fold Cartesian power of $K_t$) (so $G$
has $t^d$ vertices). Then $\alpha(G)=t^{d-1}$. Let $H$
be an induced subgraph of $G$ on more than $\alpha(G)$
vertices. Then $\deg_{\max}(H) \le \lceil\sqrt{d}\rceil$.
Dong's paper appeared in the
Journal of Graph Theory.
It is also available on the
arXiv.
17.160 Open question. True or false:
There exists a constant $c > 0$ such that
for every induced subgraph $H\subset H(k,d)$
with more than $\alpha(H(k,d))$ vertices,
$\deg_{\max}(H) \ge d^c$.
Next we discuss the steps of Huang's proof.
17.165 DEF Let $G=([n],E)$ be a graph.
We say that the $n\times n$ matrix $A$ is a
$\pm$-adjacency matrix of $G$
if $a_{ij}=a_{ji}$ (the matrix is symmetric)
and if $i\not\sim j$ then $a_{ij}=0$ and if
$i\sim j$ then $a_{ij}=\pm 1$.
17.167 DO Verify: The number of $\pm$-adjacency matrices
of a graph with $m$ edges is $2^m$.
17.169 DO Let $A$ be a $\pm$-adjacency matrix of the graph $G$.
Then $\trace(A)=0$.
17.171 ORD (7 points) Let $A$ be a $\pm$-adjacency matrix of the graph $G$.
Let the eigenvalues of $A$ be $\lambda_1\ge\dots\ge\lambda_n$.
Then $\deg_{\max}(G) \ge \max_{i=1}^n |\lambda_i|$.
17.175 DO $Q_d$ has a $\pm$-adjacency matrix
$A_d$ such that $A_d^2 = dI$ (where $I$ denotes the
$2^d\times 2^d$ identity matrix).
17.177 ORD (9 points)
Based on the exercises above (17.169-17.175)
complete the proof of Huang's Theorem (17.154).
Clearly reference each statement you are using.
MAJOR UPDATE (05-27 04:30) Due to multiple errors, starting
with DEF 17.200, this entire section (17.200-17.222) has been updated.
17.200 DEF Let $f,g:\nnn\to \rrr^+$ be functions that assign
positive real values to each positive integer. We say that
$f$ is a supermultiplicative arithmetic function if
$(\forall a,b\in\nnn)(f(a+b)\ge f(a)f(b))$. We say that $g$ is
a submultiplicative arithmetic function if
$(\forall a,b\in\nnn)(g(a+b)\le g(a)g(b))$.
17.202 Fekete's Lemma.
(a) Let $f:\nnn\to \rrr^+$ be a supermultiplicative
arithmetic function.
Then $\lim_{n\to\infty}\ (f(n))^{1/n}$ exists and is
equal to $\sup_n \ (f(n))^{1/n}$.
17.203 DO Prove Fekete's Lemma. Do not give a separate
proof of (b) but deduce it directly from (a).
17.204 DEF Let $G, H$ be graphs. We define the
strong product $G\cdot H$ as follows.
In a graph, let $a\simeq b$ denote the circumstance that
vertices $a$ and $b$ are either adjacent or equal.
We write $G^k$ for $G\cdot G\cdot \ldots \cdot G$ ($k$ times).
17.205 DO To checl your understanding of the definition,
verify these examples.
(a) Viewing the vertices of $P_8 \cdot P_8$
as the cells of the chessboard, adjacency corresponds to the King's moves.
(b) Analogously, $C_k\cdot C_{\ell}$ can be viewed as the
$k\times \ell$ toroidal chessboard with the King's moves
correspoding to adjacency. (c) $K_r \cdot K_s = K_{rs}$.
(d) $\Kbar_r \cdot \Kbar_s = \Kbar_{rs}$.
17.206 DEF We say that the function $f$ is a graph invariant
if $f$ assigns objects (numbers, strings) to graphs such that
if $G\cong H$ then $f(G)=f(H)$. (So the domain of such a function
is the class of all finite graphs.) Examples: $\alpha$, $\chi$,
number of triangles, spectrum. If the values of the invariant $f$
are numbers then we say that $f$ is a graph function.
(The spectrum is a graph invariant that is not a graph function.)
17.207 DEF Let $f,g$ be graph invariants that assign
positive real numbers to graphs. We say that $f$ is a
supermultiplicative graph function if $f(G\cdot H)\ge f(G)f(H)$
for all pairs $(G,H)$ of graphs. We say that $g$ is a
submultiplicative graph function if $g(G\cdot H)\le g(G)g(H)$
for all pairs $(G,H)$ of graphs.
17.208 DO (a) Let $f$ be a supermultiplicative
graph function. Then for all graphs $G$, the limit
$\lim_{k\to\infty} \ f(G^k)^{1/k}$ exists and is equal
to $\sup_k \ f(G^k)^{1/k}$.
(b) Let $f$ be a submultiplicative graph function.
Then for all graphs $G$, the limit
$\lim_{k\to\infty} \ f(G)^{1/k}$ exists and is equal
to $\inf_k \ f(G^k)^{1/k}$.
17.210 DEF The Shannon capacity of the graph $G$
is $\Theta(G) = \lim_{k\to\infty} \ (\alpha(G^k))^{1/k}$.
17.215 DO (a) Prove that for all graphs $G,H$,
$\alpha(G\cdot H)\ge \alpha(G)\alpha(H)$.
(b) Prove that the limit that defines $\Theta(G)$ exists
and is finite.
17.216 DO Prove that for every $k$,
$\Theta(G) \ge (\alpha(G^k))^{1/k}$.
17.220 ORD (9 points) (upper bound principle)
Let $f$ be a submultiplicative graph function such that
$\alpha(G)\le f(G)$ for all graphs $G$.
Then $\Theta(G) \le f(G)$ for all graphs $G$.
17.222 ORD (9+6+4+9 points)
(a) Prove: for all graphs $G,H$ we have
$\chi({\overline{G\cdot H}})\le \chi(\Gbar)\chi(\Hbar)$.
(b) Infer from this that $\Theta(G)\le \chi(\Gbar)$.
(c) Prove: If $G$ is a perfect graph then $\Theta(G)=\alpha(G)$.
(d) Find a graph $G$ that is not perfect but satisfies
$\Theta(G)=\alpha(G)$. Prove both statements about your graph.
Do not use big theorems.
17.225 ORD (9+7 points) (a) Prove: $\alpha(G\cdot \Gbar)\ge n$.
(b) Let $q\equiv 1 \pmod 4$ be a prime power.
Prove: $\Theta(\PGr(q)) \ge \sqrt{q}$, where $\PGr(q)$
denotes the Paley graph of order $q$.
In particular, $\Theta(C_5)\ge \sqrt{5}$.
17.250 DEF Let $G=([n],E)$ be a graph and $\calC$ the set of
cliques in $G$. For $i\in [n]$, let $x_i\in\rrr$.
We define the fractional independence number $\alpha^*(G)$
by the following linear program (LP)
(optimization of a linear objective
function under a set of linear constrains):
$$ \alpha^*(G)=\max\left\{\left. \sum_{i=1}^n x_i \ \right\rvert\
(\forall i)(x_i\ge 0) \text{ and }
(\forall C\in\calC)\left(\sum_{i\in C} x_i \le 1\right)\right\}\,.$$
17.252 ORD (7 points) Prove: $\alpha^*(G) \ge \alpha(G)$.
17.254 ORD (9+5 points) Prove: (a) If $G$ is a
regular graph of degree $\ge 1$ then $\alpha^*(G)\le n/2$.
(b) If $G$ is a triangle-free
regular graph of degree $\ge 1$ then $\alpha^*(G)=n/2$.
17.260 DEF Let $G=([n],E)$ be a graph and $\calD$ the set of
independent sets in $G$. For $D\in\calD$ let $y_D\in\rrr$.
We define the fractional chromatic number $\chi^*(G)$
by the following linear program (LP):
$$ \chi^*(G)=\min\left\{\left. \sum_{D\in\calD} y_D \ \right\rvert\
(\forall D\in\calD)(y_D\ge 0) \text{ and }
(\forall i\in [n])\left(\sum_{D:i\in D} y_D \ge 1\right)\right\}\,.$$
17.262 ORD (8 points) Prove: $\chi^*(G) \le \chi(G)$.
17.264 Bonus (14 points) :
Prove: $\alpha^*(G) \le \chi^*(\Gbar)\,.$
17.266 Bonus (12 points) Prove: If $G$ is a bipartite graph then
$\alpha^*(G)=\alpha(G)$. You may use any theorems
proved in class but no other difficult results.
17.268 Bonus (9 points)
Prove: $\Theta(G)\le \chi^*(\Gbar)$.
17.270 CH Find a graph $G$ such that $\alpha(G)=\alpha^*(G)$
but $\chi^*(G) < \chi(G)$.
17.280 STUDY the Linear Programming (LP) problem and the
LP Duality Theorem from online sources.
17.282 DO (a) Verify that the LP that defines $\alpha^*(G)$
and the LP that defines $\chi^*(\Gbar)$ are each other's dual.
(b) Verify: It follows from the LP Duality Theorem
that $\alpha^*(G) = \chi^*(\Gbar)$.
So in the end we have this chain of inequalities:
$\alpha(G) \le \Theta(G) \le \alpha^*(G) = \chi^*(\Gbar)\le \chi(\Gbar)$.
17.290 CH Use the LP Duality Theorem to prove
the Ford-Fulkerson Theorem (Max-Flow-Min-Cut).
17.300 Matrix-Tree Theorem (Kirchhoff, 1848)
Let $L$ be the Laplacian of the graph $G$. Pick $1\le i\le n$.
Let $M$ be the $(n-1)\times (n-1)$ matrix obtained by deleting
the $i$-th row and the $i$-th column of $L$. Then the number of
spanning trees of $G$ is $\det(M)$. (The result does not depend on $i$.)
17.302 CH Prove the Matrix-Tree Theorem without looking
up the proof.
17.304 ORD (9 points) Use the Matrix-Tree Theorem to deduce
Cayley's formula that the number of spanning trees of $K_n$
is $n^{n-2}$.
More to follow. Please check back later.
All exercises are due Thu, Jun 3 23:00.
16.05 Notational error made in class corrected
in class notes:
let $A\subseteq V$.
The vertex-boundary of $A$ is denoted $\partial A$. However,
the subject in this class was the edge-boundary, denoted
$\delta A$.
16.10 MATERIAL COVERED.
Separation. Menger's Theorem. Edge-boundary of $A\subseteq V$:
$\delta A=E(A,\Abar)$. Isoperimetric ratio, edge-expansion rate.
Lower bound with proof: Proof.
More to follow. Please check back later.
All exercises are due Mon, May 24 at 11pm
except where a different deadline is stated.
15.05 MATERIAL COVERED. $k$-universal graphs. Explicit
construction. Quadratic residues, Paley graphs, Paley tournaments.
If $p$ is a prime, $p\equiv 1 \pmod 4$ and $p > k^24^k$
then the Paley graph of order $p$ has the $k$-universal
extension property. Proof from Weil's character sum estimate:
deterministic simulation of random bits. Chromatic index,
Vizing's Theorem (stated).
15.10 STUDY the "Paley graphs and Paley tournaments" (PALEY) handout.
In each exercise from PALEY below, you may use without proof any
lower-numbered exercises from PALEY.
15.25 DO Solve all exercises of PALEY.
15.30 ORD (8 points) PALEY 2.10
(multiplicativity of quadratic character)
15.32 Bonus (16 points, due Jun 3) PALEY 2.11
(neighboring values of the quadratic character have very little correlation)
15.35 ORD (5 points) PALEY 3.2 (adjacency symmetric relation)
15.38 DO PALEY 3.4 (symmetry of Paley graph)
15.40 ORD (5+5 points) (a) PALEY 3.5
(Paley graph self-complementary)
(b) PALEY 4.5 (Paley tournament self-converse)
15.42 ORD (6 points) PALEY 3.7 (Paley graph has diameter 2)
(Simplicity counts)
15.44 ORD (4+4 points) PALEY 3.8 (a) (c)
(number of common neighbors equal)
15.46 Bonus (7+7 points) PALEY 3.8 (b) (d)
(number of common neighbors)
15.50 Bonus (9+5+6 points) PALEY 3.9 (eigenvalues)
15.55 ORD (8 points) PALEY 4.2 (soundness of the definition
of Paley tournaments)
15.57 DO PALEY 4.4 (symmetry of Paley tournament)
15.59 DO PALEY 4.6 (in- and out-degrees of Paley tournament)
15.61 DO PALEY 4.8 (counting 2-step walks)
15.64 DO PALEY 4.10 (a) ($\pm$-adjacency matrix)
15.66 ORD (3+5 points) PALEY 4.10 (b)(c)
($\pm$-adjacency matrix)
15.68 Bonus (8+5+5 points, due Jun 3) PALEY 4.11(i)(ii)(iii)
($\pm$-adjacency matrix of the Paley tournament)
15.100 DEF A legal edge-coloring of the graph $G=(V,E)$
is a function $h:E\to\Sigma$ (where $\Sigma$ is the set of "colors")
such that if the edges $e,f\in E$ share a vertex then $h(e)\neq h(f)$.
In other words, all edges from a vertex must have different colors.
The chromatic index $\chi'(G)$ is the smallest number of
colors required for such a coloring.
15.102 DO $\chi'(G)$ is the minimum number of matchings of $G$
of which the union is $E$.
15.104 DO $\chi'(G) \ge \deg_{\max}(G)$.
15.106 THEOREM (Vadim G. Vizing, 1964)
$\chi'(G) \le 1+\deg_{\max}(G)$.
15.110 DEF A graph belongs to "class 1" if $\chi'(G)=\deg_{\max}(G)$,
and "class 2" if $\chi'(G)=\deg_{\max}+1$.
15.112 ORD (6 points) Prove: If a regular graph $G$ of
degree $\ge 1$
belongs to class 1 then $G$ has an even number of vertices.
15.115 Bonus (24 points, due Jun 3)(Kőnig's 1916 theorem)
Prove that every bipartite
graph belongs to class 1, i.e., $\deg_{\max}(G)$ colors suffice for
an edge-coloring. (You may use Kőnig's 1931 theorem, or Hall's
1936 theorem.)
15.120 ORD (6 points) Let $n\ge 3$ be odd. From 15.112
we know that $\chi'(K_n) \ge n$. Give a simple coloring of the
edges of $K_n$ with $n$ colors. (Do not use Vizing's Theorem.)
Elegance counts.
15.122 Bonus (7 points) Let $n\ge 4$ be even.
Give a simple coloring
of the edges of $K_n$ with $n-1$ colors. Elegance counts.
15.124 DO$^*$ Consider the following statement:
15.126 DO
In the late 19th century, (*) was expected to provide a path to proving
the four-color theorem. The hope was that (*) might be true without
the assumption of the elusive notion of planarity. This was
disproved by Julius Petersen (1898):
All exercises are due Mon, May 24 at 11pm
except where a different deadline is stated.
14.05 MATERIAL COVERED.
The Hoffmann-Singleton Theorem (1960) (proved): If a $k$-regular graph of
girth $\ge 5$ with $n=k^2+1$ vertices exists then $k\in\{1,2,3,7,57\}$.
Equation satisfied by adjacency matrix. Computing eigenvalues,
multiplicities. Circulant graphs, their common eigenbasis,
their eigenvalues. Spectrum of the $n$-cycle. Dual of plane
multigraph.
14.15 ORD (6 points, due May 17) Determine the dual multigraph
of a plane drawing of a tree with $n$ vertices. Prove your answer.
14.17 ORD (4 points, due May 17) The definition gives a
one-to-one correspondence between the edges of a plane graph and
the edges of its dual. What kind of edge corresponds to a bridge?
Briefly reason your answer.
14.19 Bonus (10 points, due May 17) Find an infinite sequence
of planar graphs that have exponentially many non-isomorphic duals.
More to follow. Please check back later.
All exercises are due Mon, May 17 at 11pm
except where a different deadline is stated.
13.05 MATERIAL COVERED. Homeomorphism. Jordan arc, Jordan curve.
Jordan curve theorem. Schoenflies theorem.
Plane representation of multigraphs, planar multigraphs.
Homeomorphism of graphs, topological subgraphs.
Kuratowski's Theorem: a graph is planar if and only if
it does not have a topological $K_5$ or a topological $K_{3,3}$
subgraph. Good characterization. Euler's formula (proved).
Maximum number of edges of a planar graph: $m\le 3n-6$ (proved)
and of a planar graph of girth $\ge 4$: $m\le 2n-4$.
Non-planarity of $K_5$ and $K_{3,3}$.
Graph minors. Excluded minor characterization of planarity.
Embedding graphs on surfaces (such as the torus). Euler's
formula for toroidal embeddings: $n-m+r=0$, assuming every region
is homeomorphic to an open disc.
13.50 ORD (9 points) Let $G$ be a connected graph.
Prove: If $m\le n+2$ then $G$ is planar.
13.53 ORD (8 points) Find a connected planar graph
with two plane drawings, one of which has a 3-sided region,
the other does not. Make your example as small as you can.
You do not need to prove your example is smallest.
13.56 ORD (6 points) Find a topological $K_{3,3}$
subgraph in the Petersen graph. Attach a picture, highlight the
vertices and the edges of this topological subgraph.
13.60 ORD (14 points, due May 24) Is this graph planar?
Prove your answer.
13.70 THEOREM (Euler's formula) Let $G$ be a connected graph
with $n$ vertices and $m$ edges. Let $\wt G$ be a plane representation
of $G$ with $r$ regions. Then $n-m+r=2$.
13.72 DO Reproduce the proof from class.
13.75 DO Let $G$ be a connected graph of let $\wt G$ be a
plane representation of $G$. Let $e\in E(G)$ and let $\wt e$ be the
Jordan arc corresponding to $e$. Prove: the two sides of $\wt e$
are in the same region if and only if $e$ is a bridge.
13.77 DO (Handshake formula for regions) Let $R_1,\dots,R_r$
be the regions of a plane multigraph graph $\wt G$. Let $R_i$ have
$s_i$ sides.
(Recall that bridges count twice in counting the sides of a region
that is on both sides of the bridge.) Prove:
$\sum_{i=1}^{\infty} s_i = 2m$.
13.80 DO Let $G$ be a planar graph with $n\ge 3$
vertices. Prove: $m\le 3n-6$.
13.82 DO Infer from the preceding exercise that
$K_5$ is not planar.
13.83 ORD (8 points)
Let $G$ be a planar graph with $n\ge 3$ vertices and girth $\ge 4$.
Prove: $m\le 2n-4$.
13.85 DO Infer from the preceding exercise that
$K_{3,3}$ is not planar.
13.100 Bonus (14 points, due Jun 3, 23:00)
Let $\lambda_1$ be the largest eigenvalue of the graph $G$. Prove:
$$ \lambda_1 \ge \sqrt{\frac{\sum_{x\in V} \deg(x)^2}{n}}\,.$$
More to follow. Please check back later.
All exercises are due Mon, May 17 at 11pm
except where a different deadline is stated.
12.05 MATERIAL COVERED.
Finite Markov Chains, $T=(p_{ij})$ transition matrix. $q_t$ distribution
of particle at time $t$. Evolution: $q_{t+1}=q_tT$. Ergodic MC,
convergence to stationary distribution. Naive random walk on
$d$-regular graph: $T=(1/d)A_G$, eigenvalues $\mu_i=(1/d)\lambda_i$,
$1=\mu_1\ge\dots\ge\mu_n$, $\lambda:=\max_{i\ge 2}|\lambda_i|\le d$,
$\mu:=\max_{i\ge 2}|\mu_i|=(1/d)\lambda\le 1$. Stationary
distribution: $(1/n){\mathbf 1}$.
Theorem. $\|q_t-(1/n){\mathbf 1}\|\le \mu^t$. Euclidean norm,
operator norm: $\|A\|=\max \|Ax\|/\|x\|$. Therefore,
$\|Ax\|\le \|A\|\cdot \|x\|$. For any (not necessarily square)
real matrix $\|A\|=\sqrt{|\lambda|_{\max}(A^TA)}$.
If $A^T=A$ (symmetric real matrix) then $\|A\|=\max\{|\lambda_i|\}$.
Theorem proved using common eigenbasis of $T$ and $J$.
Case $\mu=1$: if and only if $G$ disconnected or bipartite.
Avoding trouble with bipartite or near-bipartite case:
lazy random walk: $T'=(1/2)(T+I)$: all eigenvalues $\ge 0$.
$\mu' = (1+\mu_2)/2$ and $\|q'^t-(1/n){\mathbf 1}\|\le \mu'^t$.
Spectra of special classes of graphs: $K_n$, $\Kbar_n$, $\star_n$.
Next: $P_n$, $C_n$. Chebyshev polynomials of the 1st and 2nd kind.
Recurrence, roots. Recurrence for characteristic polynomial of
graphs with $(\exists v)(\deg(v)=1)$. Conclusion: recurrence for
characteristic polynomials for paths: $f_{P_0}(t)=1$, $f_{P_1}(t)=t$,
$f_{P_{n+1}}(t)=t\cdot f_{P_n}(t)-f_{P_{n-1}(t)}$. Eigenvalues:
$\displaystyle{\lambda_k=2\cos\left(\frac{k\pi}{n+1}\right)}$ $(k=1,\dots,n)$.
12.10 STUDY LinAlg Section 11.3 (Quadratic forms) and
13.1 (Operator norm).
12.20 DEF Euclidean norm of $x=(x_1,\dots,x_n)^T\in\rrr^n$:
$\|x\|=\left(\sum x_i^2\right)^{1/2}$.
12.22 DEF Operator norm of matrix $A\in\rrr^{k\times\ell}$:
$\displaystyle{\|A\|=\max_{x\neq 0} \frac{\|Ax\|}{\|x\|}}$.
12.24 DO (a) $(\forall x\in\rrr^n)(\|Ax\|\le \|A\|\cdot\|x\|)$.
(b) If $A,B$ are real matrices such that $AB$ is defined then
$\|AB\|\le \|A\|\cdot\|B\|$.
12.26 DEF Let $A=A^T$ be a real symmetric matrix
with eigenvalues $\lambda_1\ge\dots\ge \lambda_n$.
The spectral norm of $A$ is $\max_{i\ge 1} |\lambda_i|$.
12.28 ORD (8 points) Let $A=A^T$ be a real symmetric matrix.
Prove: $\|A\|$ is equal to the spectral norm of $A$.
12.30 DEF Let $A=A^T$ be a symmetric $n\times n$ real matrix.
We say that a is a positive semidefinite matrix if
$(\forall x\in\rrr^n)(x^TAx\ge 0)$.
12.32 DO Let $A=A^T$ be a symmetric real matrix.
Prove: $A$ is positive semidefinite if and only if all eigenvalues
of $A$ are non-negative: $\lambda_i\ge 0$.
12.34 ORD (3+5 points) Let $A$ be a (not necessarily square)
real matrix. Prove that $A^TA$ is (a) symmetric and (b) positive
semidefinite. Hint for (a): use the identity $(AB)^T=B^TA^T$.
12.36 ORD (8+5 points) (a) Let $A$ be a (not
necessarily square)
real matrix. Prove: $\|A\|=\sqrt{\lambda_{\max}(A^TA)}$.
(b) Calculate the norm of the matrix
$\displaystyle{\begin{pmatrix} 1 & 2\\ 3 & 4 \end{pmatrix}}$.
Review of divisibility and gcd.
All quantifiers in the following sequence of exercises about
divisibility range over the integers, so $a,b,x$, etc.
below are integers.
12.40 DEF and NOTATION Let $a,b$ be integers. We say that $a\mid b$
("$a$ divides $b$") if $(\exists x)(ax=b)$.
12.42 DO Verify: (a) $\Div(6)=\{\pm 1, \pm 2, \pm 3, \pm 6\}$.
So $|\Div(6)|=8$. (b) $\Div(-a)=\Div(a)$
(c) $\Div(1)=\{1,-1\}$. (d) $\Div(0)=\zzz$.
12.43 DEF Let $S$ be a (finite or infinite, possibly empty)
set of integers. We say that the integer $k$ is a
common divisor of $S$ if $(\forall s\in S)(k\mid s)$.
12.44 DO If $k\in\Div(a,b)$ (i.e., $k$ is a common divisor
of $a$ and $b$) then (a) $k\mid a\pm b$
(b) $(\forall x,y)(k\mid ax+by)$ ($k$ divides all integral linear
combinations of $a$ and $b$).
12.45 DO Observe: (a) $\Div(S)=\bigcap_{a\in S}\Div(a)$.
(b) $\Div(4,-6)=\{\pm 1, \pm 2\}$ (c) $\Div(\zzz)=\{1,-1\}$
(d) If $T\subseteq S$ then $\Div(T)\supseteq\Div(S)$
(e) $\Div(\emptyset)=\zzz$.
12.46 NOTATION. (a) Let $k\zzz$ denote the set of multiples
of $k$, so $k\zzz=\{kx\mid x\in\zzz\}$. (b) For $A,B\subseteq \zzz$
let $A+B=\{a+b\mid a\in A,\, b\in B\}$.
(c) So $a\zzz+b\zzz = \{ax+by\mid x,y\in\zzz\}$ is the set of all
integral linear combinations of $a$ and $b$.
Similarly, $a_1\zzz+\dots+a_k\zzz$ is the set of all integral
linear combinations $a_1x_1+\dots+a_kx_k$.
(d) For $S\subseteq \zzz$ we write $\zzz S$ for the set of
integral linear combinations of $S$, by which we mean the set
of integral linear combinations of its finite subsets.
12.47 DO Verify: (a) $42\zzz+70\zzz=14\zzz$
(b) $42\zzz\cap 70\zzz=210\zzz$.
12.48 DEF Let $S\subseteq \zzz$. We say that $d$ is
a greatest common divisor of $S$ if (a) $d\in\Div(S)$
($d$ is a common divisor of $S$) and (b)
$(\forall e\in\Div(S)(e\mid d)$ ($d$ is a common multiple of all
common divisors). We abbreviate this statement to "$d$ is a gr.c.d.
of $S$."
12.49 DO Prove: (a) $d$ is a gr.c.d.
of $S\subseteq\zzz$ if and only if $\Div(S)=\Div(d)$.
(b) If $d$ is a gr.c.d. of $S$ then $-d$ is also a gr.c.d. of $S$.
(c) If $d$ and $e$ are gr.c.divisors of $S$ then $e=\pm d$.
12.50 NOTATION If $d$ is a gr.c.d. of $S$ then we write
$\gcd(S)=|d|$. — It follows from the preceding exercise that
if a gr.c.d. of $S$ exists then $\gcd(S)$ is unique.
12.51 DO Verify: (a) $(\forall a)(\gcd(a,a)=\gcd(a,0)=|a|)$
In particular, $\gcd(0,0)=0$
(b) $(\forall k)(\gcd(k\zzz)=|k|)$
(c) $\gcd(\emptyset)=0$
(d) $\gcd(a,b)=\gcd(a,-b)= \gcd(-a,b)=\gcd(-a,-b)$
(e) $\gcd(a,b)=\gcd(a+b,b)=\gcd(a-b,b)$.
12.52 THEOREM (a) For every set $S\subseteq\zzz$ there
exists a gr.c.d. $d$ of $S$. (b) If $d$ is a gr.c.d. of $S$ then
$d\in\zzz S$ (every gr.c.d. of $S$ can be written as an integral linear
combination of $S$) (c) If $d$ is a gr.c.d. of $S$ then
$\zzz S = d\zzz$ (the integral linear combinations of $S$ are
precisely the multiples of $d$).
12.53 DO$^+$ Prove this theorem.
12.54 ORD (12 points) Let
$P=\{p^2-1 \mid p\text{ is a prime number and } p\ge 17\}$.
Determine $\gcd(P)$. Prove.
12.60 DO Let $A=A^T$ be a symmetric $n\times n$ real matrix.
Let $e_1,\dots,e_n$ be an orthonormal eigenbasis of $A$ and let
$\lambda_1\ge\dots\ge\lambda_n$ be the corresponding eigenvalues.
Let $U_i=\span(e_1,\dots,e_i)$. Prove:
$\lambda_i=\min\{R_A(x)\mid x\in U_i\}$.
12.62 DEF A multiset is a "set with repeated elements,"
like $\{\{3,5,3,3,4,5\}\}$. So this multiset is the same as
$\{\{3,3,3,4,5,5\}\}$ (the ordering does not matter), but
$\{\{3,5,3,3,4,5\}\}\neq \{\{3,4,5\}\}$. (Formally, if $U$ is our universe
(the set of all possible objects under consideration),
then a multiset of objects from $U$
is a function $f:U\to\nnn_0$ which assigns a multiplicity to each object,
where $\nnn_0$ is the set of non-negative integers.)
12.63 DEF The spectrum of a square matrix is the multiset
of its eigenvalues, each with its algebraic multiplicity.
The adjacency spectrum of a graph is the spectrum of its
adjacency matrix.
12.65 Bonus (14 points)
Let $G$ and $H$ be graphs with adjacency spectra
$\lambda_1\ge\dots\ge\lambda_n$ and $\mu_1\ge\dots\ge\mu_k$, respectively.
Given an eigenbasis of each graph, find and eigenbasis of $G\Box H$
and prove that the spectrum of the Cartesian product $G\Box H$ is the
multiset $\{\{\lambda_i+\mu_j \mid 1\le i\le n,\, 1\le j\le k\}\}$.
12.67 ORD (9 points) Determine the adjacency spectrum of
the $d$-dimensional cube, $Q_d$.
12.70 DEF Let $G=([n],E)$ be a graph. Let
$D_G=\diag(\deg(1),\dots,\deg(n))$
denote the diagonal matrix listing the degrees of the vertices.
Let $L_G=D_G-A_G$ where $A_G$ is the adjacency matrix.
$L_G$ is called the Laplacian of $G$.
Let the eigenvalues of $L_G$ be $\rho_0\le \rho_1\le\dots\le\rho_{n-1}$.
Note that we listed the eigenvalues in increasing order and started
the numbering with 0.
12.72 DO Observe that the sum of every row of $L_G$ is zero.
12.74 ORD (7+3+4 points) (a)
Let $x=(x_1,\dots,x_n)^T \in\rrr^n$.
Verify: $x^TL_Gx=\sum_{i\sim j} (x_i-x_j)^2$. This sum has $m$ terms
(so we are summing over the set of unordered pairs of adjacent vertices).
(b) Prove: $L_G$ is positive semidefinite.
(c) Prove that $\rho_0=0$.
12.76 Bonus (10 points) Prove: $\rho_1 > 0$ if and
only if $G$ is connected.
12.77 TERMINOLOGY $\rho_1$ is the Laplacian eigenvalue gap
a.k.a. the algebraic connectivity of $G$ as defined by
Miroslav Fiedler (1973) in the Czechoslovak Math. Journal.
It is the single most important spectral parameter of a graph.
This quantity governs the expansion rate of the graph.
12.80 ORD (8 points) Prove: If $G$ is a $d$-regular
graph then any eigenbasis of $A_G$ is also an eigenbasis of $L_G$, and
$\rho_i = d-\lambda_{i+1}$.
12.84 ORD (5 points) Determine the Laplacian spectrum
of $K_n$.
12.86 Bonus (15 points) Determine the Laplacian spectrum
of the star graph $\star_n$ (a.k.a. the complete bipartite graph $K_{1,n-1}$).
As always, prove.
12.88 ORD (7 points) Find the smallest connected
graph which has a Laplacian eigenvector that is not an adjacency
eigenvector. Do this with zero calculation. Include a proof
that your example is smallest.
12.93 Bonus (18 points) Let $G$ be a connected graph
of diameter $d$. Prove: $G$ has at least $d+1$ distinct adjacency
eigenvalues.
12.100 Bonus (24 points) (expansion)
Let $G=(V,E)$ be a graph. Let $A\subseteq V$. Prove:
$\displaystyle{|E(A,\Abar)|\ge \rho_1\cdot\frac{|A|\cdot |\Abar|}{n}}$.
12.103 Bonus (20 points, due May 24) (lower bound on the algebraic
connectivity)
Let $G$ be a connected graph of diameter $d$. Prove:
$\displaystyle{\rho_1 \ge \frac{1}{dn}}$.
12.110 DEF The Chebyshev polynomials of the first kind, $T_n$,
are defined by the equation $T_n(\cos\theta)=\cos(n\theta)$.
12.115 ORD (10 points) Determine $U_n(1)$. Prove.
More to follow. Please check back later.
All exercises are due Mon, May 10 at 11pm
except where a different deadline is stated.
11.05 MATERIAL COVERED.
Two early successes of the Probabilistic Method: proof of existence without
explicit construction (Erdős).
Upper bound on $\alpha(G)$ in the $\calG(n,p)$ model (proved).
Uniform case ($p=1/2$): Ramsey bound
$2^{k/2}\not\to (k+1,k+1)$ (1949) (proved).
Graphs with large girth and large chromatic number (1959) (proved).
$p\approx n^{1/g}$ where $g$ is the target girth. There will be
short cycles but their expected number can be made less than $n/4$,
so with probability $\ge 1/2$ there will be less than $n/2$ short cycles,
remove one vertex from each: retained $\ge n/2$ vertices, no short cycles,
and $\alpha$ still small. Yields $\chi > n^{1/g}/(4 \ln n)$.
11.18 THEOREM (exponential-size Ramsey graphs, Erdős 1949)
$2^{k/2} \not\to (k+1,k+1)\,.$
11.20 Compare this with the Erdős-Szekeres bound
$4^{k} \to (k+1,k+1)$.
11.22 DO Prove Theorem 11.18 based on the class notes posted
on this website.
11.25 THEOREM (graphs with large girth and large chromatic number,
Erdős, 1959)
$(\forall g)(\exists n_0)(\forall n>n_0)(\exists$ graph $G$ with $n$
vertices such that $\girth(G) > g$ and
$\chi(G) \ge \displaystyle{\frac{n^{1/g}}{4\ln n}}$.
11.27 DO Prove Theorem 11.25 based on the class notes posted
on this website.
11.30 ORD (7 points)
Prove: In the uniform ER model, whp, $\chi(G) > (\omega(G))^{100}\,.$
11.35 Bonus (7+4 points) (a) Let $G=([n],E)$ be
a connected graph with greatest eigenvalue $\lambda_1$. Let
$x=(x_1,\dots,x_n)^T$ be an eigenvector to $\lambda_1$.
Prove: if there is an automorphism $\pi$ of $G$ such that
$\pi(i)=j$ then $x_i=x_j$. (b) Show that this is false
if we do not assume connectedness. Give a counterexample where
$\lambda_1 \neq 0$. Make your counterexample as small as possible.
11.38 DO Determine the automorphism group of the
star graph $\star_n = K_{1,n-1}$.
11.40 DO (a) State the adjacency matrix
of $\star_n$. (b) Determine the rank and the nullity
of this matrix. (c) Find the greatest eigenvalue of $\star_n$.
(d) Combine all this to showing that
the spectrum of $\star_n$ is $\pm \sqrt{n}$ and $0$ with multiplicity $n-2$.
11.45 ORD (9 points) Let $G$ be a $d$-regular graph with
diameter $\ge 4$.
Prove: $\lambda_2(G) \ge \sqrt{d}$. Make it clear where you
use the diameter condition. Reason why diameter 3 does not suffice
for the argument. Make sure you make a clear distinction
between "subgraph" and "induced subgraph."
(In class I erroneously stated diameter $\ge 3$ as the condition.)
11.50 Bonus (20 points) (Courant-Fischer min-max theorem))
LinAlg 10.2.7.
Base your proof on the Spectral Theorem as stated below (8.75).
11.60 Bonus (18 points) (Interlacing) LinAlg 10.2.8.
Base your proof on the Courant-Fischer min-max theorem.
11.65 ORD (14 points) Let $G$ be a graph with
eigenvalues $\lambda_1\ge\dots\ge\lambda_n$. Prove:
If $\lambda_k > 0$ then $\alpha(G)\le n-k$.
11.70 ORD (7+7+8 points) Consider the following sequence
of matrices: $A_0=(0)$ (a $1\times 1$ matrix) and for $d\ge 1$,
$$A_d = \begin{pmatrix} A_{d-1} & I \\
I & -A_{d-1}\,.
\end{pmatrix}$$
So $A_d$ is a $2^d\times 2^d$ matrix. (Here $I$ denotes the identity
matrix of the appropriate size, which in this case is $2^{d-1}\times 2^{d-1}$.)
More to follow. Please check back later.
All exercises are due Mon, May 10 at 11pm
except where a different deadline is stated.
10.05 MATERIAL COVERED.
$k$-th power of the adjacency matrix of a digraph counts
walks of length $k$. Trace of 2nd power of adjacency
matrix of a graph: $2m$, 3rd power: 6 times the number of
triangles. Stochastic matrix, finite Markov Chain, transition
matrix $T$, transition digraph $G_T$, evolution of MC:
multiply to the right by transition matrix. Study of
evolution of MC = study of powers of a (usually very large)
matrix. Card shuffling: 52! states. Stationary distribution:
probability distribution that is a left eigenvector to transition matrix to
eigenvalue 1. 1 is a (right) eigenvalue of stochastic matrix, stationary
distribution always exists (stated), if $G_T$ strongly
connected then stationary distribution unique (stated),
period of vertex in digraph, vertices in same strong component have
same period, strongly connected digraph aperiodic if period = 1,
finite MC ergodic if transition digraph strongly connected and
aperiodic; in this case, distribution converges to stationary
(stated). Eigenvalues of graphs: $\lambda_1\ge\dots\ge\lambda_n$.
$(\forall i)(\lambda_1\ge |\lambda_i|)$. If $G$ connected then
$\lambda_1 > \lambda_2$. If $G$ $d$-regular then $\lambda_1=d$
and $\lambda_1=\lambda_2$ iff $G$ is connected. If $G$ bipartite
then $\lambda_i = -\lambda_{n-i+1}$ (spectrum symmetric about
zero). If $G$ is connected and $\lambda_n=-\lambda_1$ then
$G$ is bipartite. Period of a graph: 1 or 2; 2 iff bipartite.
Connected non-bipartite graph: $(\forall i)(\lambda_1 > |\lambda_i|)$.
$T$ uniform random walk on $d$-regular graph $G$: transition
matrix $T=(1/d)A_G$. If $G$ connected regular graph then
stationary distribution uniform. If $G$ connected,
non-bipartite then MC ergodic. Question: rate of
convergence to uniform. Thm (stated): if $q_t=(q_{t1},\dots,q_{tn})$
is the distrbution at time $t$ then $|q_{ti}-(1/n)| \le (\lambda/d)^t$
where $\lambda=\max\{|\lambda_i|: i\ge 2\}$. Eigenvalue gap $d-\lambda$
controls expansion.
10.10 STUDY DM Chap. 8 (Finite Markov Chains). Make sure to refresh
your browser, this chapter has just been updated.
The "Last update" item on the front page should show the date of
May 1, 2021. If you see a different date,
you are viewing an earlier cached version.
Please clear your cache and try again.
10.15 DO Give a one-line proof of the inequality
$\displaystyle{\binom{2n}{n} < 4^n}$ for $n\ge 1$. No factorials,
no induction.
10.25 DO Let $G$ be a digraph and $A_G$ its adjacency matrix.
Let $a_{ij}^{(k)}$ denote the $(i,j)$ entry of the $k$-th power $A_G^k$.
Prove: $a_{ij}^{(k)}$ is the number of $i\to\dots\to j$ directed walks
of length $k$ in $G$.
10.27 DO Let $G$ be a graph. Prove: (a)
$\trace(A_G)=0$ (b) $\trace(A_G^2)=2m$ (c)
$\trace(A_G^3)=6t$ where $t$ denotes the number of triangles in $G$.
10.34 Bonus (12+4 points)
Let $x_1,\dots,x_n$ be real numbers. (a) Prove:
$$\left(\sum_{i=1}^n x_i^2\right)^3 \ge \left(\sum_{i=1}^n x_i^3\right)^2\,.$$
(b) Determine, when does equality hold.
10.38 ORD (4 points) Prove:
$t_{K_n} \sim (\sqrt{2}/3)\cdot m_{K_n}^{3/2}$,
where $t_{K_n}$ denotes the number of triangles in $K_n$ and $m_{K_n}$
denotes the number of edges of $K_n$.
10.40 Bonus (16 points) (maximum number of triangles for a given
number of edges) Prove: For all graphs $G$ we have
$t\le (\sqrt{2}/3)\cdot m^{3/2}$, where $t$ denotes the number of triangles
in $G$ and, as usual, $m$ is the number of edges of $G$.
In the exercises below, a Markov Chain (MC) will always
refer to a finite Markov Chain with $n$ states.
10.50 DO (a) Prove: an $n\times n$ matrix
is stochastic if and only if its entries are non-negative and
the all-ones vector is a right eigenvector to eigenvalue 1.
10.52 ORD (7+8 points) (a) Let $A$ be a stochastic
matrix. Prove: $|\det(A)|\le 1$. (b) Find all
$n\times n$ stochastic matrices for which equality holds.
10.54 DO (a) Every permutation matrix is a stochastic matrix.
(b) The matrix $(1/n)J_n$ is a stochastic matrix (where
$J_n$ is the $n\times n$ all-ones matrix).
10.56 DEF A convex combination of vectors $v_1,\dots,v_k$
if a linear combination $\sum_{i=1}^k \alpha_i v_i$ where
the coefficients $(\alpha_1,\dots,\alpha_k)$ form a probability
distribution. A subset $S$ of a vector space over $\rrr$ is
convex if it is closed under convex combinations.
10.57 STUDY LinAlg 5.3 (Convex combinations).
10.58 DEF An $n\times n$ matrix $A$ is doubly stochastic
if both $A$ and its transpose are stochastic. In other words,
the elements of the matrix are non-negative and every row sum is 1
and every columns sum is 1.
10.59 DO (a) Prove that the set of $n\times n$
stochastic matrices is convex, i.e., prove that any convex combination
of stochastic matrices is stochastic. (b)
Prove that the set of $n\times n$ doubly stochastic matrices is convex.
10.61 CH
Prove: every doubly stochastic matrix is a
convex combination of permutation matrices.
10.65 ORD (7 points) Prove: If a MC has more than one
stationary distribution then it has infinitely many.
10.67 Bonus (9 points) Find a MC that has a unique stationary
distribution while its transition digraph (a) is not strongly connected,
(b) has a self-loop at every vertex, and (c) has two vertices with
no edge between them in either direction.
Make your transition digraph as small as possible.
Attach a picture of the MC and also state the transition matrix.
Prove the uniqueness of the stationary distribution of your MC.
10.70 ORD (5+15 points) Consider the MC with the set $[2]$
of states and the following transition probabilities:
$p_{11}=0.1$, $p_{12}=0.9$, $p_{21}=0.6$, $p_{22}=0.4$.
More to follow. Please check back later.
All exercises are due Mon, May 3 at 11pm
except where a different deadline is stated.
09.05 MATERIAL COVERED.
Proof of the Perfect Graph Theorem (Lovász 1972).
Observation: Perfect
graph contains independent set that intersects each maximum clique.
Lemma 1: If we blow up each vertex to a clique, graph remains perfect.
Lemma 2: Perfect graph contains clique that intersects each
maximum independent set. Thm follows. Matchings, matching number
$\nu(G)$. Covering set (hitting set), covering number $\tau(G)$.
$\nu\le\tau\le 2\nu$.
Theorem (Kőnig 1931): For bipartite graphs, $\tau = \nu$.
EX: Follows from Menger's Thm. Follows from Dilworth's Thm
(and therefore from Perfect Graph Thm). Kőnig's Thm
equivalent to perfectness of complements of bipartite graphs.
Philip Hall's "Marriage Theorem" discussed. Spectral graph
theory. Rayleigh quotient.
09.16 ORD (5+5 points) (a) Prove: If $G$ is a perfect
graph then $G$ has an independent set that intersects every
maximum clique. Do not use any big theorems, just the definitions.
(b) Find the smallest perfect graph in which no
independent set intersects every maximal clique.
Prove that it is perfect and has the
required property. Do not use any big theorems, just the definitions.
You do not need to prove that your graph is smallest.
09.20 Bonus (15 points) (Lemma 1 to Perfect Graph Theorem)
Let $v$ be a vertex of the graph $G$. Let us construct
the graph $G^*(v)$ by "doubling $v$" as follows: we
add a new vertex $w$ and make $w$ adjacent to $v$
and to all its neighbors.
09.24 Perfect Graph Theorem (Lovász, 1972)
If the graph $G$ is perfect then its complement $\Gbar$ is also
perfect.
09.28 Lemma 2 to Perfect Graph Theorem.
If $G$ is a perfect graph then $G$ has a clique that intersects
every maximum independent set.
09.30 ORD (7 points) Prove that the Perfect Graph Theorem
follows from Lemma 2 (09.28).
09.40 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", written a \nu in LaTeX).
A perfect matching is a matching of size $n/2$
(all vertices are matched).
09.42 DO
Verify: $\nu(K_n)=\nu(C_n)=\nu(P_n)=\lfloor n/2\rfloor.$
09.44 DO
For every $n\ge 2$, find a graph with $n$ vertices and
$n-1$ edges such that $\nu(G)=1$.
09.46 ORD (7 points) Let $M$ be a maximal matching.
Prove: $|M| \ge \nu(G)/2$.
09.55 DEF A cover of a graph $G$ is a
a set $C\subseteq V$ of vertices that "hits" every edge:
$(\forall e\in E)(\exists v\in C)(v\in e)$. 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, written in LaTeX as \tau.)
09.60 DO $C\subseteq V$ is a cover if and only
if its complement, $V\setminus C$, is an independent set.
09.62 DO Verify: $\tau(K_n)=n-1$,
$\tau(C_n)=\lceil n/2\rceil$, $\tau(P_n)=\lfloor n/2\rfloor$.
09.64 ORD (6 points, due May 10)
Let $0\le k\le n-1$. Find the maximum number of edges
of a graph with $\tau(G)=k$. (As usual, $n$ is the number of vertices.)
Your answer should be a simple closed-form expression.
Give a simple description of the extremal graph (the graph that achieves
this maximum).
09.66 DO $\nu(G)\le \tau(G)$.
09.68 ORD (6 points) Let $M$ be a maximal matching. Prove:
$\tau(G) \le 2|M|$. (Note: it follows that $\tau(G)\le 2\nu(G)$).
09.75 (Dénes Kőnig's Theorem, 1931)
If $G$ is a bipartite graph then $\nu(G)=\tau(G)$.
09.80 Bonus (11 points) Prove that Kőnig's Theorem
follows from Menger's Theorem, directed vertex-connectivity version.
09.82 DO Prove: Kőnig's Theorem follows
from Dilworth's Theorem and through this, from the Perfect
Graph Theorem.
09.84 DO Prove: Kőnig's Theorem is
equivalent to the statement that the complement of
a bipartite graph is perfect.
09.90 NOTATION For a graph $G=(V,E)$ and a set $A\subseteq V$,
we write $N_G(A)$ to denote the set of neigbors of vertices in $A$
that are not in $A$: $N_G(A)=\{v\in V\setminus A\mid
(\exists w\in A)(v\sim w)\}$.
09.92 DEF For $A\subseteq V(G)$, a perfect $A$-matching
is a matching that matches every vertex in $A$.
09.95 (Philip Hall's "Marriage Theorem", 1936)
Let $G$ be a bipartite graph with parts $P$ and $Q$, so
$V=P\dot\cup Q$. Then the following two statements are
equivalent.
Part (b) is called the Hall conditions.
09.97 DO Prove that the Hall conditions are necessary for
the existence of a perfect $P$-matching.
09.99 ORD (9 points) Prove that Hall's Theorem
follows from Kőnig's Theorem.
More to follow. Please check back later.
All exercises are due Mon, May 3 at 11pm
except where a different deadline is stated.
08.05 MATERIAL COVERED.
$k$-universal graphs. $k$-universal extrension propety implies
$k$-universality. Non-constructive proof that such a graph
with $k^2 2^k$ vertices exists (Erdős) for $k\ge k_0$.
Probabilistic method, uniform Erdős-Rényi model.
Network flows. Flow value same across all $s-t$ cuts.
Max-Flow-Min-Cut Theorem proved. Residual digraph, augmenting path.
Edmonds-Karp choice of augmenting path, complexity bound mentioned.
Spectral Theorem: symmetric real matrix has orthonormal eigenbasis.
Quadratic form associated with such a matrix. Rayleigh quotient $R_A(x)$
where $A$ is a symmetric $n\times n$ real matrix and $x\in\rrr^n$.
Extremal properties (stated): $\max_{x} R_A(x)=\lambda_1$,
$\min_{x} R_A(x)=\lambda_n$. Courant-Fischer max-min theorems (stated).
Corollary: Interlacing Theorem (stated).
08.10 STUDY LinAlg Chap. 8 (Eigenvectors and eigenvalues),
Chap. 10 (Spectral Theorem), and Section 4.1, especially Cor.
4.1.10 (Rank-Nullity Theorem).
In the linear algebra exercises below, you may use the Spectral
Theorem, but not more advanced chapters of linear algebra.
08.15 DEF The graph $G$ is $k$-universal if every graph
with $k$ vertices is isomorphic to an induced subgraph of $G$.
08.17 DO Observe that $K_k$ is not $k$-universal. Even though
every graph with $k$ vertices is a subgraph of $K_k$, those are not
induced subgraphs. Every induced subgraph of $K_k$ is complete.
08.19 DO Let $k\ge 1$. Prove: there exists a $k$-universal graph
with $\displaystyle{\le k\cdot 2^{\binom{k}{2}}}$ vertices.
08.21 DEF We say that the graph $G$ has the
$k$-universal extension property if $n\ge k$ and
the following holds:
for every pair of disjoint subsets $A,B\subseteq V(G)$
with a total of $|A\cup B|=k-1$ vertices, there exists
a vertex $x\in V(G)$ such that $x$ is adjacent to all
vertices in $A$ and $x$ is not adjacent to any of the
vertices in $B$.
08.23 ORD (10 points) Prove: If a graph $G$ has the
$k$-universal extension property then $G$ is $k$-universal.
08.28 Bonus (18 points) (universal extension property of random graphs)
Let $n = k^2 2^k$ where $k\ge 1$. Consider a random graph
$\calG_n=([n],E)$ in the uniform Erdős-Rényi
model. Prove that whp, $\calG$ has the $k$-universal
extension property (and is therefore $k$-universal).
08.30 THEOREM (Erdős) For all sufficiently large $k$
there exists a $k$-universal graph with $n=k^2 2^k$ vertices.
08.32 DO Deduce Theorem 08.30 from 08.28. Why did
we need to add "for all sufficiently large $k$" in the Theorem?
08.35 Bonus (16 points) Let $k\ge 2$. Prove: If a graph
$G$ with $n$ vertices is $k$-universal then $n > 2^{(k-1)/2}$.
08.50 Bonus (15 points) Let $G=(V,E)$ be a $k$-connected graph,
i.e., $\kappa(G)\ge k$. Let $A,B\subset V$ be two disjoint
$k$-subsets of $V$. Prove: there exist $k$ vertex-disjoint paths
connecting $A$ to $B$. (We say that an $x-y$ path
connects $A$ to $B$ if $x\in A$ and $y\in B$.) Use Menger's
Theorem (07.45). (Note. The paths you need to find are not
just internally disjoint but entirely disjoint.)
08.58 ORD (8+16 points)
(a) State the directed vertex-connectivity
version of Menger's Theorem. (b)
Deduce the directed vertex-connectivity version of Menger's Theorem
from the directed edge-connectivity version (07.105).
08.66 ORD (8 points) Deduce Menger's Theorem (undirected
vertex-connectivity version) from the directed vertex-connectivity
version.
08.73 ORD (6 points) Let $A$ be an $n\times n$
symmetric real matrix. Prove: If $x$ and $y$ are eigenvectors of $A$
to different eigenvalues then $x$ and $y$ are orthogonal,
i.e., $x^Ty=0$. The proof should be just one line.
08.75 SPECTRAL THEOREM. If $A$ is a symmetric $n\times n$
real matrix then $A$ has an orthonormal eigenbasis in $\rrr^n$.
(Check LinAlg Chap 10 for the definitions.)
08.80 DEF Let $A$ be a symmetric $n\times n$ real matrix.
The quadratic form associated with $A$ is the function
$Q_A(x)=x^TAx$ where $x=(x_1,\dots,x_n)^T\in\rrr^n$ is an
$n$-dimensional real vector, written as a column matrix.
08.82 DO If $A=(a_{ij})$ then
$Q_A(x) = \sum_{i=1}^n \sum_{j=1}^n a_{ij}x_ix_j$.
08.85 DO Let $b_1,\dots,b_n$ be an orthonormal eigenbasis
of $A$ and let $\lambda_1\ge \lambda_2\ge \dots\ge\lambda_n$ be
the corresponding eigenvalues. In other words, $b_i^Tb_j=\delta_{ij}$
(this equation expresses orthonormality)
where $\delta_{ij}$ is the Kronecker delta symbol: $\delta_{ii}=1$
and for $i\neq j$, $\delta_{ij}=0$. Moreover, $Ab_i=\lambda_i b_i$
(so $b_i$ is an eigenvector to the eigenvalue $\lambda_i$).
08.90 DO Let $v=\sum_{i=1}^n \alpha_i b_i$ be the
expansion of the vector $v\in\rrr^n$ in terms of the eigenbasis.
Then $Q_A(v) = \sum_{i=1}^n \lambda_i \alpha_i^2$.
08.92 DEF The Rayleigh quotient associated with the
real symmetric matrix $A$ is defined as
$$ R_A(x)=\frac{Q_A(x)}{\|x\|^2}$$
where $x\in \rrr^n$, $x\neq 0$, and $\|x\|=\sqrt{x^Tx}=\sqrt{\sum x_i^2}$.
08.94 ORD (9+3 points)
(Rayleigh's Principle)
Prove: (a)
$\displaystyle{\lambda_1=\max_{x\in\rrr^n,\, x\neq 0} R_A(x)}$ and
(b)
$\displaystyle{\lambda_n=\min_{x\in\rrr^n,\, x\neq 0} R_A(x)}$.
08.100 DEF Let $G$ be a graph.
By the eigenvalues of $G$ and their multiplicities
we mean the eigenvalues of the adjacency matrix $A_G$
and their multiplicities.
08.105 ORD (10+8+6+5+4)
Consider the following $n\times n$ matrix.
$$L_n(a,b) = \begin{pmatrix} a & b & b & \dots & b & b\\
b & a & b & \dots & b & b\\
b & b & a & \dots & b & b\\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
b & b & b & \dots & a & b\\
b & b & b & \dots & b & a
\end{pmatrix}$$
$L_n(1,1)$ is the $n\times n$ "all-ones matrix", denoted $J_n$.
08.110 NOTATION Let $G$ be a graph and
$\lambda_1(G)\ge\dots\ge\lambda_n(G)$ its eigenvalues
(with listed with multiplicity). (As always, $n$
is the number of vertices.) We also write $\lambda_i=\lambda_i(G)$
when there is no confusion about the graph.
08.115 ORD (5 points)
Prove: $\lambda_1(G)+\dots +\lambda_n(G)=0$.
08.120 DO (action of the adjacency matrix)
Let $G=([n],E)$ be a graph nd $A$ its adjacency matrix.
Let $x\in \rrr^n$ be a column vector. Let $y=Ax$.
Let $x=(x_1,\dots,x_n)^T$ and $y=(y_1,\dots,y_n)^T$.
Verify:
$$ y_i = \sum_{j:j\sim i} x_j\,.$$
In words: the coordinates correspond to vertices,
and each coordinate of $y$ is the sum of the
neighboring coordinates of $x$, where "neighboring"
means they are adjacent in the graph.
08.122 ORD (9 points)
Prove: $\lambda_1(G) \le \deg_{\max}(G)$.
08.125 Bonus (7 points)
Prove: $\lambda_1(G) \ge \deg_{\avg} = 2m/n$.
08.128 Bonus (8 points) Let $H$ be a subgraph of $G$.
Prove: $\lambda_1(H)\le\lambda_1(G)$.
08.135 ORD (10 points) (Herbert Wilf's Theorem)
Prove: $\chi(G) \le 1+\lambda_1(G).$
Elegance of the proof counts.
08.138 Bonus (11+5 points) (a) Prove: If $G$ is
connected then
$\lambda_1(G)$ has an all-positive eigenvector (all coordinates positive).
(b) Find a graph $G$ such that $\lambda_1(G)$ does not
have an all-positive eigenvector. Prove.
08.140 Bonus (8 points) Prove:
$(\forall i)(\lambda_1(G) \ge |\lambda_i(G)|)\,.$
MISC.
08.160 Bonus (16 points, due May 10)
Let $G$ be a 4-cycle-free graph (no $C_4$
subgraphs). Prove: $m=O(n^{3/2})$.
08.170 Bonus (12 points, due May 10)
Prove Stanley's Theorem 06.107.
08.180 ORD (6+2 points)
(rational root of polynomial with integer coefficients)
(a) Let $f(z)=a_0+a_1z+\dots+a_nz^n$ be a polynomial
with integer coefficients. Assume $a_0a_n\neq 0$. Let $p,q$ be relatively
prime integers, i.e., $\gcd(p,q)=1$. Assume $f(p/q)=0$. Prove:
$p\mid a_0$ and $q\mid a_n$. (The vertical bar means "divisor of"
so what you need to prove is that $p$ is a divisor of $a_0$
and $q$ is a divisor of $a_n$.)
More to follow. Please check back later.
All exercises are due Mon, Apr 26 at 11pm,
except where a different deadline is stated (May 3).
This problem set includes five ORD problems and one Bonus
problem due Apr 26.
07.05 MATERIAL COVERED.
Ramsey numbers. Erdős's non-constructive lower bound proved.
The PROBABILISTIC METHOD of proving the existence of certain
objects without constructing them. EXPLICIT CONSTRUCTIONS:
difficult area. $s$-$t$ connectivity, Menger's Theorem: four versions
stated (vertex-disjoint or edge-disjoint, undirected or directed).
Network flows. Kirchhoff's Law. Max-Flow-Min-Cut Theorem
(Ford--Fulkerson) (stated).
07.30 DEF (Undirected vertex-cut)
Let $s\neq t$ be two vertices of the graph $G=(V,E)$.
A set $C$ of vertices and edges is a vertex-cut between $s$ and $t$
if every $s-t$ path passes through an element of $C$.
A minimum $s-t$ vertex-cut is an $s-t$ vertex-cut of minimum size.
07.32 DEF (continued) Two $s-t$ paths are internally disjoint
if they do not share any vertices other than $s$ and $t$.
07.34 DEF The $s-t$ connectivity of the graph $G$ is the maximum
number of pairwise internally disjoint $s-t$ paths. It is denoted
$\kappa(G;s,t)$, using the Greek letter $\kappa$ ("kappa",
in LaTeX: \kappa).
07.35 DO $\kappa(G;s,t)\le \min\{\deg(s),\deg(t)\}$.
07.36 DO Verify: For every pair $s\neq t$
of vertices of $K_n$ we have $\kappa(K_n;s,t)=n-1$.
07.38 ORD (5 points, due May 3)
Let the two parts of the vertex set
of $K_{k,\ell}$ be $A$ and $B$. So $|A|=k$, $|B|=\ell$, and $A$ and $B$ are
independent sets. Let $s\in A$ and $t\in B$. Determine
$\kappa(K_{k,\ell};s,t)$.
Prove.
07.43 ORD (5 points, due Apr 26)
Let $G$ be a graph and $s\neq t$ two vertices. Let $C$ be a
minimum $s-t$ vertex-cut. Prove: $\kappa(G;s,t)\le |C|$.
07.45 Menger's Theorem (1928), undirected vertex-connectivity version.
Let $G$ be a graph and $s\neq t$ two vertices. Let $C$ be a
minimum $s-t$ vertex-cut. Then $\kappa(G;s,t) = |C|$.
07.47 DEF We say that the graph $G$ is $k$-connected
if for every pair $s\ne t$ of distinct vertices, $\kappa(G;s,t)\ge k$.
(We also say that $G$ is "$k$-vertex-connected" for the same concept
if we want to emphasize that we are not talking about edge-connectedness,
to be defined later.)
The vertex-connectivity of $G$ is the largest $k$ such that
$G$ is $k$-vertex-connected. This number is denoted $\kappa(G)$.
07.49 DO Verify that $\kappa(K_n)=n-1$ $(n\ge 2)$ and
$\kappa(C_n)=2$ $(n\ge 3)$.
07.51 DO Prove: $\kappa(G)\le \deg_{\min}(G)$.
07.53 ORD (6 points, due May 3)
Prove: the vertex-connectivity of every toroidal
grid $C_r\Box C_s$ is 4 $(r,s\ge 3)$.
07.54 DO Prove: $G$ is 2-connected if and only if every pair
of distinct vertices belongs to a cycle.
07.55 Bonus (6 points, due May 3)
Let $G$ be a graph with $n\ge 3$ vertices and no isolated vertices.
Prove: $G$ is 2-connected if and only if every pair of edges
is co-cyclic (belongs to a cycle).
07.58 DEF A bridge in a graph $G$ is an edge $e$ such that
$G-e$ has more connected components than $G$. A graph is bridgeless
if it has no bridge.
07.60 DO Prove that the following two statements are equivalent.
07.62 DO Prove: a graph $G$ is bridgeless if and only if every edge
of $G$ belongs to a cycle.
07.64 DO A 2-connected graph is bridgeless.
07.66 ORD (5 points, due Apr 26) Find the smallest connected
graph with at least two vertices that is bridgeless but not 2-connected.
07.70 Bonus (18 points, due May 3)
Prove: A graph $G$ has a strongly connected
orientation if and only if $G$ is connected and bridgeless.
07.88 NOTATION Let $G=(V,E)$ be a digraph and let $A,B\subset V$.
Let $E(A,B)=\{(a,b)\in E \mid a\in A, b\in B\}$. This is the set of
edges that originate in $A$ and end in $B$.
07.90 DEF (Directed edge-cut)
Let $s\neq t$ be two vertices of the digraph $G=(V,E)$.
An $s-t$ cut is a pair $(A,\Abar)$ of complementary
subsets of $V$ where $s\in A$ such that $t\in \Abar$.
We say that the set $E(A,\Abar)$ is the set of edges in this cut.
Note that every $s-t$ path must include at least one edge from
$E(A,\Abar)$. The size of the cut is $|E(A,\Abar)|$.
A minimum $s-t$ cut is an $s-t$ cut of minimum size.
We sometimes say "$s-t$ edge-cut" to emphasize that we are not
talking about a vertex-cut.
07.92 DEF (continued) Two $s-t$ paths are edge-disjoint
if they do not share any edges. They may share vertices (in addition
to sharing $a$ and $t$). (By an $s-t$ path in a digraph we always mean
a directed $s-t$ path, directed from $s$ to $t$.)
07.94 DEF The $s-t$ edge-connectivity
of the digraph $G$ is the maximum number of pairwise
edge-disjoint $s-t$ paths. It is denoted
$\lambda(G;s,t)$, using the Greek letter $\lambda$ ("lambda",
in LaTeX: \lambda).
07.95 DO $\lambda(G;s,t)\le \min\{\deg^+(s),\deg^-(t)\}$.
07.96 ORD (5+5 points, due Apr 26)
Recall that a digraph $=(V,E)$ is oriented if the adjacency relation
is antisymmetric, i.e., if $(u,v)\in E$ then $(v,u)\notin E$.
(a) For every $n\ge 2$, find an oriented digraph
$G$ and two vertices, $s\neq t$, in $G$, such that $\lambda(G;s,t)=n-1$.
(b) Prove: an oriented digraph cannot have more than one
such pair of vertices.
CH 07.98 For infinitely many values of $n$, construct a
vertex-transitive tournament $T_n$ such that for every pair
$(s,t)$ of distinct vertices, the value $\lambda(T_n;s,t)$ is the same.
07.103 DO
Let $G$ be a digraph and $s\neq t$ two vertices. Let $(A,\Abar)$ be a
minimum $s-t$ cut. Prove: $\lambda(G;s,t)\le |E(A,\Abar)|$.
07.105 Menger's Theorem, directed edge-connectivity version.
Let $G$ be a digraph and $s\neq t$ two vertices. Let $(A,\Abar)$
be a minimum $s-t$ cut. Then $\lambda(G;s,t) = |E(A,\Abar)|$.
07.120 DEF A flow network is a quintuple $(V,E,s,t,c)$
where $G=(V,E)$ is a digraph, $s\neq t$ are two vertices, called
the source and the sink, and $c;E\to \rrr^{\ge 0}$
a function that assigns non-negative real numbers to each edge.
For $(u,v)\in E$, the value $c(u,v)$ is called the capacity
of the edge $(u,v)$.
07.122 DEF Given a flow network $(V,E,s,t,c)$, an $s-t$ flow
is a function $f:E\to\rrr$ that satisfies the conservation law
at every vertex $v\neq s,t$. The conservation law at vertex $v$ is
defined by the equation $$\inflow(v)=\outflow(v),$$ where
$\inflow(v)=\sum_{u:(u,v)\in E} f(u,v)$ and
$\outflow(v)=\sum_{w:(v,w)\in E} f(v,w)$.
(This definition ignores the capacities. Note that we allow $f$
to take negative values.)
The value of the flow is $\val(f):=\outflow(s)-\inflow(s)$.
07.124 DEF (inflow, outflow across $s-t$ cut)
Let $(V,E,s,t,c)$ be a flow network and
$f:E\to\rrr^{\ge 0}$ an $s-t$ flow. Let $(A,\Abar)$ be an
$s-t$ cut, i.e., $A\subset V$, $s\in A$ and $t\in \Abar$.
We define
$$\inflow(A):=\sum_{(w,v)\in E,\, w\in \Abar\,,v\in A} f(w,v)$$
and
$$\outflow(A):=\sum_{(u,v)\in E\,, u\in A\,,v\in\Abar} f(u,v)$$
07.126 ORD (9 points, due Apr 26)
(a) Prove: For every $s-t$ cut $(A,\Abar)$,
$\outflow(A)-\inflow(A)=\val(f)$.
(b) Infer from (a) that $\inflow(t)-\outflow(t)=\val(f)$.
07.130 DEF Given a flow network $(V,E,s,t,c)$, a flow
$f: E\to\rrr^{\ge 0}$ is feasible if it satisfies the
constraints $$(\forall e\in E)(0\le f(e)\le c(e))\,.$$
07.132 DEF (capacity of a cut)
Let $(V,E,s,t,c)$ be a flow network and
$(A,\Abar)$ an $s-t$ cut. The capacity
of this cut is defined as
$$c(A,\Abar) := \sum_{(u,v)\in E\,, u\in A\,,v\in\Abar} c(u,v)\,.$$
Note that only the outgoing capacities appear in this sum.
07.135 ORD (6 points, due Mon, Apr 26)
Let $(V,E,s,t,c)$ be a flow network and $f$ a feasible flow.
Let $(A,\Abar)$ be an $s-t$ cut. Prove:
$$\val(f)\le c(A,\Abar)\,.$$
07.135 Max-Flow-Min-Cut Theorem (Lester R. Ford and Delbert Ray
Fulkerson, 1956)
Let $(V,E,s,t,c)$ be a flow network. Let $f$ denote feasible flows.
Then
$$ \max_f \val(f) = \min_A c(A,\Abar) \,.$$
Here the maximum is taken over all feasible flows $f$ and
the minimum is taken over all $s-t$ cuts $(A,\Abar)$.
An integral flow is a flow that takes integer values, i.e.,
$(\forall e\in E)(f(e)\in\zzz)$.
07.137 Max-Flow-Min-Cut Theorem under integral constraints
(Ford-Fulkerson).
Assume all capacities are integers. Then there exists
an optimal integral flow.
In other words, there exists an integral flow $f$ such that
$$\val(f) = \min_A c(A,\Abar) \,.$$
07.150 Bonus (16 points, due Apr 26) Derive the directed
edge-connectivity version of Menger's Theorem (07.105)
from the Max-Flow-Min-Cut theorem under integral constraints.
More to follow. Please check back later.
All exercises are due Mon, Apr 26 at 11pm
except where a different deadline is stated.
06.05 MATERIAL COVERED.
Ramsey's Theorem for graphs. Proof of the Erdős-Szekeres bound:
induction on $k+\ell$, infinitely many "base cases." Markov's
and Chebyshev's inequalities. Second moment method. Random graphs,
Erdős-Rényi model. Proof that
if the edge probability is just a bit larger than $(\ln n)/n$ then
whp there are no isolated vertices: example of the threshold phenomenon.
Digraphs, DAGs, orientations of undirected graphs. Number of
acyclic orientations: Stanley's Theorem (stated). Accessibility,
strong components.
06.08 REVIEW all of PROB.
06.12 STUDY digraph terminology from DM 6.2. WARNING:
Digraph terminology is not uniform, such basic concepts
as paths and cycles mean different things in different texts.
For this course please follow the terminology used in PROB.
06.18 DEF Let us consider an infinite sequence of
probability spaces, $(\Omega_n,P_n)$, and an event
$A_n\subseteq\Omega_n$ in each. We say that the events $A_n$
occur "with high probability," abbreviated as "whp,"
if $P_n(A_n)\to 1$ as $n\to\infty$.
06.20 ORD (6 points)
Find a probability space and a random variable $X$ such
that
(a) $X$ takes nonnegative integer values only
(b) $E(X)=100$ (c) $P(X > 0) \le 0.01$.
Minimize the size of your sample space.
06.25 ORD (second moment method, 6 points)
Let $X$ be a non-negative random variable.
Prove: (a) $\displaystyle{P(X=0) \le\frac{\var(X)}{E(X)^2}}$.
(b)
$\displaystyle{P(X \le E(X)/2) \le\frac{4\var(X)}{E(X)^2}}$.
06.28 ASYMPTOTIC NOTATION Let $a_n,b_n$ be sequences.
We write $a_n = \omega(b_n)$ if $b_n=o(a_n)$.
06.30 ORD (7+20+8+12 points)
Consider the $\calG(n,p)$ model. We also denote a random
graph selected from this distribution by $\calG(n,p)$.
Let $q(n,p)$ denote the probability that $\calG(n,p)$
contains a triangle.
(c) Let $X_n$ be number of triangles in $\calG(n,p(n)$.
Find a function $f(n,p)$ such that if $p(n)=\omega(1/n)$ then
$f(n,p(n))\to \infty$ (as $n\to\infty)$
and $P(X_n \ge f(n,p(n)))\to 1$. Make your function $f(n,p)$
grow as fast as you can make it. In other words,
whp, there will be a lot of triangles.
This shows that at the threshold when triangles show up,
and in fact many of them do, they will still be
isolated from each other. In fact, they will not even belong
to the same connected component.
06.33 Bonus (8 points) (Previous problem
continued) Prove: If $p(n)=o(1/n)$
then, whp, $\calG(n,p)$ is a forest.
06.38 Bonus (6+9 points) (a) Let $\epsilon > 0$.
Prove: in the $\calG(n,1/2)$ model, whp, the degree
of every vertex will be in the interval $(n/2)(1\pm\epsilon)$.
(b) Make $\epsilon=\epsilon(n)$ depend on $n$.
Find a function $\epsilon(n)\to 0$ such that part (a) still
holds. Make $\epsilon(n)$ approach zero as fast as you can
make it. Do not use any results in probability theory that
are not discussed in PROB.
06.50 CONSTRUCTION (Zsigmond Nagy's graphs, 1973)
Let $k\ge 7$. Nagy's graph $NG_k$ has $\binom{k}{3}$
vertices, labeled by the 3-subsets of $[k]$:
$V(NG_k)=\{v_A \mid A\subseteq [k], |A|=3\}$. Two
vertices, $v_A$ and $v_B$, are adjacent, if $|A\cap B|=1$.
06.52 Bonus (10+10+5 points) Show that
(a) $\alpha(NG_k)=O(k)$ and
(b) $\omega(NG_k)=O(k)$.
(c) Show that Nagy's graphs demonstrate
the relation $n\not\to (cn^{1/3}, cn^{1/3})$
for some constant $c > 0$. State the value of $c$
you get; make it as small as you can.
06.55 DO DM 6.2.16 (accessibility by a walk
is the same as accessibility by a path; therefore
accessibility is a transitive relation).
06.57 DO DM 6.2.17 (mutual accessibility is an
equivalence relation)
06.59 DO DM 6.2.22 (every tournament has a Hamilton path)
06.61 DO DM 6.2.23 (every strongly connected tournament
has a Hamilton cycle)
06.63 ORD (9 points) DM 6.2.25 (DAGs have topological sort)
06.65 DO Prove: (a) A digraph with $n$ vertices has
at most $n!$ topological sorts. (b) Which digraph
has exactly $n!$ topological sorts?
06.67 Bonus (6 points) DM 6.2.27 (lower bound on the number
of topological sorts of the divisibility digraph)
06.69 DO Prove: A tournament
has at most one topological sort.
06.71 ORD (7 points) Determine the minimum number of edges
of a DAG with $n$ vertices such that the DAG has a unique
topological sort. Prove.
06.75 DEF A digraph is transitive if
for every three distinct vertices $u,v,w$, if
$u\to v$ and $v\to w$ are edges then $u\to w$
is also an edge.
06.77 NOTATION Let us write $n\stackrel{T}{\to} k$ if every
tournament with $n$ vertices contains a transitive subtournament
with $k$ vertices. (Note: this is not standard notation.)
06.79 Bonus (15 points) Prove: $2^k \stackrel{T}{\to} k+1$.
06.81 Bonus (20 points) Demonstrate by an explicit construction
that $3^k \stackrel{T}{\not\to} 2^k+1$ for all $k\ge 0$.
06.90 Bonus (12+6 points) Assume the graph $G$ has an
orientation $\vec G$ such that in $\vec G$, every vertex has
out-degree $\le k$. (a) Prove: $\chi(G)\le 2k+1$.
(b) Prove that this bound is tight for all $k$.
06.95 NOTATION Let $G=(V,E)$ be a digraph and let $A,B$ be two
disjoint subsets of the set of vertices. Then $E(A,B)$ denotes
the set of edges going from $A$ to $B$:
$E(A,B)= \{(u,v)\in E\mid u\in A, v\in B\}$.
06.96 DO Prove: a digraph $G=(V,E)$ is strongly
connected if and only if for all nontrivial subsets $A$ of $V$
(i.e., $A\neq emptyset$ and $A\neq V$) the set $E(A,\Abar)$ is
not empty.
06.97 DEF (symmetrization) We can turn a digraph into
a graph by ignoring orientation and self-loops. Formally, let
$G=(V,E)$ be a digraph. Define the graph $\wt{G} = (V,\wt{E})$
by making vertices $u\neq v\in V$ adjacent in $\wt G$
if $(u,v)\in E$ or $(v,u)\in E$ (or both). We call $\wt G$ the
symmetrization of $G$.
06.98 DEF We say that a digraph $G$ is weakly connected
if its symmetrization $\wt G$ is connected.
06.99 ORD (12 points) Let $G$ be a digraph with the
property that for every vertex we have $\deg^-(v)=\deg^+(v)$.
Prove: If $G$ is weakly connected then it is strongly connected.
06.105 DEFINITION An acyclic orientation of a graph
is an orientation that is a DAG. Let $\acyc(G)$ denote the number
of acyclic orientations of the graph $G$.
One of the most surprising combinatorial identities
connects this quantity to the chromatic polynomial.
06.107 Theorem (Richard Stanley)
For every graph, $\acyc(G) = (-1)^n P(G,-1)$.
Here $n$ is the number of vertices and $P(G,x)$
is the chromatic polynomial of $G$.
06.110 ORD (12 points) Verify Stanley's Theorem
for $K_n$, $\Kbar_n$, and all trees, by explicitly
computing the chromatic polynomial as well as the
number of acyclic orientations.
More to follow. Please check back later.
All exercises are due Mon, Apr 19 at 11pm
except where a different deadline is stated.
05.05 MATERIAL COVERED.
Diameter of graphs. Diameter of random graphs in the uniform
Erdős-Rényi model. "Almost all graphs" have
diameter 2. Probability of existence of an isolated vertex
when the edge probability is small (non-uniform model).
Evolution of random graphs. Threshold phenomena.
Ramsey theory, Erdős-Rado arrow symbol $n\to (k,\ell)$.
Baby Ramsey Theorem: $6\to (3,3)$. $5\not\to (3,3)$.
05.10 STUDY The Chernoff (Bernstein) bounds in PROB, Section 7.11.
So by now you will have studied the entire PROB handout.
RAMSEY THEORY
05.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}$.
05.17 ORD (4 points)
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.)
05.20 DO (Baby Ramsey) $6\to (3,3)$. Review proof
from class.
05.22 DO $5\not\to (3,3)$.
05.25 ORD (4+7 points)
(a) Define the symbol $n\to (q,r,s)$.
(b) Prove: $17 \to (3,3,3)$.
05.27 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.
05.30 Theorem (Erdős-Szekeres, 1934)
Let $k,\ell \ge 1$. Then
$$ \binom{k+\ell}{k} \to (k+1,\ell+1) \,. $$
05.32 DO (before Thursday's class, 4-15)
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?
05.34 Bonus (12 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.
05.36 ORD (5 points) Infer from the Erdős-Szekeres Theorem
that $4^n \to (n+1,n+1)$.
05.38 ORD (8 points) Prove: $n^2 \not\to (n+1,n+1)$.
MISC.
05.50 Bonus (20 points, due Apr 26)
Prove: If $G$ is a vertex-transitive graph
then $\alpha(G)\cdot\chi(G) \le n(1+\ln n)\,.$
05.53 ORD (8 points) Construct two random variables that are
uncorrelated but not independent. Make your sample space as
small as possible. You do not need to prove that your sample
space is smallest possible. Make sure to give a clear definition
of your probability space (sample space, probability distribution).
05.56 ORD (9+4 points)
(a) Construct a graph $G=(V,E)$, two cycles, $C$ and $D$
in $G$, and three edges, $e, f$, and $g$ in $G$ such that
$e, f\in E(C)$ and $f,g\in E(D)$, and in the symmetric
difference graph $H=(V,E(C)\triangle E(D))$, the edges
$e$ and $g$ are in different connected components.
Make your graph as small as possible. (b) Prove that your
graph is smallest possible.
05.59 Bonus (16 points) Find a perfect graph $G$ such that
neither $G$ nor its complement is a comparability graph.
Prove. Make your graph as small as you can. You do not
need to prove that it is smallest possible.
05.62 (NO) DEF Look up the definition of planar graphs.
05.64 FACTS 1. Every subgraph of a planar graph
is planar. 2. Every planar graph has a vertex
of degree $\le 5$ (if it has a vertex at all).
3. Every tree is planar.
05.66 FOUR COLOR THEOREM Every planar graph is
4-colorable.
05.68 ORD (9 points) Prove the 6-color theorem: every planar
graph is 6-colorable. Do NOT use any results we did not prove
in class, except that you may use some of the facts stated in 05.64.
RANDOM GRAPHS
05.80 ORD (14 pts) Let $\calG_n$ be a random graph in
the uniform Erdős-Rényi model. Let $[n]$ be the
set of vertices of $\calG_n$. Let $n\ge 4$. Consider the events
$A_n = ``\deg(1)=3$” and $B_n = ``\deg(2)=3$”.
All exercises are due Mon, Apr 19 at 11pm
except where a different deadline is stated.
04.05 MATERIAL COVERED.
Maximum independent set, greedy bound. Connection to greedy coloring bound.
Extremal Graph Theory, $\ex(n,H)$ notation. Mantel's Theorem:
$\ex(n,K_3)=\lfloor n^2/4\rfloor$, two proofs: by induction with
steps of two; and using the inequality between the arithmetic and
quadratic mean. Complete multipartite graphs.
Turán's Theorem, Turán's graph $T(n,r)$:
$\ex(n,K_{r+1})=|E(T(n,r))|$. Proof: saturation,
induction in steps of $r$. Consequence: stronger than greedy
lower bound on independence number. Even stronger lower bound:
Caro-Wei: $\alpha(G) \ge \sum 1/(1+d_i)$. Proof: analysis of a
randomized algorithm, using linearity of expectation. Random
graphs: the Erdős-Rényi model.
04.20 Greedy Independent Set algorithm
Initialize $A:=\emptyset$
04.22 ORD (5+5 points)
(a) Prove: the Greedy Independent Set algorithm
returns an independent set of size
$\displaystyle{\ge \frac{n}{1+\deg_{\max}(G)}}$.
04.35 EXTREMAL GRAPH THEORY
04.37 DO If $\chi(G) < \chi(H)$ then $G$ is $H$-free.
04.40 NOTATION. Let $n_1,\dots,n_k\ge 1$. The
complete $r$-partite graph $K_{n_1,\dots,n_r}$
has $n=n_1+\dots+n_r$ vertices, partitioned into $r$ blocks
as $V=V_1\dot\cup\dots\dot\cup V_r$ where $|V_i|=n_i$,
and two vertices are adjacent if and only if they do not belong
to the same block. In particular, for $r=2$ we get the
familiar complete bipartite graphs $K_{n_1,n_2}$.
04.42 DO The complement of $K_{n_1,\dots,n_r}$
is the disjoint union of $r$ cliques of respective sizes
$n_1,\dots,n_r$.
04.44 DO $\chi(G)=r$ if and only if $G$ is a spanning
subgraph of a complete $r$-partite graph.
04.46 DEF The $r$-partite Turán graph $T(n,r)$
is the complete $r$-partite graph $K_{n_1,\dots,n_r}$ with
$n=n_1+\dots+n_r$ where $(\forall i,j)(|n_i-n_j|\le 1)$
(the parts are as nearly equal as possible).
04.48 DO In the Turán graph $T(n,r)$, each part
has size $n_i = \lfloor n/r\rfloor$ or $\lceil n/r\rceil$.
Moreover, if $(n \bmod r)=t$ then exactly $t$ of the $n_i$
will be greater than $\lfloor n/r\rfloor$.
04.48 DO The Turán graph $T(n,r)$ is defined
uniquely up to isomorphism.
04.50 DO Among all $r$-colorable graphs with $n$ vertices,
the Turán graph $T(n,r)$, and only this graph, has the
maximum number of edges.
04.55 TURÁN'S THEOREM (1941). $\ex(n,K_{r+1})$
is equal to the number of edges of $T(n,r)$, and $T(n,r)$ is
the unique $K_{r+1}$-free graph with this number of edges.
04.57 Corollary
$\displaystyle{\ex(n,K_{r+1}) \le \left(1-\frac{1}{r}\right)\frac{n^2}{2}}$.
04.59 ORD (12 points)
Derive the corollary from Turán's Theorem.
We now prepare for the proof of Turán's Theorem.
04.63 DEF We say that the graph $G$ is saturated
with respect to the property of being $H$-free if (a) $G$
is $H$-free and (b) if we add any edge to $G$ then the graph
we obtain is no longer $H$-free. (We do not add vertices,
only edges joining existing vertices.) We also say that
such a graph is a saturated $H$-free graph.
04.65 DO Prove: every complete $r$-partite graph is
a saturated $K_{r+1}$-free graph.
04.67 DO If $G$ is an $H$-free graph then $G$ is a spanning
subgraph of a saturated $H$-free graph.
04.69 DO If $G$ is a saturated $K_{r+1}$-free graph then
$G\supseteq K_r$.
04.72 PROOF OF TURÁN'S THEOREM.
04.77 ORD (14 points) Prove each item in the SUMMARY.
04.79 CONCLUSION. If we add up the leftmost terms in
each line of the SUMMARY, we obtain $|E(G)|$. If we add
up the rightmost terms in each line, we obtain $|E(T(n,r)|$.
Therefore, $|E(G)|\le |E(T(n,r)|$. This completes the
proof of Turán's Theorem, except for the uniqueness
of the extremal graph. QED
04.81 DO Modify the proof above to also prove that
the extremal graph is unique.
04.85 Bonus
(Turán's bound on the independence number, 16 points,
due May 3)
For every graph $G$,
$$\alpha(G) \ge \frac{n^2}{n+2m} = \frac{n}{1+\deg_{\avg}}.$$
Derive this bound from Corollary 04.57. Hint.
Apply 04.75 to the complement of $G$. Let $r=\omega(\Gbar)=\alpha(G)$.
04.87 DO Turán's bound is always at least as good
as the greedy bound 04.22, and it is strictly better unless $G$
is regular. Find an infinite family of graphs that demonstrate
an extreme gap between the two bounds: for this family,
the greedy lower bound should be $O(1)$ (bounded by a constant) while
Turán's lower bound should be $\Omega(n)$.
04.90 Mantel's Theorem (1910)
If $G$ is triangle-free then $m\le \lfloor n^2/4\rfloor.$
04.91 Observe that this result is the $r=2$ case of
Turán's Theorem.
We gave two proofs of Mantel's Theorem, both based on the following lemma.
04.93 LEMMA. If $G$ is triangle-free and $x\sim y$ are adjacent
vertices then $\deg(x) + \deg(y) \le n$.
04.95 DO Prove the Lemma. Where does a more general form
of this lemma appear in the proof of Turán's Theorem?
04.97 The first proof we gave in class for Mantel's Theorem
is an inductive proof that corresponds to the proof of
Turán's Theorem above. The second proof was analytic.
04.99 Sketch of the second proof of Mantel's Theorem.
04.101 DO Find $c_x$. Apply the inequality between the quadratic
and arithmetic means to the resulting expression to obtain the
inequality $m\le n^2/4$. Given that $m$ is an integer, it follows
that $m\le \lfloor n^2/4\rfloor$. QED
The following elegant improved bound on the independence number
was found independently by Yair Caro (1979) and Victor Keh-Wei Wei (1981).
04.113 ORD (9+8 points)
(a) Prove that the Caro-Wei bound is always
at least as good as Turán's bound, and it is strictly better
unless $G$ is regular. (b) Find an infinite family of graphs
that demonstrate an extreme gap between the two bounds: for this family,
Turán's lower bound should be $O(1)$ (bounded by a constant) while
the Caro-Wei lower bound should be $\Omega(n)$.
04.115 Proof of Caro-Wei.
04.127 DO Prove the two items listed in the proof.
04.140 RANDOM GRAPHS -- The Erdős-Rényi model
This burgeoning field was created in a single paper by
Paul Erdős and Alfréd Rényi in 1960.
04.142 The $\calG(n,p)$ model where $n$ is a positive integer
and $0 < p < 1.$
04.146 DO Prove: (a) The expected number of edges of $\calG$
is $p\binom{n}{2}$ (b) The expected number of triangles in $\calG$
is $p^3\binom{n}{3}$.
04.148 DO Prove: The variance of the number of edges of $\calG$
is $p(1-p)\binom{n}{2}$.
04.150 ORD (16 points) Let $X_n$ denote the number of triangles
in the random graph $\calG$ in the $\calG(n,p)$ model.
(a) Calculate $\var(X_n)$. Give a reasonably simple
closed-form expression. (b) The answer will be a polynomial
in $n$. What is the degree of this polynomial? (c)
Asymptotically evaluate $\var(X_n)$ as $p$ is fixed and $n\to\infty$.
Your answer should be of the form $\var(X_n)\sim a(p)n^b$ where
$b$ is a constant and $a$ is a function of $p$. Determine $a$
and $b$. Hint. PROB 7.8.19 (variance of sum)
More to follow. Please check back later.
All exercises are due Mon, Apr 12 at 11pm
except where a different deadline is stated.
03.05 MATERIAL COVERED.
Automorphisms. Vertex-transitive graphs. Examples. Regular graphs
that are not vertex-transitive. Hamiltonicity problem for
vertex-transitive graphs. Independent sets. Independence number
$\alpha(G)$. Upper bound proofs (1) by system of linear inequalities
and rounding, and (b) by the Pigeon Hole Principle.
Legal coloring, chromatic number $\chi(G)$.
$\alpha\chi \ge n$ (stated). Example of graphs where
$\alpha\chi=\Omega(n^2)$. Bipartite = 2-colorable, i.e., $\chi(G)\le 2$.
For vertex-transitive graphs, $\alpha\chi\le n(1+\ln n)$ (stated).
Clique number $\omega(G)=\alpha(\Gbar)$. $\chi\ge\omega$.
Examples where $\chi >\omega$.
$\omega=2 \Leftrightarrow G$ is triangle-free. Existence of
large-chromatic triangle-free graphs (stated). Perfect graph:
$\chi = \omega$ holds for all induced subgraphs.
Examples: bipartite graphs, their complements$^*$, comparability
graphs of posets (partially ordered sets), incomparability
graphs of posets$^*$ (Dilworth's Theorem). Not perfect:
$C_{2k+1}$ for $k\ge 2$ and its complement.
The perfect graph conjectures, history.
03.20 DEF An automorphism of the graph $G=(V,E)$ is a $G\to G$
isomorphism. In other words, it is a permutation $\pi$ of the set $V$
that preserves adjacency:
$(\forall u,v\in V)(u\sim v \Leftrightarrow \pi(u)\sim \pi(v))$.
The set of automorphisms of $G$ is denoted $\aut(G)$.
03.22 COMMENTS $\aut(G)$ is a group under composition of permutations.
The identity permutation is always a member of $\aut(G)$. Often, it is the
only member.
03.24 DEF $G$ is vertex-transitive if
$(\forall u,v\in V)(\exists \pi\in\aut(G)(\pi(u)=v)$. In other words,
all vertices are equivalent under automorphisms.
03.26 EXAMPLES of vertex-transitive graphs: $K_n$, $C_n$, the complete
bipartite graphs $K_{r,r}$, the five Platonic solids (viewed as graphs),
the Petersen graph.
03.28 DO If a graph is vertex-transitive then so is its complement.
03.30 DO If $G$, $H$ are vertex-transitive then so is $G\Box H$.
In particular, the toroidal grids are vertex-transitive.
03.32 DO (a) If $G$ is vertex-transitive then $G$ is regular.
(b) The converse is false. Find the smallest regular graph
that is not vertex-transitive. ("Smallest" mean minimum number of vertices,
and among those, the minimum number of edges.) Prove, with very few
case-distinctions, that your graph is smallest. Find the smallest
connected regular graph that is not vertex-transitive.
03.34 DO A graph is asymmetric if it has no automorphisms
other than the identity. Find (a) the smallest asymmetric graph
(b) the smallest asymmetric tree.
03.40 DEF For $r\ge 2, q\ge 2r+1$, the Kneser graph $Kn(q,r)$
has $n=\binom{q}{r}$ vertices, labeled by the $r$-subsets of $[q]$:
$V=\{v_A\mid A\in \binom{[q]}{r}\}$. The vertices $v_A$
and $v_B$ are adjacent if $A\cap B=\emptyset$.
03.42 DO Prove: $Kn(5,2)\cong$ Petersen's graph.
03.44 DO Prove: the Kneser graphs are vertex-transitive.
03.46 DO (a) Prove: Petersen's graph has 120 automorphisms.
(b) Prove: the dodecahedron graph has 120 automorphisms.
03.48 ORD (6 points) Find the girth of the Kneser graph $Kn(q,r)$.
03.50 DEF The odd-girth of a graph is the length of its
shortest odd cycle. The odd-girth of a bipartite graph is infinite.
03.52 DO Find the girth and the odd-girth of the toroidal grid
$C_{31}\Box C_{24}$.
03.54 Bonus (10+7 points, due Mon, Apr 19)
(a) Find the odd-girth of the Kneser graph $Kn(q,r)$.
(b) Find an infinite sequence of Kneser graphs $Kn(q_i,r_i)$
such that the odd-girth of $Kn(q_i,r_i)$ is $\Omega(\log n_i)$ where
$n_i=\binom{q_i}{r_i}$ is the number of vertices.
03.60 ORD (12 points, due Mon, Apr 19)
Let $G$ be a graph with minimum degree $\ge 3$
(i.e., every vertex has degree $\ge 3$). Prove: the girth of $G$
is $O(\log n)$. State the constant implied by the big-Oh notation.
Get the best constant you can.
03.62 ORD (12 points, due Mon, Apr 19)
Find an infinite sequence of non-bipartite
graphs of minimum degree $\ge 3$ and odd-girth $\Omega(n)$.
Prove. Specify your constant hidden in the $\Omega$ notation;
make it as large as you can.
03.65 DO Let $T$ be a tree with $n$ vertices. Prove that
among the spanning trees of $K_n$ there are exactly $n!/|\aut(T)|$ that
are isomorphic to $T$.
03.67 ORD (9+3) (a) List all nonisomorphic trees with 6 vertices,
and with each, state their number of automorphisms. No proof
required. (b) Use part (a) and the preceding exercise
to verify that the number of spanning trees of $K_6$ is $6^4$.
Show all your work!
03.70 DEF The independence number of the graph $G$,
denoted $\alpha(G)$, is the size of its largest independent set.
(See Def 01.18.) An independent set of size $\alpha(G)$ is called
a maximum independent set.
03.72 DEF A maximal independent set is an independent
set that is not properly contained in any independent set.
03.72 DO Verify: $\alpha(P_n)=\lceil n/2\rceil$ and
$\alpha(C_n)=\lfloor n/2\rfloor$. To prove the upper bounds,
use the method of linear inequalities for $C_n$ and the Pigeon
Hole Principle for $P_n$.
03.75 ORD (5 points) How small can a maximal independent
set be compared
to a maximum independent set? For every $n$, find the minimum ratio
$|S|/\alpha(G)$ where $G$ is a graph with $n$ vertices and
$S$ is a maximal independent set in $G$. The minimum is taken over
all choices of $G$ and $S$.
03.77 DO Find the minimum size of maximal independent
sets in (a) $P_n$ (b) $C_n$.
03.80 Bonus (16 points, due Mon, Apr 19)
Determine the quotient $\alpha(G)/n$ for toroidal graphs
$G=C_r\Box C_s$ $(r,s\ge 3)$ $(n=rs)$. Give a clear statement of your answer,
and clearly separate the proof of the lower bound and the proof of the
upper bound.
03.82 CH Determine the independence number of the Kneser
graph $Kn(q,r)$. The answer is a very simple expression involving
binomial coefficients.
03.84 DO (naive lower bound) $\alpha(G) \ge n/(1+\deg_{\max})$.
Give an efficient algorithm to find an independent set of this size or greater.
03.90 DEF The clique number of the graph $G$, denoted
$\omega(G)$, is the size of the largest clique (complete subgrph)
in $G$.
03.92 DO $\omega(G) = \alpha(\Gbar)$.
03.94 DO Determine the clique number of the Kneser graph $Kn(q,r)$.
03.100 DEF Let $G=(V,E)$ be a graph and $\calC$ a set.
We refer to the elements of $\calC$ as "colors." A coloring
if a function $f:V\to\calC$. A $k$-coloring is a coloring where
$|\calC|=k$. (Note: not all colors need to be used.)
A legal coloring is a coloring that satisfies the
condition that $(\forall u,v\in V)(u\sim v \Rightarrow f(u)\neq f(v))$.
03.102 DEF The chromatic number of $G$, denoted $\chi(G)$,
is the minimum number of colors required for a legal coloring.
We say that $G$ is $k$-colorable if $k$ colors suffice for a
legal coloring, i.e., is $k\ge \chi(G)$.
03.104 DO $G$ is bipartite if and only if $G$ is 2-colorable.
03.106 DO $\chi(C_n)= 2$ if $n$ is even and $3$ if $n$ is odd.
03.108 DO $\chi(G)=n \Leftrightarrow G=K_n\,.$
03.110 DO $\chi(G) \ge \omega(G)$.
03.112 ORD (7 points) $\alpha(G)\cdot \chi(G) \ge n$.
03.114 DO Find infinitely many graphs $G$ such that
$\alpha(G)\cdot\chi(G) = \Omega(n^2)$.
03.116 CH Prove: If $G$ is vertex-transitive then
$\alpha(G)\cdot\chi(G) \le n(1+\ln n)\,.$
03.120 DO Prove: $\chi(G)\le 1+\deg_{\max}(G)$.
Give a simple algorithmic proof. Compare your algorithm with
the "Greedy coloring" handout.
03.122 ORD (9 points, due Mon, Apr 19)
Solve part (b) of the Problem in the
"Greedy coloring" handout. (Greedy coloring is terrible.)
03.124 Bonus (14 points, due Mon, Apr 19)
Let $G$ be a triangle-free graph.
Prove: $\chi(G)=O(\sqrt{n})$. Specify the constant
implied by the big-Oh notation. Get the best constant you can.
03.126 Bonus (7 points) Prove:
$\chi(Kn(q,r))\le q-2r+2$.
03.128 THEOREM (Lovász)
$\chi(Kn(q,r)) = q-2r+2$.
03.134 ORD (8 points) Let $G_1=(V,E_1)$ and $G_2=(V,E_2)$
be graphs on the same set of vertices. Let
$G_1\cup G_2=(V,E_1\cup E_2)$. Prove:
$\chi(G_1\cup G_2)\le \chi(G_1)\cdot \chi(G_2)$.
03.136 DO Find the smallest triangle-free graph of chromatic number 3.
03.138 DO Find the smallest graph that contains no $K_4$ but
has chromatic number $\ge 4$.
03.140 ORD (Fun-math problem, 10 points)
Find the smallest triangle-free graph of chromatic number $\ge 4$.
Your graph will have 11 vertices and can be drawn
so as to show a rotational symmetry of order 5 (the rotatiion of the
plane by $2\pi/5$ does not change the drawing). You do not need to
prove that the graph is smallest. Do not prove that the graph is
triangle-free. Prove that your graph is not 3-colorable. Hand
in a nice drawing of your graph on a separate sheet. Make sure
to label the vertices for reference.
03.144 CH (Tutte 1947, Zykov 1949, Mycielski 1955)
For every $k$ there exists a triangle-free
graph of chromatic number $\ge k$.
The next major problem was whether large-chromatic graphs can
have large girth. This was solved by Paul Erdős
in one of the early triumphs of the probabilistic method.
03.146 THEOREM (Erdős, 1959)
For all $k$ and $g$ there exist graphs of chromatic number $\ge k$
and girth $\ge g$.
03.148 CH (DeBruijn-Erdős, 1951) (In this course, all graphs are
finite. This problem is an exception.) Let $k$ be a positive integer.
If every finite subgraph of an infinite graph $G$ is $k$-colorable
then $G$ is $k$-colorable. — Give three proofs: 1. Use the Compactness
Theorem of first-order logic. 2. Use Tykhonoff's Theorem stating
the compactness of the topological product of compact spaces.
3. Use nothing but Zorn's lemma.
03.155 DEF For a graph $G=(V,E)$ and $k\ge 0$ let $P(G,k)$
denote the number of legal colorings $f:V\to [k]$.
03.157 DO Verify: (a)
$P(K_n,x)=x(x-1)\dots(x-k+1)$ (b)
$P(\Kbar_n,x)=x^n$.
03.160 Notation (removal of an edge)
Let $G=(V,E)$ be a graph and $e\in E$. Then $G-e = (V, E\setminus \{e\})$.
(We remove the edge $e$ but keep its endpoints.)
03.162 DEF Let $G=(V,E)$ be a graph and $e=\{u,v\}\in E$
and edge. The contraction of $e$ (turning $e$ into a single vertex)
defines the graph $G/e$ as follows: we interiduce a new vertex $v_e$
that will replace $e$; we make sure $v_e\notin V$. Now
$V(G/e)=V\cup \{v_e\}\setminus \{u,v\}$. For $x,y\in V\setminus \{u,v\}$
we make $x\sim_{G/e} y$ if $x\sim_G y$, and for
$x\in V\setminus \{u,v\}$ we make $x\sim_{G/e} v_e$
if $x\sim_G u$ or $x\sim_G v$.
03.164 DO Verify: for any edge $e$ of the graphs indicated,
(a) $K_n/e \cong K_{n-1}$ $(n\ge 2)$, (b)
$C_n/e \cong C_{n-1}$ $(n\ge 4)$, (c) $P_n/e \cong P_{n-1}$.
03.166 DO (Contraction-deletion recurrence)
Let $e\in E(G)$. Prove:
$P(G,k)=P(G-e,k) - P(G/e,k)$.
03.168 DO Prove: $P(G,x)$ is a polynomial in $x$.
This function is called the chromatic polynomial of $G$.
Use the contraction-deletion recurrence.
03.170 Bonus (8 points)
Prove that $P(G,x)$ is a polynomial in $x$.
Do not use the contraction-deletion recurrence. Instead, for each
legal coloring, consider
the color partition of $V$ (partition of $V$ according to color).
How many colorings correspond to the same partition?
03.172 ORD (5 points)
Prove that all trees with $n$ vertices have
the same chromatic polynomial.
03.174 Bonus (8 points, due Mon, Apr 19)
Find the chromatic polynomial of cycles,
$P(C_n,x)$. Your answer should be a simple closed-form expression.
03.176 ORD (4+4+9, due Mon, Apr 19)
(a) Prove that the chromatic polynomial
$P(G,x)$ has degree $n$. Let $P(G,x)=a_nx^n +a_{n-1}x^{n-1}+\dots+a_0$.
Prove: (b) $a_n=1$ and (c) $a_{n-1} = -m$. (As always, $m$
denotes the number of edges.)
03.185 DEF The graph $G$ is perfect if
$\chi(G)=\omega(G)$ and the same holds for all induced subgraphs
of $G$, i.e., $(\forall A\subseteq V)(\chi(G[A])=\omega(G[A])$.
03.188 DO Verify: (a) All bipartite graphs
are perfect (b) $K_n$ is perfect (c) $C_n$ is perfect
if and only if $n$ is even (d) the smallest imperfect graph
is $C_5$ (e) If $G$ has an induced odd cycle of length $\ge 5$
then $G$ is not perfect.
03.190 ORD (9 points) Let $n\ge 5$ be an odd number.
Prove: $\Cbar_n$ is not perfect.
03.192 CH Prove: the complement of a bipartite graph is
perfect.
03.194 ORD (5 points) Find a graph $G$ that satisfies
$\chi(G)=\omega(G)$
but is not perfect. Make your graph the smallest possible.
(Minimum number of vertices, and among those with the minimum number
of vertices, the minimum number of edges.)
Give a very simple description of your graph
(one line). Complicated solutions will not be accepted.
State the chromatic number and the clique number of your graph
and briefly reason why it is not perfect. You do not need to prove
minimality.
03.200 DEF A partially ordered set ("poset")
is a set with a binary relation that is reflexive, antisymmetric,
and transitive. This means, if $S$ is the set and $\le$ denotes the
relation, then (a) $(\forall x\in S)(x\le x)$, (b)
$(\forall x,y\in S)((x\le y\ \&\ y\le x)\Rightarrow x=y)$, and (c)
$(\forall x,y,z\in S)((x\le y\ \&\ y\le z)\Rightarrow x\le z)$.
03.202 DEF Let $(S,\le)$ be a poset. We say that $x,y\in S$
are comparable if $x\le y$ or $y\le x$; if neither of these holds,
we call $x$ and $y$ incomparable. The comparability graph
is defined on the vertex set $S$; two distinct element are adjacent
if they are comparable. The complement of this graph is the
incomparability graph of $(S,\le)$.
03.204 ORD (10 points, due Mon, Apr 19)
Count the edges of the comparability graph of the
Boolean poset $(\calP([r]), \subseteq)$. Your answer should be a simple
closed-form expression. Give a simple proof; elegance counts.
03.206 Bonus (7 points, due Mon, Apr 19)
Let $m(n)$ denote the number of edges of the
divisibility poset on $[n]$. Prove: $m(n)\sim n\ln n$.
03.208 ORD (8 points) Prove: the comparability graph of
a poset is perfect.
3.210 DO Prove: every bipartite graph is a comparability graph.
03.212 DEF A chain in a poset is a set of pairwise
comparable elements, i.e., a clique in the comparability graph.
An antichain is a set of pairwise incomparable elements,
i.e., an independent set in the comparability graph.
A chain cover of the poset $(S,\le)$ is a partition of
$S$ into chains, $S=C_1\dot\cup\dots\dot\cup C_k$. The size of this
cover is $k$.
03.214 DO Prove: If $k$ is the size of a chain cover
of the poset $(S,\le)$ and $A$ is an antichain in the poset, then
$k\ge |A|$. Consequently, if $k=|A|$ then both the chain cover
and the antichain are optimal (the chain cover is minimal and the
antichain cover is maximal).
03.220 THEOREM (Dilworth, 1950) Given a poset, the maximum
size of an antichain is equal to the minium size of a chain cover.
03.222 DO Verify that Dilworth's Theorem is equivalent
to the statement that the incomparability graph of a poset is perfect.
03.225 HISTORY Perfect graphs were defined by Claude Berge in 1961.
Berge formulated two remarkable conjectures regarding this class of graphs:
All exercises are due Mon, Apr 12 at 11pm.
WARNING: Definitions due Tue, Apr 6, before class.
02.05 MATERIAL COVERED.
Eulerian trail, Eulerian tour. Inequalities between the
arithmetic, quadratic, geometric, and harmonic means.
Asymptotic notation: asymptotic equality, big-Oh, big-Omega ($\Omega$),
big-Theta ($\Theta$) notation. Stirling's formula, prime counting function.
Finite probability spaces, examples, events, random variables,
expected value, linearity of expectation, indicator variables,
application to counting heads in a sequence of (biased)
coin flips.
02.08 STUDY (definitions and theorems due before next class,
Tue, Apr 6):
asymptotic notation: ASY 1-3 (asymptotic equality),
DM 2.1 (limits), 2.3 (little-oh notaion, 2.4 ($O,\Omega,\Theta$
notation)
02.10 STUDY (definitions and theorems due before next class,
Tue, Apr 6):
Finite Probability Spaces: PROB 7.1 (events), 7.7
(random variables)
02.11 STUDY (by Apr 12) PROB 7.2--7.4 (main theme:
independence of events), PROB 7.5 (random graphs), PROB 7.8
(variance), PROB 7.9--7.10 (independence of random variables)
02.12 STUDY (definitions and theorems due before next class,
Tue, Apr 6): DM 6.2 (digraph terminology)
02.20 DEF A walk of length $k$ from vertex $s$ to
vertex $t$ is a sequence $s=v_0,v_1,\dots,v_k=t$ of vertices such that
$(\forall i)(v_{i-1}\sim v_i)$. (Repeated vertices are permitted.)
This walk is a closed walk if $s=t$.
02.22 DO (a) Prove: If $t$ is accessible from $s$
by a walk then $t$ is accessible from $s$ by a path. Prove that
the shortest $s\dots t$ walk is a path. (b)
Use this result to give an elegant proof that
accessibility is a transitive relation.
02.24 DO Prove: If there exists a closed walk
of odd length in $G$ then there exists an odd cycle in $G$.
02.27 DEF An Eulerian trail from vertex $s$ to
vertex $t$ in the graph $G$ is a walk that passes through every
edge exactly once. An Eulerian tour is a closed
Eulerian trail: $s=t$. A graph is Eulerian if
it has an Eulerian tour.
02.29 THEOREM Let $G$ be a graph without isolated vertices
(vertices with no neighbor). Prove: $G$ is Eulerian
if and only if it is connected and every vertex has even degree.
02.30 DO (a) Prove the Theorem.
(b) Give an analogous necessary and sufficent condition for a graph
to have an Eulerian trail from vertex $s$ to vertex $t$.
02.40 DEF The arithmetic mean or (simple) average of the
real numbers $a_1,\dots,a_n$ is the quantity
$$ A(a_1,\dots,a_n) = \frac{a_1+\dots+a_n}{n}\,.$$
02.42 DEF Let $(p_1,\dots,p_n)$ be a probability distribution, i.e.,
$p_i\ge 0$ and $\sum_{i=1}^n p_i = 1$. The weighted average
of $a_1,\dots,a_n$ with weights $p_i$ is the quantity
$$ \sum_{i=1}^n p_ia_i.$$
If $p_1=\dots=p_n=1/n$ (uniform distribution), we get the arithmetic mean.
02.44 DO If $m$ is a weighted average of $a_1,\dots,a_n\in \rrr$ then
$\min_i a_i \le m \le \max_i a_i$.
02.46 DEF The quadratic mean of $a_1,\dots,a_n$ is the
quantity
$$ Q(a_1,\dots,a_n) = \sqrt{A(a_1^2,\dots,a_n^2)} =
\sqrt{\frac{a_1^2+\dots+a_n^2}{n}} $$
02.48 DO Prove:
$(\forall a_1,\dots, a_n\in\rrr)(A(a_1,\dots,a_n)\le Q(a_1,\dots,a_n))$.
Show that equality holds $(Q=A)$ if and only if $a_1=\dots =a_n\ge 0$.
02.49 DO Prove: If $m$ is a (weighted) quadratic average
of $a_1,\dots,a_n\in\rrr$ then
$\min_i |a_i| \le m \le \max_i |a_i|$.
02.50 Let $a_1,\dots,a_n > 0$. The geometric mean
of $a_1,\dots,a_n$ is the quantity
$$ G(a_1,\dots,a_n) = \left(\prod_{i=1}^n a_i\right)^{1/n}\,$$
02.52 THEOREM Let $a_1,\dots,a_n > 0$. Then
$$G(a_1,\dots,a_n) \le A(a_1,\dots,a_n)\,.$$
Equality holds $(G=A)$ if and only if $a_1=\dots =a_n$.
02.54 DO Prove Theorem 02.52 for $n=2$.
02.56 DO Prove Theorem 02.52 for $n=4$.
02.58 DO Prove Theorem 02.52 for $n=3$ using the preceding exercise.
02.60 DO
Prove Theorem 02.52 for $n=2^k$. Use the method of 02.56.
02.62 Bonus (5 points) Prove Theorem 02.52 for all $n$,
given that we have already
proved it for powers of 2. Use the method of 02.58.
Proofs by other methods will not be accepted.
02.64 DEF Let $a_1,\dots,a_n > 0$. The harmonic mean of
of $a_1,\dots,a_n$ is the quantity
$$ H(a_1,\dots,a_n) = \frac{1}{A\left(\frac{1}{a_1},\dots,\frac{1}{a_n}\right)} = \frac{n}{\frac{1}{a_1}+\dots +\frac{1}{a_n}}\,.$$
02.66 ORD (5 points) Let $a_1,\dots,a_n > 0$. Prove:
$$H(a_1,\dots,a_n) \le G(a_1,\dots,a_n)\,.$$
Equality holds $(H=G)$ if and only if $a_1=\dots =a_n$.
02.68 DO The road from point $A$ to point $B$ consists
of $n$ segments of equal length. A car travels from $A$ to $B$.
It passes through the $i$-th segment at speed $v_i$. Prove, that
the average speed of the car from $A$ to $B$ is $H(v_1,\dots,v_n)$.
02.70 DO Let $a_1,\dots,a_n > 0$.
Prove the two extreme inequalities in this series:
$$\min_i 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_i a_i\,.$$
02.75 ORD (4+4 points)
(a) Prove that for all $n\ge 2$ we have
$\displaystyle n! < \left(\frac{n+1}{2}\right)^n$. Use the inequality
between the arithmetic and the geometric mean. (b) Prove that
$n! = o\left((n/2)^n\right)$ (little-oh notation). Use Stirling's formula.
02.85 DO Prove: $(\forall n\ge 0)(n! \ge (n/\eee)^n)$.
Use the power series expansion $\eee^x =\sum_{k=0}^{\infty} x^k/k!$.
02.87 DO (a) Let $1\le k\le n$. Prove:
$$\left(\frac{n}{k}\right)^k \le \binom{n}{k} \le
\left(\frac{\eee n}{k}\right)^k \,.$$
02.89 Bonus (7 points) Let $1\le k\le n$. Prove:
$$ \sum_{j=0}^k \binom{n}{j} \le \left(\frac{\eee n}{k}\right)^k \,.$$
02.91 DO Prove: $(\forall x\in\rrr)(1+x\le \eee^x)$.
02.93 DO Solve all exercises in ASY, Sections 2, 3.
02.95 DO Solve all exercises in DM, Sections 2.3, 2.4,
and 2.7.
02.97 ORD (5 points)
Prove: there exist constants $a,b,c$ such that
$\binom{2n}{n} \sim an^bc^n$. Determine $a,b,c$. Clearly state these
values. Here $\sim$ refers to asymptotic equality. Read ASY.
Use Stirling's formula.
02.99 ORD (4 points)
Prove: there exist constants $a,b$ such that
$\sqrt{n^2+1}-n \sim an^b$. Determine $a,b$. Clearly state these
values.
02.102 DO Let $a_n, b_n$ be sequences of positive numbers.
Prove: If $a_n\sim b_n$ then $a_n = \Theta(b_n)$.
02.104 ORD (7 points)
Let $a_n, b_n$ be sequences of positive numbers.
Assume $a_n\to\infty$ and $a_n = \Theta(b_n)$. Prove:
$\ln(a_n) \sim \ln(b_n)$.
02.110 Bonus (6+6 points)
Let $\nnn$ denote the set of positive integers.
Let $k:\nnn\to\nnn$ be a function such that $1\le k(n)\le n$.
(a) Prove: if $k(n)=o(\sqrt{n})$ then
$$\binom{n}{k(n)}\sim \frac{n^{k(n)}}{k(n)!} $$
(b) Prove: if $k(n)=\Omega(\sqrt{n})$ then this asymptotic equality
does not hold.
02.112 DO Let $\epsilon > 0$. Prove:
$\ln x=o(x^{\epsilon})$.
02.114 DO Let $C$ and $\epsilon$ be positive constants.
Prove: $n^C = o(\exp(n^{\epsilon}))$.
(Notation: $\exp(x)=\eee^x$.)
02.120 DO Solve all non-starred exercises in PROB,
Sections 7.1--7.5 (events, independence) and
Sections 7.7--7.10 (random variables)
02.125 ORD (6 points) Construct a finite probability space
$(\Omega,P)$ and three events $A,B,C\subseteq\Omega$ such that
$A,B,C$ are pairwise but not fully independent. Make your
smaple space $\Omega$ as small as possible. You don't need
to prove that $|\Omega|$ is smallest.
02.127 ORD (5+3) PROB 7.7.22(a)(b) (marbles in cups)
02.129 Bonus (3+10) Let $A=(a_{ij})$ be an $n\times n$
random $(\pm 1)$-matrix:
each entry $a_{ij}$ takes the value $1$ or $-1$ depending on a fair
coin flip. Determine (a) the expected value and (b) the variance
of $\det(A)$.
Your answers should be very simple expressions in terms of $n$.
Prove.
02.135 Bonus (strongly negatively correlated events, 14 points)
Let $A_1,\dots,A_m$ be balanced events, i.e., $(\forall i)(P(A_i)=1/2)$.
Assume for all $i\neq j$ we have $P(A_i\cap A_j)\le 1/5$.
Prove: $m\le 6$.
02.145 Bonus (7 points) Consider a graph $G=(V,E)$.
Let us say
that the edges $e$ and $f$ are co-circular if either $e=f$ or
there is a cycle that contains both. Prove that co-circularity
is an equivalence relation on $E$.
02.150 CH Let $G$ be a DAG (directed acyclic graph)
of depth $d$ (so $d$ is the length of the longest directed path).
Assume $d < 2^k$. Prove: one can delete a set of $\le m/k$ edges
so that the remaining DAG has depth $ d' < 2^{k-1}$. (Read
about digraphs in DM.)
All exercises are due Mon, Apr 5 at 11pm.
WARNING: The problem numbering has changed compared to an early edition.
The numbering was finalized at 18:25 on March 30 and remains stable
after that point.
01.05 MATERIAL COVERED.
Basic concepts of graph theory, examples of graphs. Adjacency.
Degree. Regular graphs. Complement. Isomorphism. Cartesian product
of graphs. Complete graphs, paths, cycles, grids, toroidal grids.
Petersen's graph.
Bipartite graphs. Subgraphs, induced subgraphs, spanning subgraphs.
01.10 STUDY DM Chap. 6.1 Definitions and exercises
up to Exercise 6.1.73. All definitions due by Thursday's class
(Apr 1).
01.15 STUDY GR19 Classes 1 and 2.
01.18 DEF An independent set in the graph $G=(V,E)$
is a subset $A\subseteq V$ such that there are no edges between
pairs of vertices in $A$. In other words, $E\cap \binom{A}{2} = \emptyset$.
01.20 ORD (8 points) Count the independent sets in the
path $P_n$ with $n$ vertices $(n\ge 1)$. (This is the path of length $n-1$.)
Express your answer as a closed-form expression (no summation
or dot-dot-dots) in terms of a familiar sequence. Give a clear
statement of your answer, followed by the proof. Note: the empty set
is an independent set. So if we denote the number we seek by $s(n)$
then $s(1)=2$ and $s(2)=3$. (Verify!)
01.22 Bonus (16 points)
Count the subgraphs of the path $P_n$ $(n\ge 1)$.
Express your answer as a closed-form expression (no summation
or dot-dot-dots) in terms of a familiar sequence. Give a clear
statement of your answer, followed by the proof. Note: the graph
with no vertices is also a subgraph. So if we denote the number
we seek by $z(n)$ then $z(1)=2$ and $z(2)=5$. (Verify!)
01.25 ORD (2+2+4 points)
DM 6.1.11 (a)(b)(c) (self-complementary graphs)
01.27 DO Find the maximum number of edges of a disconnected
graph with $n$ vertices. (Disconnected means "not connected.")
Give a clear answer (a simple closed-form expression), and prove it.
01.29 DO Prove: if the graph $G$ is disconnected
then its complement $\Gbar$ is connected.
01.31 DO (Handshake Theorem) $\sum_{v\in V} \deg(v)=2m$.
01.33 DO Let $\deg_{\avg}(G)$ denote
the average degree of a graph $G$.
(So $\deg_{\avg}(G)$ is the aritmetic mean of the degrees.)
Prove: $G$ has a subgraph
where every vertex has degree $\ge (1/2)\deg_{\avg}(G)$.
01.34 DO Prove: A graph is a tree if and
only if for every pair of vertices there is a unique path
connecting them.
01.35 Bonus (18 points) Let $T$ be a tree.
A subtree is
a subgraph that is a tree. Let $S_1,\dots,S_k$ be subtrees of $T$.
Assume the $S_i$ pairwise intersect, i.e., for every $i$ and $j$
($1\le i < j \le k$) the subtrees $S_i$ and $S_j$ share a vertex.
Prove: all the $S_i$ intersect (i.e., all of them share a vertex).
01.37 ORD (5 points) Let $G$ be a connected graph. Assume
the following holds: If $S_1, S_2, S_3$ are subtrees of $G$ such that
the $S_i$ pairwise intersect then all of them intersect.
Prove: $G$ is a tree.
01.39 ORD (15 points; lose 4 points for each mistake)
Draw all non-isomorphic trees with $n=7$ vertices (i.e., one
representative of each class of isomorphic 7-vertex trees).
State, how many you have found. Avoid the three kinds of mistake:
(a) you draw two isomorphic trees (b) you miss a tree
(c) you include a graph among your pictures that does not belong
(it is not a tree with 7 vertices).
01.40 DO Prove: If a tree $T$ has $\ge 2$ vertices
then it has a vertex of degree 1. Hint: Let $P$ be a
maximal path if $T$ (i.e., a path that is not a subgraph of any
other path). Prove: The endpoints of $P$ have degree 1 in $T$.
01.42 DO Prove: a tree with $n$ vertices has $m=n-1$ edges.
Complete the inductive proof given in class: remove a vertex of degree 1;
show that what remains is also a tree (assuming $n\ge 2)$.
01.43 DO Prove: a forest with $k$ connected components
has $m=n-k$ edges.
01.44 DEF A spanning tree of a graph $G$ is a spanning
subgraph that is a tree.
01.46 DO Prove: A graph $G$ has a spanning tree if and
only if $G$ is connected.
01.47 DO Prove:
(a) A connected graph has at least $n-1$ edges.
(b) Every graph has at least $n-m$ connected components.
01.48 DO Prove that the following statements are
equivalent about a graph $G$.
01.53 ORD (9 points) Let $G$ be a graph with $m$ edges.
Prove: $G$ has a bipartite spanning subgraph with at least $m/2$
edges. Your proof should also provide an efficient deterministic
algorithm for finding such a subgraph. "Efficient" should mean
"polynomial time" but you do not need to prove that your
algorithm works in polynomial time.
01.60 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$.)
01.62 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 ?
01.64 ORD (4+6 points) (a) Count the 4-cycles in $K_n$. Give
a simple closed-form expression. Test case: the number of 4-cycles
in $K_4$ is 3. (b) Count the 4-cycles in $Q_n$.
Give a simple closed-form expression. Briefly reason your answers.
01.66 ORD (6 points) Count the shortest paths from the
bottom left to the top right corner of $\grid(k,\ell)$. Your answer
should be a simple closed-form expression in terms of binomial
coefficients.
01.68 CH (Do not look this up on the web.)
The $d$-dimensional cube graph $Q_d$ has
$n=2^d$ vertices and each vertex has degree $d$. Let $A$ be
a subset of $V(Q_d)$ of size $|A| > n/2$. Let $H=Q_d[A]$ denote
the subgraph of $Q_d$ induced by $A$. Prove: $H$ has a vertex
of degree $\ge \sqrt{d}$.
01.75 DEF The girth of a graph is the length of its
shortest cycle. The girth of a forest is infinite.
01.77 DO The girth of the complete graph $K_n$ is 3 ($n\ge 3$).
The girth of the $d$-dimensional cube graph $Q_d$ is 4 ($d\ge 2$).
The girth of the dodecahedron graph is 5.
01.80 ORD (5 points) Let $k,\ell \ge 3$. What is the
girth of the toroidal grid $C_k \Box C_{\ell}$ ? Give a clear answer.
Indicate the proof.
01.83 DO (Petersen's graph) Both graphs below have
10 vertices, they are regular of degree 3, and have girth 5 (verify!).
Show that these two graphs are isomorphic. (You need to find an
isomorphism.)
01.85 ORD (7+3 points) Let $r\ge 1$.
(a) Let $G$ be an $r$-regular graph
of girth $\ge 5$. Prove: $n\ge r^2+1$. (b)
Give examples that show that this inequality is tight for $r=1,2,3$
(i.e., for these values of $r$, the equality $n=r^2+1$ is possible).
01.88 Bonus (isomorphism of toroidal graphs, 20 points)
Let $k,\ell,r,s\ge 3$. Prove: if $C_k\Box C_{\ell} \cong C_r\Box C_s$
then $\{k,\ell\} = \{r,s\}$.
01.90 DEF $[n]$ denotes the set $\{1,2,\dots,n\}$. Let
$G=([n],E)$ be a graph. The adjacency matrix of $G$ is
the $n\times n$ matrix $A_G = (a_{ij})$ where $a_{ij}=1$ of
vertices $i$ and $j$ are adjacent and $0$ otherwise. Note
that by definition, the diagonal elements are $a_{ii}=0$.
The characteristic polynomial $f_G(x)$ is the
characteristic polynomial of $A_G$.
01.92 DO Prove: isomorphic graphs have the
same characteristic polynomial.
01.95 DO Let $\lambda_1,\dots,\lambda_n$ be the
eigenvalues of the adjacency matrix $A_G$. Prove:
(a) The $\lambda_i$ are real. (b)
$\sum_{i=1}^n \lambda_i=0$.
01.97 Bonus (7 points) (Continued.)
Express $\sum_{i=1}^n \lambda_i^2$
as a very simple closed-form expression in terms of $n$
(the number of vertices of $G$) and $m$ (the number of edges
of $G$). Prove your answer.
Class #17, Tue, May 25
Shannon capacity of graphs: $\Theta(G)$.
Strong product of graphs. Examples: King's moves graph on chessboard
and toroidal chessboard. Fekete's Lemma. How to prove upper bounds
on $\Theta(G)$? Fractional independence number $\alpha^*(G)$, fractional
chromatic number $\chi^*(G)$. Linear Programming, LP Duality Theorem.
Consequence: $\alpha^*(G) = \chi^*(\Gbar)$. $\Theta(G)\le\alpha^*(G)$.
UPDATE (06-02 14:30) Assumption $d > 0$ added.
A multilinear polynomial is a linear
combination of multilinear monomials:
$f(x_1,\dots,x_n)=\sum_{I\subseteq [n]} a_I x_I$ where
$a_I\in\rrr$.
Example: How many adjacency queries are needed to find out whether
a hidden graph is planar?
This conjecture was recently verified by Hao Huang (2019) using
spectral graph theory, through the following equivalent refomulation.
There exists a constant $c > 0$ such that the following holds.
Let $H$ be an induced subgraph of $Q_d$ on more than half the vertices.
Then $\deg_{\max}(H)\ge d^c$.
We discuss the proof in full detail.
Huang's result give the positive answer for $t=2$.
But the answer is not known even for $t=3$; Huang's
method does not seem to generalize.
This is the result of Exercise 11.70.
UPDATE (05-27 03:45) The previous version erroneously had
$ab$ instead of $a+b$ in the arguments on the left-hand side.
(Note: the limit may be infinite.)
(b) Let $f:\nnn\to \rrr^+$ be a submultiplicative
arithmetic function.
Then $\lim_{n\to\infty}\ (g(n))^{1/n}$ exists and is
equal to $\inf_n \ (g(n))^{1/n}$.
(i) $V(G\cdot H)=V(G)\times V(H)$.
(ii) For $g_1,g_2\in V(G)$ and $h_1,h_2\in V(H)$ we say that
$(g_1,h_1)\simeq_{G\cdot H} (g_2,h_2)$ if
$g_1\simeq_G g_2$ and $h_1\simeq_H h_2$.
UPDATE (5-27 19:45) Typo in the definition of adjacency corrected.
Class #16, Thu, May 20
Class #15, Tue, May 18
UPDATE (5-23 20:15): Clarification "from PALEY" was added (twice)
to the sentence above.
UPDATE (5-19 20:15): this problem was added. The corresponding
part of PALEY has been corrected and reorganized (PALEY 4.9--4.11).
UPDATE (5-19 20:15): this problem is a significant update of
the problem, previously numbered 10.63. The corresponding
part of PALEY has been corrected and reorganized (PALEY 4.9--4.11).
Make sure to clear your browser's cache if you do not see
PALEY 4.11.
Comment. Such a coloring is required for the organization of
the rounds of a round-robin tournament. At some point in the
history of chess competitions, the start of a tournament was delayed
because the organizer forgot to bring his tables of such a
a coloring to the event.
(*) Every bridgeless 3-regular planar graph is class-1 (can be
edge-colored by 3 colors).
Prove: (*) is equivalent to the 4-Color Theorem. (Tait's Theorem)
The Petersen graph is class 2 (cannot be edge-colored by 3 colors).
Petersen's graph is the smallest such graph; and this was the context
in which Petersen found this graph.
Class #14, Thu, May 13
(Recall that "exponentially many" means that there exist a constant
$c > 1$ such that for all sufficiently large $n$ there are more
than $c^n$ of them.) State the value of your $c$. Make it
as large as you can.
Class #13, Thu, May 11
UPDATE (5-16):
Note that the outer region is also a region, and it can be 3-sided.
(Recall that a graph is a multigraph of girth $\ge 3$.)
Class #12, Thu, May 6
Hint for (a): apply Rayleigh's Principle to $A^TA$.
This circumstance is also expressed as "$a$ is a divisor of $b$,"
and also as "$b$ is a multiple of $a$."
Let $\Div(a)$ denote the set of divisors of $a$.
Let $\Div(S)$ denote the set of common divisors of $S$.
Omitting a pair of braces, $\Div(a,b)$ denotes the set of
common divisors of $a$ and $b$.
UPDATE (06-03): error in part (a) fixed.
Note: This is not Courant-Fischer, just an enhanced version
of Rayleigh's principle.
The Chebyshev polynomials of the second kind, $U_n$,
are defined by the equation
$U_n(\cos\theta)=\frac{\sin((n+1)\theta)}{\sin\theta}\,$).
Class #11, Tue, May 4
Explicit construction: Ramanujan graphs (Lubotzky-Phillips-Sarnak,
Margulis, 1988) (not shown).
Spectral graph theory. Spectrum of the star graph found.
Corollary: if the $d$-regular graph $G$ has diameter $\ge 4$ then
$\lambda_2(G)\ge \sqrt{d}$ by Interlacing Theorem.
Alon-Boppana: All sufficiently large $d$-regular graphs
satisfy $\lambda_2 > 2\sqrt{d-1}-\epsilon$ (stated).
Def: Ramanujan graph: $(\forall i\ge 2)(|\lambda_i|\le 2\sqrt{d-1})$.
Alan J. Hoffman's spectral lower bound on the chromatic number:
$\displaystyle{\chi \ge 1+\frac{\lambda_1}{-\lambda_n}}$ (stated).
For Ramanujan graphs,
this gives a lower bound of $\approx \sqrt{d-1}$ on the chromatic number,
and these graphs also have large girth.
OPEN QUESTIONS. (a)
Does there exist $\epsilon > 0$ such that for all
sufficiently large $k$, $(\sqrt{2}+\epsilon)^k\not\to (k+1,k+1)$ ?
(b) Does there exist $\epsilon > 0$ such that for all
sufficiently large $k$, $(4-\epsilon)^k \to (k+1,k+1)$ ?
These are two of the greatest unsolved problems in graph theory.
(a) Prove that $A_d^2 = d I$.
(b) Find the spectrum of $A_d$ (the list of eigenvalues and
their multiplicities).
(c) Prove: If we change all $-1$ entries of $A_d$ to $1$,
we get the adjacency matrix of the $d$-dimensional cube $Q_d$.
Class #10, Thu, Apr 29
Hint. Look around on this page, you might find something
relevant.
(b) Use part (a) to get a quick and elegant proof of the fact that
the product of two stochastic matrices is stochastic.
UPDATE (05-06 16:30) "to eigenvalue 1" added to part (a).
Examples: permutation matrices, the matrix $(1/n)J$.
Surprise: The proof uses Hall's theorem.
UPDATE (05-06 16:50) the word "doubly" added.
(a) State the transition matrix $T$ of this MC and
find its stationary distribution $\pi=(\pi_1,\pi_2)$.
(b) Starting from the initial distibution concentrated on state 1, i.e.,
from $q_0=(1,0)$, compute the distribution $q_t=(a_t,b_t)$
after $t$ time steps. (So $a_0=1$ and $b_0=0$.)
Prove: $a_t-\pi_1 = c^t\pi_2$ and $b_t-\pi_2=-c^t\pi_2$
for some constant $c$. Find the constant $c$. This will show
rapid convergence to the stationary distribution.
Do not use any electronic devices. Show your work!
Class #09, Tue, Apr 27
Prove: (a) If $G$ is perfect then $G^*(v)$ is also perfect.
(b) $\alpha(G^*(v))=\alpha(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 by
providing a cover of the same size and vice versa.
UPDATE (4-30, 16:00) Previous version erroneously referred to
the edge-disjoint version.
(a) There exists a perfect $P$-matching in $G$.
(b) For all subsets $A\subseteq P$ we have $|N_G(A)|\ge |A|$.
Class #08, Thu, Apr 22
UPDATE (05-01 01:25): Chap 8 and Sec 4.1 added for background.
Deduce (b) from (a) in one line; do not repeat the argument
used to prove (a).
(a) Determine all eigenvectors of $J_n$. For each eigenvector,
state the corresponding eigenvalue.
(b) Prove that every eigenvector of $J_n$ is also an
eigenvector of $L_n(a,b)$ for all $a,b$. State the corresponding
eigenvalue of $L_n(a,b)$.
(c) Find an eigenbasis and the corresponding eigenvalues of
$J_n$. Clearly state the multiplicity of each eigenvalue.
What kind of multiplicity did you find? Geometric? Algebraic?
UPDATE (05-01 01:20) added the "What kind..." question.
Study LinAlg.
(d)
State the eigenvalues of $L_n(a,b)$ and their multiplicities.
Briefly reason your answer.
(e)
Find the eigenvalues of the complete graph $K_n$ and their multiplicities.
Hint. Use nothing but the definition of an eigenvector.
Hint. Use Rayleigh's Principle (08.94).
UPDATE (05-01 22:10) Erroneous reference 8.64 replaced by 8.94.
Hint. Rayleigh quotient.
Instructions. Prove and use the contraction-deletion
recurrence (03.166). Establish a contraction-deletion recurrence
for $\acyc(G)$. Prove it. (Be careful about the details, no handwaving).
Then use the two recurrences to prove Stanley's theorem by induction.
Make sure to say on what parameter you are inducting.
(b) Prove: If a rational number $r$ is a root of a polynomial with integer
coefficients with leading coefficient $a_n=1$ then $r$ is an integer.
Class #07, Tue, Apr 20
(a) Every edge of the graph $G$ is a bridge.
(b) $G$ is a forest. (A forest is a cycle-free graph.)
UPDATE (Apr 23, 22:50): the word "oriented" was added, and also its definition.
We say that $(A,\Abar)$ is a minimum $s-t$ cut for this flow network
if $c(A,\Abar)$ is minimal among all $s-t$ cuts.
Structure your proof. Clearly state before each stage of the
proof, what that stage will accomplish. If you use induction,
state, on what parameter you are inducting. If you can separate
out part of the proof as a lemma, do. Conceptual clarity is
paramount.
Class #06, Thu, Apr 15
Let $p:\nnn\to (0,1)$ be a function that associates a real
number between 0 and 1 with every positive integer.
Prove the following sharp threshold result.
(a) If $p(n)=o(1/n)$ then $q(n,p(n))\to 0$. In other words,
whp there will be no triangle.
(b) If $p(n)=\omega(1/n)$ then $q(n,p(n))\to 1$.
In other words, whp there will at least one triagle.
Include, in a separate, highlighted section of your solution,
the required asymptotic variance calculation. Note that
in Exercise 04.150, $p$ was assumed to be a constant,
and this assumption is not satisfied now, so the
asymptotics may be different.
Show all your work!
(d) A bowtie is a graph that consists of
two triangles that share a vertex. Let $K_4^-$ denote
the graph on 4 vertices with 5 edges. (This is $K_4$
minus one edge, or viewed another way, a pair of triangles
that share an edge.) Find a positive constant $c$
such that if $p(n)=O(n^{-1+c})$ then whp, no two triangles
will share a vertex (so there will be neither a bowtie nor
a $K_4^-$ in the graph). Make $c$ as large as you can.
Make your proof elegant and structured by formulating a lemma
about the sets $E(A,\Abar)$.
Class #05, Tue, Apr 13
This used to be a challenge problem (03.116); it is no longer.
You now have the tools.
(Comment. Some solvers of 2.145 attempted to prove that
co-circularity is transitive by claiming that there will
be a cycle in $H$ that contains both $e$ and $g$. This
exercise shows that this approach cannot succeed.)
(a) Determine $P(A_n)$, $P(B_n)$, and $P(A_n\cap B_n)$.
Your answer should be simple closed-form expressions using
binomial coefficients. Simplicity counts.
(b) Are $A_n$ and $B_n$ positively correlated, negatively correlated,
or independent? (The answer depends on $n$.)
Class #04, Thu, Apr 8
Input: graph $G=([n],E)$
Output: an independent set $A\subseteq [n]$
Notation: $N_G(v)=\{\text{neighbors of }v\}$ $(v\in [n])$
for $i=1$ to $n$
if $N_G(i)\cap A=\emptyset$
then $A:=A\cup\{i\}$
end(for)
return $A$
In particular, it follows that this is a lower bound on $\alpha(G)$.
(b) Deduce the same lower bound on $\alpha(G)$
from the Greedy Coloring Algorithm. (See handout.)
Notation. Let $H$ be a fixed graph. We say that
the graph $G$ is $H$-free if $G$ has no subgraph isomorphic to $H$.
Let $\ex(n,H)$ denote the maximum number of edges of $H$-free graphs
with $n$ vertices.
With some abuse of notation, in this context we write $G\not\supseteq H$
to indicate that $G$ is $H$-free. For instance, we write
$G\not\supseteq K_3$ to indicate that $G$ is triangle-free.
For example, all bipartite graphs are triangle-free.
Here $(n \bmod r)$ denotes the smallest non-negative remainder
of $n$ modulo $r$. For instance, $(57 \bmod 5)=2$ and
$T(57,5) = K_{11,11,11,12,12}$.
Recall that $r$-colorability of $G$ means that $r$ colors suffice, it
does NOT mean $\chi(G)=r$. What it means is that $\chi(G)\le r$.
This theorem tells us that even though not all $K_{r+1}$-free graphs
are $r$-colorable, the largest $K_{r+1}$-free graph (max number of edges
for a given number of vertices) is actually $r$-colorable.
We need to show that if $G=(V,E)$ is a $K_{r+1}$-free graph with
$n$ vertices and $m$ edges then $m\le |E(T(n,r))|$.
WLOG, we may assume that $G\supseteq K_r$. (DO: Why?)
We proceed by induction on $n$. If $n\le r$ there is nothing
to prove. (DO: Why?)
Assume $n>r$ and the theorem is true for $n'=n-r$
(Inductive Hypothesis).
Let $V=A\dot\cup B$ where $|A|=r$ and the induced subgraph $G[A]$
is a clique.
Let $E_G[A,B]$ denote the set of edges between $A$ and $B$.
04.73 DO Prove: $|E_G[A,B]|\le |A|\cdot |B|-|B|$.
Hint.
Prove: $(\forall b\in B)(\exists a\in A)(a\not\sim b)$.
04.75 SUMMARY Let us now place a copy of $T(n,r)$ on the
vertex set $V$ such that $A$ induces an $r$-clique in $T(n,r)$.
Observe:
UPDATE (4-25): Deferred to May 3 (due date previously listed as Apr 26)
This bound is tight, as shown by the complete bipartite graph
$K_{\lfloor n/2\rfloor, \lceil n/2\rceil}$.
The Lemma states $m$ inequalities. Let us add them up.
The right-hand side will be $mn$.
How many times does vertex $x$ feature on the left-hand side?
If that number is $c_x$ then we get that $\sum_{x\in V} c_x\deg(x)\le mn$.
04.110 Theorem (Caro, Wei) Let $G=([n],E)$ and let $d_i=\deg(i)$.
Then
$$ \alpha(G) \ge \sum_{i=1}^n \frac{1}{1+d_i}\,.$$
We prove this result by analyzing a randomized version of the
Greedy Independent Set algorithm. The only change we make to
the algorithm is that as a preprocessing step, we randomly
permute the vertices. So our sample space has size $n!$.
Let $Y_i$ denote the indicator of the
event $A_i$ that vertex $i$ (under the original labeling) is
added in the independent set $A$. Then $|A|=\sum Y_i$ and
therefore $E(|A|)=\sum E(Y_i)$. Now $E(Y_i)=P(A_i)$. Let
$B_i$ be the event that under the new ordering, $i$ precedes
all its neighbors. Observe:
Now, by the linearity of expectation, we obtain that $E(|A|)\ge \sum 1/(1+d_i)$
and therefore the observation that $\alpha(G) = \max |A| \ge E(|A|)$
concludes the strikingly elegant and unexpected proof. QED
Source: Noga Alon and Joel H. Spencer:
The Probabilistic Method. (Wiley, 1992, 2000).
Alon and Spencer also show how to derive the full power of
Turán's Theorem from the Caro-Wei Theorem.
We fix a set $V$ of $n$ vertices. For each pair $\{u,v\}$ of
distinct vertices we flip a biased coin to decide whether to
join $u$ and $v$ by an edge; we join them if the coin comes
up Heads. The probability of this event is $p$, and these $\binom{n}{2}$
events are independent.
The outcome of this experiment is a graph with vertex set $V$, so the
sample space is the set $\Omega$ of all the $2^{\binom{n}{2}}$ graphs on $V$.
04.144 DO Observe that for $G\in\Omega$ (a graph with vertex set $V$)
$$P(\calG = G) = p^m(1-p)^{\binom{n}{2}-m}$$
where $\calG$ is our random graph and $m$ is the number of edges of $G$.
Class #03, Tue, Apr 6
HISTORY. This problem was known as "Kneser's Conjecture" (1955)
after the proposer, Martin Kneser (1928-2004). In the 1960s,
Paul Erdős and András
Hajnal observed that Kneser's graph was in a way similar
to "Borsuk's graph" for which the Borsuk--Ulam theorem gave a tight
lower bound on the chromatic number. In 1978, László
Lovász formalized this intuition, reducing Kneser's conjecture
to the Borsuk--Ulam Theorem by a surprising topological method,
using high-dimensional simplicial complexes. Within weeks, Imre
Bárány gave an entirely different, elementary
reduction of Kneser's Conjecture to the Borsuk--Ulam Theorem,
using high-dimensional convex geometry.
Hint. It has 5 vertices.
Hint. It has 6 vertices.
STORY. Some years back I gave a summer math camp to 8th-graders.
I called the camp "Fun Math." One day I assigned this problem.
More than any other problem, this one caught their fancy.
Six of them went to the blackboard after class, trying to solve it.
One of them, a girl, succeeded. Lesson: DO NOT LOOK IT UP!!!
You are denying yourself the learning experience (and the fun) if you do.
This concept was introduced by G. D. Birkhoff in 1912.
Examples: (a) the divisibility poset
$([n], \mid)$: the set $[n]$ with the divisibility
relation; (b) The Boolean poset $(\calP([r]),\subseteq)$:
the powerset of $[r]$ (set of all subsets) with the "subset or equal"
relation. (This poset has $n=2^r$ elements.)
Note that this is a good characterization: an minimum chain cover
is an efficiently verifiable witness of the maximality of a given
antichain.
(1) The weak perfect graph conjecture: If $G$ is perfect then $\Gbar$
is perfect.
Note that this conjecture includes Dilworth's Theorem, in view of the very
simple exercise 03.205.
(2) The strong perfect graph conjecture: $G$ is perfect if and
only if neither $G$ nor its complement contains an induced odd cycle
of length $\ge 5$.
DO: the strong conjecture implies the weak conjecture.
The weak perfect graph conjecture was proved by László
Lovász in 1972; the proof is about 3 pages.
The strong perfect graph conjecture was proved in 2006 in a
180-page paper by Maria Chudnovsky, Neil Robertson, Paul Seymour,
and Robin Thomas.
Class #02, Thu, Apr 1
(a) Deduce this from the Cauchy--Schwarz inequality.
(b) Deduce this directly from the definition.
(c) State and prove the weighted version of this inequality.
Hint. Observe that $A(a_1,a_2,a_3,a_4)=A(A(a_1,a_2), A(a_3,a_4))$
and the analogous identity holds for the geometric mean. Use the
preceding exercise.
Use Theorem 02.52.
(Note: $0! = 0^0=1$, as every empty product is 1. This convention is
the natural analogue of the convention that every empty sum is zero.)
UPDATED 4-4 19:15 (multiple updates)
Note: "co-circular" is not a standard term, I invented it for this
exercise only.
Class #01, Tue, Mar 30
UPDATE 4-3 8:15 DM has been updated. Previously this exercise was
numbered 6.1.5.
($\deg(v)$ denotes the degree of the vertex $v$ and $m$ is the number
of edges.)
You can draw them by hand and
separately upload the sheet of images. Your pictures should be clean
and unambiguous. You do not need to prove anything about your pictures.
List your graphs in some logical order; indicate in the text how you
ordered them.
(a) $G$ is a tree.
(b) $G$ is connected and has $m\le n-1$ edges.
(c) $G$ is cycle-free (a forest) and has $m\ge n-1$ edges.
(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.
View the instructor's
class material from previous years
Return to the
Department of Computer Science home page
Course home
Go to top