Assignment 1, due Tuesday 15 January:
READ Chapters 1 and 2 of
the book. This shouldn't be too hard, but
do pay attention. There are some words in there that we didn't talk
about in class.
PROBLEMS:
Type 1: 1.1, 1.5, 2.1, 2.3, 2.6, 2.10, 3.2, 3.4, 4.2
Type 2: 1.2, 2.2, 2.4, 2.8, 2.11, 3.5
Type 3: 2.9
Type 4: 2.5, 3.10, plus the following:
Let p be a prime number of the form 4k+1 (where k is an
integer). Form a graph G(p) with vertices {0,1,...,p-1} and
with an edge connecting vertex i to vertex j if and only if
i-j is a square mod p. (Except make it a simple graph: don't
put a loop at i even though 0 is a square.)
Prove that G(p) is isomorphic to its complement.
[By definition a number k is a square mod p if there is some
integer x such that x2 is congruent to k mod p.]
Assignment 2, due Tuesday 22 January:
READ Sections 5 and 6 (that's
the first half of Chapter 3).
PROBLEMS:
Type 1: 5.1, 5.4, 6.1, 6.4, 6.5
Type 2: 2.13(i), 2.14(i), 5.6, 6.7, plus the following:
Let G be a graph with adjacency matrix A. Prove that the number
of WALKS (not paths as I misstated originally) of length n between
vertex i and vertex j is equal to the (i,j) entry of the matrix An.
(Thanks to Louis for pointing out my blunder.)
Type 3: 5.3
Type 4: 5.10, 6.8, plus the following:
Prove that if the edges of the graph K17 are each colored either
red,
white, or blue, then the graph must contain either a completely red
triangle, a completely white triangle, or a completely blue triangle.
Assignment 3, due Tuesday 29 January:
First, remember that if
I asked you to revise your first homework, the revision
is due Tuesday. Turn in the original together with the revision.
Second, READ Sections 7
and 8 in the book.
PROBLEMS:
Type 1: 7.2, 7.6, 8.1, 8.5, 8.6
Type 2: 6.6 [We were having so much fun not finding Hamiltonian cycles
that I didn't get a chance to define a "line graph." See problem
3.9.
It might help to do parts of that problem to get a feel for line graphs.]
7.3, 7.4, 7.5, 8.3 - OOPS, this one is harder than I originally thought,
8.4
Type 3: 7.7 - in both parts, it should say SIMPLE graph
Type 4: Let H(m,n) be the graph with mn vertices arranged in an m
x n grid,
with edges connecting each vertex to its nearest neighbors to the north,
east, south, and west. (So if you draw H(9,9) it looks like a checkerboard.)
Figure out which m and n make H(m,n) Hamiltonian.
Assignment 4, due Tuesday 5 February:
PROBLEMS:
Type 1: 9.2, 9.4, 9.8
Type 2: 9.3
Type 3: 9.11
Type 4: 9.13, plus: Formulate a conjecture about the number
P(n) of parking
functions from {0,1,...,n-1} to {0,1,...,n-1}.
Revisions of assignment
2 are due Thursday 7 February.
Here is a homework calendar, to help keep track of all the dates.
Assignment 5, due Tuesday 12 February:
READ Section 11
PROBLEMS:
Type 1: 10.1, 10.2, 10.4, 11.1, 11.8
Type 2: 11.2, 11.3, 11.4, 11.7, 11.9
Type 3: 10.5
Type 4: Prove that there are (n+1)(n-1) parking functions
on the set {0,...,n-1}.
REVISIONS of assignment
3 are due Thursday 14 February.
SECOND REVISIONS of assignment
1 are due Tuesday 12 February.
Assignment 6, due Tuesday 19 February:
PROBLEMS:
Type 1: 12.1, 12.3, 12.4, 12.7, 12.10, 14.1
Type 2: 12.2, 12.6, 12.9, 14.2
WAIT! 12.9 is not correct as stated. Part (ii) is only 3/4
correct. If a graph is
outerplanar then it cannot have a subgraph contractible to K4
or K2,3 and it also
cannot have a subgraph homeomorphic to K4. But it COULD
have a subgraph
homeomorphic to K2,3. Can you think of an example?
Type 3: 12.8
Type 4: 12.13
And if you feel like it,
try drawing K7 on the surface of a torus without any edges crossing.
There's a revision due Thursday:
check the calendar to keep up to date.
By popular request, we're having a TEST
on THURSDAY, 28 February. Here
is a review
sheet
of sorts. [Added 5 March: there is a solution
key for your perusal outside my office door.]
[Update 26 March: solutions are no longer
posted on my door. Ask me if you want to see them.]
Assignment 7, due Tuesday 26 February:
PROBLEMS:
Type 1: 13.1, 13.8, 14.3, 14.5
Type 2: 13.2, 13.4, 13.7, 14.4
Type 3: 13.5
Type 4: 13.11, 14.7
There are also zillions
of revisions and things like that...check the calendar.
Assignment 8, due Tuesday 12 March:
READ Section 18, twice,
slowly. (It's two pages long.)
PROBLEMS:
Type 1: 17.1, 17.5, 17.7
Type 2: 17.2, 17.4, 17.6
Note: Proving your answer for 17.2 takes some work (especially the
second one).
Type 3: 17.8
Type 4: Show that X(R2) is at most 7. [Hint:
find a coloring!]
Also, show that X(R2) is at least 4. [Hint: I can
only think of one strategy for how
to do this. What's your strategy?]
Assignment 9, due Tuesday 26 March:
PROBLEMS:
Type 1: 15.1, 15.4, 19.2, 19.3, 19.5, 20.1
Type 2: 15.2, 19.1, 20.2, 20.5
Type 3: 19.4
Type 4: Find an upper bound for X(Rn) (for all n).
This means find a function f(n) such
that X(Rn)<f(n) for all n. [Hint: this is not
as hard as it sounds. Generalize one of
the upper bounds for X(R2).]
Various REVISIONS are due
Thursday 28 March.
ENJOY your spring break
(with lots of crayons).
Assignment 10, due Tuesday 2 April:
READ Section 22
PROBLEMS:
Type 1: 20.7, 22.1, 22.3
Type 2: 20.6, 20.8, 22.4
Note: There's a solution to 20.6 in the book, but write it up anyway.
Type 3: 15.9
Note: There's a solution to this one in the book too, but again,
write it up anyway.
You can only follow the book's argument if you understand it.
Type 4: none this week
Assignment 11, due Tuesday 9 April:
PROBLEMS:
Type 1: 23.1, 23.2, 23.3
Type 2: 22.5, 22.7, 23.5
Type 3: #2 from the worksheet (Prove that every flock of chickens
has at least one king.)
Type 4: #6 from the worksheet (Can a flock have exactly two kings?)
Assignment 12, due Tuesday 16 April:
READ Section 25 (it's easy)
PROBLEMS:
Type 1: 24.1 (i) and (ii) [just do the first sentence], 24.2 (i),
25.1, 25.3
Type 2: 25.2, 25.5, #4 from the 11 April worksheet (Find a stationary
distribution for the
Markov chain described in #1 on the 9 April worksheet with n=2.)
Type 3: 25.6
Type 4: none this week
The type
3 is due THURSDAY 18 April.
Assignment 13, due Tuesday 23 April:
PROBLEMS:
Type 1: 26.1, 26.6(i), 27.2, 28.2, 29.5
Type 2: 26.2, 26.4, 29.2, 29.6
Type 3: none this week
Type 4: 28.3
That's it. ALL REVISIONS ARE DUE BY THURSDAY 25 APRIL.
We have a FINAL
EXAM on
Wednesday 1 May at 12:00-3:00
pm.