MA 4143/6143 - Homework















Starred* problems should be completed if you are enrolled in the course at the 6000 level.
I recommend (but do not require) that all students read and attempt these problems. If you make some significant progress, you should turn it in.

Homework 7 10, due Apr 29 at 2pm

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

A. Without using any theorems that we stated but did not prove, show that the 1-skeleton of the icosahedron is 3-connected.

B. Suppose G is a graph with a torus-embedding.
i) What should the definition of a face of the torus-embedding be?
ii) Find a graph embedding on the torus with |V| - |E| + f = 0, where f is the number of faces of the embedding.

Homework 7 9, due Apr 22 at 2pm

Matoušek-Nešetřil p189: 1a, 2b
Matoušek-Nešetřil p195: 1

A. Draw K6 on the Klein bottle.

Homework 7 8, due Apr 15 at 2pm

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

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.

Suggested practice problems for Exam 2

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

Homework 7, due Mar 25 at 2pm

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

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

Homework 6, due Mar 18 at 2pm

Matoušek-Nešetřil p123: 2, 4, 5, 10, 12*
Matoušek-Nešetřil p129: 1, 5

Homework 5, due Feb 27 at 2pm

Matoušek-Nešetřil p116: 1, 2, 3, 5abc, 6

A. Show that the graph Cn has 2n distinct automorphisms.
Hint: Consider where the vertices 1 and 2 are sent to.

Homework 4, due Feb 11 at 2pm

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

Homework 3, due Feb 4 at 2pm

Matoušek-Nešetřil p73: 5*, 9, 10ab, 13, 19

A. How many ways are there to sit n people at a circular table? (Two seatings are considered the same if every person has the same left neighbor in both seatings.)

B. 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 28 at 2pm

Matoušek-Nešetřil p64: 2
Matoušek-Nešetřil p67: 6ab*, 7a
Matoušek-Nešetřil p73: 2, 3a, 11, 15

Homework 1, due Jan 21 at 2pm

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.

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.