MA 4143/6143 - Homework















Starred* problems should be completed if you are enrolled in the course as 6143.
I recommend (but do not require) that Mathematics majors who have taken Foundations read and attempt these problems. If you make some significant progress, you should turn it in.

Homework 11, due Apr 30 at 11am

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

A. Prove that any tree is planar.
Hint: It may be easier to prove the stronger statement that a tree has a planar embedding where every arc is a straight line segment.

Homework 10, due Apr 23 at 11am

Matoušek-Nešetřil p175: 4
Matoušek-Nešetřil p189: 1a, 2ab
Matoušek-Nešetřil p195: 1, 2ab

A. Draw K6 on the Klein bottle.

B. Prove that any graph with an R2-embedding has an embedding on the torus.
Hint: If you use the construction of the torus by identifying sides of the square, then you might find it somewhat enlightening to find a map from a continuous bijection from R to an open interval. One such example is given by tan-1x!

1. Your book calls a "planar drawing" what I've been calling an R2 embedding. It may affect your reading of book exercises.
2. In p189 #2a, the main thing to check is that the graph is really K4,4. This shouldn't be too difficult. Part b is more interesting.

Homework 9, due Apr 9 at 11am

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

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 8, due Apr 2 at 11am

Matoušek-Nešetřil p124: 9b
Matoušek-Nešetřil p152: 2
Matoušek-Nešetřil p158: 3*, 4, 5, 9
Matoušek-Nešetřil p165: 1a

Hint on p124 9b: Expand out (I + A)n-1 using (a slight extension of) the binomial theorem. Why is every entry of this matrix non-negative?

Homework 7, due Mar 26 at 11am

Matoušek-Nešetřil p136: 8
Matoušek-Nešetřil p148: 1, 2ab, 5*
Matoušek-Nešetřil p152: 1
Matoušek-Nešetřil p158: 1

A. In the correspondence that Dr. Dobson discussed last friday, what automorphism of the Petersen graph does the permutation 21435 (given in one-line notation) correspond to?

Homework 6, due Mar 7 at 11am

Matoušek-Nešetřil p117: 6
Matoušek-Nešetřil p123: 4
Matoušek-Nešetřil p136: 7, 10ab, 10c*

A. Prove that a minimum length walk between v and w is a path.

Homework 5, due Feb 26 at 11am

Matoušek-Nešetřil p107: 5a (don't use the formula for D(n))
Matoušek-Nešetřil p117: 5
Matoušek-Nešetřil p123: 2, 5, 10
Matoušek-Nešetřil p129: 1, 5*, 7

Hint on p107 5a: What happens when you remove n from the permutation (in an opposite way to how it was added in 3)?

Homework 4, due Feb 14 (due to Snow Day) at 11am

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

A. How many pairwise nonisomorphic graphs are there on 4 vertices? Describe the graphs, and find the number of graphs on {1,2,3,4} isomorphic to each of them. (Make sure your total number of graphs adds to 64.)

Homework 3, due Feb 5 at 11am

Matoušek-Nešetřil p73: 9, 13, 15b, 24b*, 25ab
Matoušek-Nešetřil p103: 1

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.)

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

Homework 2, due Jan 29 at 11am

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

Homework 1, due Jan 22 at 11am

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.