THE HOMEWORK EXERCISES ARE ASSIGNED FROM THE 3RD EDITION!
HOMEWORK 1: (DUE: Sept. 15
Monday)
Chapter 1: 1, 2, 10;
Chapter 2: 1, 2, 9;
Math students should do 5 out of 6, non-math students 4 out of 6 problems.
HOMEWORK 2: (DUE: Sept. 29
Monday)
Chapter 3: 3;
Chapter 4: 2, 3, 4, 5;
Chapter 5: 3;
Note: Some problems are hard! Math students should do 5 out of 6, non-math students 4 out of 6 problems.
HOMEWORK 3: (DUE: Oct. 13
Monday)
Chapter 5: 4;
Chapter 6: 1, 2, 3,
Problem #5: (i) Prove that there is a constant a>0, and N, such that for each n> N, the probability that the
median degree of G(2n+1,1/2) is between n-100 and n+100 is at least a.
(consider the degree sequence d_1< = d_2 <= ....<= d_{2n+1}, and d_{n+1} is the median degree.).
(ii) (HARD) Prove that there is a a constant a>0, and N, such that for each n> N, probability that the median degree of G(2n+1,1/2) is n is at least a.
(iii) (COULD BE HARD) Is it true that almost surely the median degree of of G(2n+1,1/2) is n?
Problem #6: N+1 plates are laid out around a circular dining table, and a hot cake is passed between
them in a manner of a symmetric random walk: each time it arrives on a plate,
it is tossed to one of the two neighboring plates, each with probability 1/2.
The game stops at the moment when the cake has visited every plate at least once.
Show that, with the exception of the plate where the cake began, each plate has probability 1/N of being the last plate visited by the cake.
Problem #7: Let S be a symmetric random walk with S_0=0, and let N_n be the number of points that have
been visited by S exactly once up to time n. Show that E[N_n] = 2.
Note: Some problems are hard! Math students should do 5 out of 7, non-math students 4 out of 7 problems.
HOMEWORK 4: (DUE: Nov. 10.
Wednesday)
Chapter 7: 1, 2, 3;
Chapter 8: 1, 2;
Proof of Theorem 8.3.1, t>0 case.
HOMEWORK 5: (DUE: Dec. 3.
Wednesday)
Chapter 17: 1, 4, 6, 8, ;
Problem 5: Prove that the number of triangle-free labelled
graphs with n vertices is at most 2^{n^2/4+o(n^2)}.
Problem 6: Consider a graph with 3n vertices, n Red, n Blue and n Green.
Add edges randomly: an edge connecting a RB pair of vertices is chosen with probability p_1,
an edge connecting a RG pair of vertices is chosen with probability p_2,
an edge connecting a BG pair of vertices is chosen with probability p_3,
where p_1*p_2*p_3=n^(-2) and p_1 >= p_2> = p_3 >= t/n^2 (for some t).
Prove that with probability at least 1-3/t-1/n there is a tri-colored triangle.
HOMEWORK 6: (DUE: Dec. 15.
Monday)
Problem 1: Let G be a graph with n>10 vertices and suppose that if any new edge is added to G then
the number of the copies of K_10 increases. Prove that G has at least 8n-36 edges.
Problem 2: A finite sequence a_1, a_2, a_3, ..., a_n is non-repetitive if it does not contain a
sequence of the form x_1, x_2, ..., x_m, x_1, x_2, ..., x_m, as a subsequence of
consecutive terms. Prove that there exists an infinite non-repetitive sequence
over any 15-element set of symbols.
Problem 3: Show that for n sufficiently large there is a graph with n vertices, with chromatic number at least n/2 and clique number at most n^{3/4}.
Problem 4. Suppose that p=c/n, where c is fixed and n is sufficiently large (i.e. tending to infinity).
(a) Prove that w.h.p G(n,p) contains no set of vertices with s=|S|< n/(20 c^2)
such that S contains (at least) 2s edges.
(b) Show that w.h.p. the maximum degree D<= ln n/ lnln n.
(c) Show that w.h.p. the vertices of degree at least 2 ln n/(3 lnln n) form an independent set.
Problem 5: Using probabilistic method, prove the following: Let G be a given graph with
n vertices and minimum degree d>100. Prove that V(G) can be partitioned into two sets X and Y such that
|X|<= O((n ln d)/d) and every vertex Y has at least one neighbor in X and at least one neighbor in Y.
Problem 6: Show that every bipartite graph G has a C_4-free subgraph with at least 1/2|E(G)|^{2/3} edges.