Most but not all homework is assigned from the instructor's
Lecture notes (LN) (PDF, 96 pages)
DO problems: do not hand in. Point equivalents are stated for your information. These problems, like all others, may recur in tests.
17.1 DO: LN 8.1.2 (eq 3 pp), 8.1.3 (eq 2 pp), 8.1.5 (eq 1 p)
17.2 DO: LN 8.1.6 (eq 5pp), 8.1.7 (eq 4 pp).
17.3 LN 8.1.8 (12 points)
17.4 DO: 8.1.16 (eq 5 pp)
17.5 DO: 8.1.17 (eq 3 pp), 8.1.18 (eq 3 pp)
17.6 Let G be a connected undirected graph with n ≥ 2 vertices. Consider the simple random walk on G: the states are the vertices of G; the transitions are to each neighbor of the current state with equal probability, so pij=1/deg(i) if i and j are adjacent, zero otherwise. Prove that the vector π with π(i)=deg(i)/(2m) is a stationary distribution (where m is the number of edges). (8 points)
DO problems: do not hand in. Point equivalents are stated for your information. These problems, like all others, may recur in tests.
16.1 Give a closed-form expression for the generating function of the sequence bn=n22-n. (7 points)
16.2 Let g(x) be the generating function of the
sequence "2n choose n."
(a) Find the convergence radius of g(x). (7 points)
(b) CHALLENGE PROBLEM. Find a simple closed-form expression
for g(x).
16.3 DO: Let rn be the number of ways one can pay n pennies as a combination of pennies, nickels, dimes, and quarters. For instance, r12 = 4, the possible combinations being 1 dime + 2 pennies; 2 nickels + 2 pennies; 1 nickel + 7 pennies; 12 pennies. Find a closed-form expression for the generating function of this sequence. (Equivalent to 8 points.)
16.4 DO: Consider the recurrence
an=an-1+8an-2-12an-3
with initial values
a0=a1=0, a2=1.
(a) Give a closed-form expression for the generating function of this
sequence. (Equivalent to 7 points)
(Hint: your denominator should factor as (x-2)2(x+3).)
(b) Find an explicit formula for an.
(Equivalent to 7 points)
16.5 Let f(x) be the generating function of the
Fibonacci numbers modulo 5 (so the coefficients are mod 5
residue classes). Formally, this generating function looks
the same as the generating function over the integers, and
it appears to have the same closed-form expression.
(a) Factor the denominator modulo 5. Notice something notable about
the factors. (6 points)
(b) Use the result of (a) to obtain a very simple
explicit formula for the Fibonacci numbers modulo 5. (8 points)
16.6 CHALLENGE PROBLEM. Let N denote the set of nonnegative integers. We try to partition N into m ≥ 2 infinite arithmetic progressions. This is of course possible, for instance we can take the residue classes mod m; this way we partitioned N into m arithmetic progressions each with increment m. (The "increment" is the difference between consecutive terms in the sequence.) But we want the increment of each arithmetic progression in our partition be different. Prove that this is impossible.
Posted Tuesday, 11-14, 5:50pm; due Thursday, 11-16, before class.
"DO" exercises: do not hand them in.
15.1 DO: redo the midterm problems without time pressure.
15.2 DO: In a digraph, if there is a directed walk from vertex x to vertex y then there is a directed path from x to y.
15.3 DO: A DAG (directed acyclic graph) is a digraph without directed cycles. A topological sort of a digraph is a numbering of the vertices such that every edge is increasing (goes from smaller to greater number). Prove: given a digraph G, a topological sort of G exists if and only if G is a DAG. -- Notice that this is a GOOD CHARACTERIZATION: existence of something is equivalent to the nonexistence of another thing.
15.4 A tournament is a directed complete graph; every edge is oriented in exactly one direction (so for every pair x,y of vertices, exactly one of the edges x→ y and y→ x is present). Prove: every tournament has a Hamilton path (a directed path through all the vertices). (8 points)
15.5 CHALLENGE PROBLEM (requires group theory) Prove that the automorphism group of a tournament is solvable.
Posted Thursday, 11-9, 11pm; due Tuesday, 11-14, before class.
14.1 Find a planar multigraph which has two essentially different plane representations in the sense that the corresponding dual graphs are not isomorphic. Find the multigraph with the smallest possible number of edges. Draw your multigraph in two ways and draw each dual. (4 points)
14.2 Let L be the multigraph which has just 1 vertex and two edges (naturally, both edges are loops). Draw L on the torus (toroidal chessboard) in such a way that there will be only one region. With which chess piece could you associate your drawing? (4 points)
14.3 Prove: if a simple planar graph has n ≥ 3 vertices and it has no triangles then m ≤ 2n - 4. (Here m is the number of edges and n the number of vertices). (6 points)
14.4 Prove: every planar graph has a vertex of degree ≤ 5. (6 points)
14.5 Prove: there exists a positive constant c such that the probability that a random graph is planar is (a) less than (1+c)-n; (b) less than (1+c)-n2 . (6+6 points; a correct solution to part (b) alone earns all the 12 points)
14.6 What is the minimum number of edges of a connected nonplanar graph with n vertices? Prove your answer (both that such a graph with the number of edges you indicate exists and that it has the smallest possible number of edges. (6 points)
14.7 Let A1,...,An be events and let B denote the complement of their union. Then the Inclusion-Exclusion formula says P(B) = S0 - S1 + S2 - + ... Prove: (a) P(B) ≥ S0 - S1; (2 points) (b) P(B) ≤ S0 - S1 + S2. (6 points) (c) State and prove the general case. (3 points; you get all the 11 points for a correct solution of (c) alone.)
Posted Tuesday, 11-7, 7pm; due Thursday, 11-9, before class.
13.1 Prove: more than half of the vertices of a tree have degree ≤ 2. (6 points)
13.2 We want to arrange n books on k shelves. What matters is which books get on which shelf, and also the order in which they appear on each shelf matters. The amount of space between adjacent books does not matter. Count the arrangements. (It is permitted to leave a shelf empty; each shelf alone can hold more than n books, so for instance putting all books on a single shelf is permitted.) Your answer should be a simple closed-form expression. (6 points)
13.3 A (0,1)-matrix is a matrix of which every entry is 0 or 1. A submatrix is defined by removing a subset of the rows and a subset of the columns. They don't need to be contiguous; so the number of submatrices of an n × n matrix is (2n -1)2 (verify!). A submatrix is homogeneous if it is either all-zero or all-one. Let N=2k. Prove that there exists an N × N (0,1)-matrix which does not have a 2k × 2k homogeneous submatrix. (15 points)
12.1 Find the independence number of the knight's graph on the 5 by 5 toridal chessboard. Prove your answer. (6 points)
12.2 Challenge problem. Determine or estimate the chromatic number of the King's graph on an n by n toroidal chessboard.
12.3 Construct a triangle-free graph (graph containing no K3) of chromatic number 4. Your graph should be as small as possible. Hint. Your graph should have 11 vertices and 5-fold rotational symmetry. -- You do not need to prove that 11 is the smallest possible number of vertices of such a graph, but you do need to prove that the graph you constructed is not 3-colorable. (6 points)
12.4 Challenge problem. For every k, construct a triangle-free graph of chromatic number at least k.
12.5 Let G be a directed graph (read definition in LN). Suppose every vertex has out-degree at most k. Prove that the chromatic number of G is at most 2k+1. (10 points) (Legal colorings of directed graphs are defined the same way as for undirected graphs; if there is an edge from i to j then the colors of vertices i and j must differ.)
12.6
This result sometimes allows proving lower bounds on the chromatic
number.
Let G be a graph with n vertices.
Prove: &chi(G) ≥ n / α(G). (5 points)
(χ(G) is the chromatic number;
α(G) is the independence number of G.
12.7 Challenge problem. Prove: if G is a triangle-free graph with n vertices then χ(G)=O(√ n).
12.8 Determine the expected number of triangles in a random graph. (5 points; out of these, 3 points go for the clear definition of your random variables.)
12.9 Challenge problem. Asymptotically evaluate the variance of the number triangles in a random graph. Your result should be a very simple expression which is asymptotically equal to the variance in question (while the number of vertices approaches infinity). Compare your result with the variance of the number of heads in a sequence of "n choose 3" coin flips. Which random variable is more concentrated?
12.10 Challenge problem. Prove: every graph with m edges contains a bipartite subsgraph with at least m/2 edges. Hint. Expected value.
12.11 Review the Erdős--Rado "arrow notation" in Ramsey Theory. DO: Prove 6 → (3,3). (Do not hand in.)
12.12 Extend the arrow notation to more than 2 edge-colors. Define and prove the relation 17 → (3,3,3). (10 points)
Posted Tuesday, 10-31, 11:05pm; due Thursday, 11-2, before class.
11.1 Problem 10.8 is due Thursday with this problem set.
11.2 DO: study the bijective proof of Cayley's formula via Prüfer's Code (Matoušek - J. Nešetríl text)
11.3 LN 6.1.8 (2+2 points)
11.4 [LN 6.1.21] THIS PROBLEM WAS POSTED BY MISTAKE, do not hand in. It is identical with Problem 10.7.
11.5 DO: LN 6.1.18, 6.1.19 (do not hand in)
Posted Sunday, 10-29, 1:00am; due Tuesday, 10-31, before class (problems 10.1 -- 10.7).
10.1 LN 2.4.9 (5+5 points)
10.2 LN 2.7.10 (10 points)
10.3 LN 6.1.5 (1+1+4 points)
10.4 LN 6.1.6 (a)(b) (5+5 points)
10.5 Challenge problem: LN 6.1.6(c)
10.6 LN 6.1.16 (8 points; you lose 2 points for every mistake up to 4 mistakes)
10.7 LN 6.1.21 (5 points)
10.8 Prove: the number of spanning trees of a graph is not greater than the product of the degrees of its vertices. (12 points) Deadline for this problem: Thursday, 11-2. Please do NOT hand it in on Tuesday, 10-31.
Posted Tuesday, 10-24, 11:45pm; due Thursday, 10-26, before class.
9.1 DO: Solve Quiz 1(PDF) without the time pressure. (Do not hand in but do this by Thursday; the solutions will be discussed in the discussion session which you are supposed to attend.)
9.2 DO: LN 2.4.2. (Do not hand in.)
9.3 LN 2.4.7 (5+5 points)
9.4 DO: LN 2.4.12 (Do not hand in.)
Posted Saturday, 10-21, 2:40pm; due Tuesday, 10-24, before class.
8.1 (Conditional probabilities) Diseases A and B have similar symptoms. Let W be the population of all patients showing these symptoms. The two diseases can only be differentiated by costly tests. We know (from sampling the population and performing these costly tests) that 70% of W have disease A, 25% have disease B, and 5% have some other disease. We consider the effectiveness of treatment T. We know that 60% of the patients with disease A respond to T, while only 12% of the patients with disease B respond to treatment T. From the rest of the population W, 40% respond to treatment T.
(a) A new patient arrives at the doctor's office. The doctor determines that the patient belongs to W. What is the probability that the patient will respond to treatment T? (4 points)
(b) ("Probability of causes") The patient's insurance will not pay for the expensive tests to differentiate between the possible causes of the symptoms. The doctor bets on treatment T. A week later it is found that the patient did respond to the treatment. (b) What is the probability that the patient had disease A? (6 points)
8.2 [Prove: if there exist k nontrivial independent events then the sample space has size ≥2k.] THIS PROBLEM WAS POSTED BY MISTAKE, do not hand in. It is identical with Problem 7.2.
8.3 We roll n dice. Let X be the product of the numbers shown. Determine E(X). (4 points)
8.4 Construct two random variables over the same probability space such that they are uncorrelated but not independent. Make your sample space as small as possible. (5+2+3) (5 points for a correct solution; 2 additional points if your sample space was minimal; and 3 more points if you can prove that a smaller sample space would not suffice.)
8.5 We roll three dice. The dice show the numbers X, Y, Z.
(a) What is the size of the sample space for this experiment? (2 points)
(b) Are the random vaiables X+Y and X+Z uncorrelated, positively correlated, or negatively correlated? Compute the covariance of these two variables. (5 points)
(c) Partition the sample space into six classes A1,...,A6 so that the random variables X+Y and X+Z become independent under each condition Ai. (7 points) Independence of the random variables R and S under condition C means (&forall r,s (reals))(P(R=r and S=s | C)= P(R=r | C)P(S=s | C).
8.6 LN 7.2.11 (4 points)
8.7 LN 7.2.13 (6 points; out of this, 4 points go for the clear and accurate definition of the auxiliary random variables you introduce. No underage members admitted to the club.)
8.8 Challenge problem. LN 7.3.11. (No deadline, separate sheet.)
Posted Wednesday, 10-18, 1:20am; due Thursday, 10-19, before class.
7.1 LN 7.1.17 (6 points)
7.2 LN 7.1.25 (5 points)
7.3 LN 7.1.2, 7.1.3, 7.1.5, 7.1.7 DO (do not hand in)
7.4 LN 7.2.3, 7.2.4, 7.2.5, 7.2.8 DO (do not hand in)
7.5 LN 7.1.27 Challenge Problem.
Posted Saturday, 10-14, 12 noon; due Tuesday, 10-17, before class.
6.1 We have n identical chocolate bars and we want to distribute them between k kids so that each of them gets at least two. Count the number of possible outcomes. Your answer should be a very simple expression. As always, prove your answer. (4 points)
6.2 Prove: the product of k consecutive integers is always divisible by k!. (5 points) (This is an AH-HA problem - it has a one-line solution, but it is a clever line.)
6.3 LN 2.2.9 "DO," do not hand in.
6.4 LN 2.2.10 (7 points) You need to refer to the definition of limit in your solution and prove that (∀ε>0)(etc.)
6.5 LN 5.1.2 "DO," do not hand in. Use the prime property directly, do not use the full power of the Fundamental Theorem of Arithmetic.
6.6 LN 5.1.7 (3 points) (An AH-HA problem.)
6.7 LN 5.1.13 (3 points)
6.8 Let the power series expansion of 1/√(1-x) be ∑n=0∞ anxn. Prove that an is asymptotically equal to c/√n for some constant c. Determine the value of c. (7 points) ---- Notice that a previously and a currently assigned problem from LN are relevant. (Which problems?) If you are not sure of the answer to the previously assigned problem, make sure to see Hari Monday evening (5-6pm, Ry 28).
6.9 Challenge problem. (No deadline, separate sheet, hand directly to instructor.) Let Tn denote the number of those subsets of [n] whose cardinality is divisible by 3. Prove: |Tn - 2n/3| < 1.
Posted Tuesday, 10-10, 3:40pm; due Thursday, 10-12, before class.
5.1 LN 2.2.6 parts 1,2 "DO" - do not hand in
5.2 LN 2.2.6 part 3 (4 points)
5.3 LN 2.2.7 (5 points) (Prove your answer; elegance counts)
5.4 LN 2.2.12 Challenge problem (write on separate sheet, hand to instructor; no point value, no deadline)
5.5 LN 5.1.1 (3 points)
5.6 LN 5.1.3 (4 points)
5.7 LN 5.1.5 (3 points)
Posted Friday, 10-6, 11:30pm; due Tuesday, 10-10, before class.
All numbers appearing in these problems are integers. p always denotes a prime number.
4.1 Prove: there are infinitely many primes that are congruent to -1 mod 4. (4 points)
4.2 Prove that 561 is a Carmichael number, i.e., if a is relatively prime to 561 then a560≡1 (mod 561). (5 points)
4.3 Find all primitive roots mod 17. Prove your answer. (4 points)
4.4 What is the number of primitive roots mod p between 1 and p? State and prove your answer. (6 points)
4.5 LN 4.1.18 (4 points)
4.6 LN 4.1.19 (4 points)
4.7 LN 4.1.23 (4 points) Show all calculations. Do not use calculators except for division/multiplication. Elegance counts.
4.8 LN 4.1.24 (a) (b) (c) (4+2+6 points)
4.9 LN 4.1.25 (4 points) Your proof should be one-line!
4.10 LN 4.1.26 (5 points)
4.11 Challenge problem (no deadline, no point value; if you hand in a solution, do it on a separate sheet and give it directly to the instructor after class). Prove that all Carmichael numbers are square-free.
Please PRINT your name on each sheet and
state your status on the front page
("2nd year CS grad," "3rd year undergrad math major," etc.)
Posted Tuesday, 10-3, 3:40pm; due Thursday, 10-5, before class.
All numbers appearing in these problems are integers.
3.1 Prove: if a ≡ b (mod m) then gcd(a,m)= gcd(b,m). (5 points)
3.2 Let n be a positive integer. Prove: ∑d|n φ(d) = n.
(Here, φ is Euler's phi function. The summation is over all positive divisors of n.) (6 points)
All numbers appearing in these problems are integers.
2.1. Prove: if d is a common divisor of a and b and d is also a linear combination of a and b then d is a greatest common divisor of a and b. (5 points)
2.2. LN 1.2.5 (d) (f) (3+3 points)
2.3. LN 1.2.6 (6 points)
2.4. LN 2.1.4 (a) (6 points); (b) (challenge problem, no point value, no deadline)
2.5. LN 4.1.15 (b) (c) (2+7 points)
2.6. LN 4.1.17 (a) (b) (c) (d) (e) (2+3+3+3+3 points)
2.7. LN 4.1.21 (5 points)
2.8. LN 4.1.22 (a) (b) (3+3 points); (c) (d) (challenge problems, no point value, no deadline)
2.9. LN 4.1.27 (a) (b) (c) (d) (2 points each)
1.1. LN 1.2.5 (a) (b) (c) (h) (3+3+4+4 points)
1.2 LN 4.1.16 (a) (b) (8+4 points)