Starred* problems should be completed if you are enrolled in the course at the 6000 level.
I recommend that all students with a reasonably strong background read and attempt these problems. If you make some significant progress, you should turn it in.

Final homework, not to be collected

Matoušek-Nešetřil p195: 2, 6
Matoušek-Nešetřil p204: 3
Matoušek-Nešetřil p214: 1

A. If α and β are arcs with α(1) = β(0), then explain in detail how to "glue" α and β to get an arc γ so that γ(0) = α(0) and γ(1) = β(1).

Homework 12, due Apr 21 at 11am

Matoušek-Nešetřil p195: 1, 3, 5

A. Draw K6 on the Klein bottle.

B. What is the image of the "equator" under the sterographic projection map? (In case it's not already clear, the equator is the intersection of the unit sphere with the plane z = 0.)

C. This problem is about the stereographic projection map. Recall that o is the "North pole" (0, 0, -1 1).
i) Find an equation (parametric or symmetric) for the line between o and v = (x, y, z).
ii) Using your answer from part (i), find an explicit formula for the stereographic projection of v.

Homework 11, due Apr 12 at 11am

Matoušek-Nešetřil p175: 8
Matoušek-Nešetřil p189: 1, 2b

A. Let X consist of m points in an n-dimensional vector space V.
     i) Describe (using a pseudocode approach similar to the examples in class) the greedy algorithm for finding a maximal independent subset of X.
     ii) Show that your algorithm yields a basis for V if and only if X spans V.

Homework 10, due Apr 5 at 11am

Matoušek-Nešetřil p158: 6, 7
Matoušek-Nešetřil p175: 1, 2, 3, 5

Homework 9, due Mar 24 at 11am

Matoušek-Nešetřil p148: 2ab, 5
Matoušek-Nešetřil p158: 1, 2, 4

A. Show that the graphs pictured on p198 are all 2-connected.

Homework 8, due Mar 8 at 11am

Matoušek-Nešetřil p129: 9
Matoušek-Nešetřil p136: 2, 5, 8, 10*
Matoušek-Nešetřil p148: 1

Remark: A "graph with loops and multiple edges" is another way to say a "multigraph with loops", as we defined in class.

Homework 7, due Mar 1 at 11am

Matoušek-Nešetřil p123: 9b, 10
Matoušek-Nešetřil p129: 1, 5, 6
Matoušek-Nešetřil p225: 5a

Hint: For 9b, it may help to expand out (I + A)n-1 using (an analogue of) the Binomial Theorem.

Homework 6, due Feb 22 at 11am

Matoušek-Nešetřil p116: 5abc, 6, 7*
Matoušek-Nešetřil p123: 1, 2, 4, 5

Homework 5, not to be collected

Matoušek-Nešetřil p103: 6
Matoušek-Nešetřil p106: 7
Matoušek-Nešetřil p116: 2, 3
Matoušek-Nešetřil p123: 4

Homework 4, due Feb 8 at 11am

Matoušek-Nešetřil p103: 3, 4
Matoušek-Nešetřil p106: 1, 2, 3, 6

Homework 3, due Feb 1 at 11am

Matoušek-Nešetřil p73: 4, 9, 10ab, 11, 19

A. Prove that the sum from k = 1 to n of k⋅(n choose k) is n⋅2n-1.

Hint on 9: {1, 3, 6, 8} are no-two-consecutive because {1, 2, 4, 5} are distinct!

Homework 2, due Jan 25 at 11am

Matoušek-Nešetřil p64: 2
Matoušek-Nešetřil p66: 1, 6ab*, 7a
Matoušek-Nešetřil p73: 2, 3a

Homework 1, due Jan 18 at 11am

Students taking the course as 6143 need not do 1.3.1, and any student who has taken Foundations may replace 1.3.1 with the starred problem, 3.1.5.
Students who have not had Foundations will certainly want to read Chapter 1.3 carefully, and will likely also want to read through Chapter 1.2.

Matoušek-Nešetřil p15: 6
Matoušek-Nešetřil p23: 1, 2, 3a
Matoušek-Nešetřil p64: 4, 5* (esp. part b)

Hint: on 1.2.6, it may be helpful to show that each side is contained in the other.