Homework assignments

Assignment 1, due Wednesday, January 15.

Long before the due date, carefully read Ziegler, Lecture 0.

Ziegler, Lecture 0: Problems 0, 5.
You don't need to do the open-ended question at the end of Problem 5.

Additional problems:
1. Show that the expression for conv(K) given on page 4 is indeed convex. (There are two expressions for conv(K) on that page. I mean the first, more general one that does not assume a finite set.)
2.
a. Given an affine subspace S=x+L for L linear, and any point y in S, show that S=y+L.
b. Prove the the affine hull of n points is at most n-1-dimensional.
c. Prove that a set {x1,...,xn} is affinely independent if and only if there do not exist constants c1,...,cn, not all zero with Σci=0 and Σcixi=0

Assignment 2, due Wednesday, January 22.

Ziegler, Lecture 0: Problems 3, 9.

Assignment 3, due Friday, February 7.

Long before the due date, carefully read Ziegler, Lecture 1, Sections 1.1-1.4.

Ziegler, Lecture 1: Problems 3, 4, 5. For Problem 5: In keeping with the pattern of other Farkas Lemmas, put "but not both" into the statement.
For these problems, feel free to use anything we know from your reading in Lecture 1.

Additional Problems:
1. Fix a point x0 in a polyhedron P. Show that the lineality space of P is {y in Rd: x0+t y is in P for all t in R}.
2. Let P be a polyhedron. If F is any nonempty face of P, then lineal(F)=lineal(P).
You'll want to use Additional Problem 1 to prove Additional Problem 2.

Assignment 4, due Friday, February 28

Note that Assignment 5 is also due Friday, February 28 (for reasons we discussed in class), but I am calling them two separate assignments for bookkeeping reasons. Long before the due date, carefully read Ziegler, Lecture 2, Sections 2.1-2.2.

Ziegler, Lecture 2: Problems 0, 2, 4, 7.

Notes:
• For Problem 0, you must also show that if a polyhedron P has a vertex, then its lineality space is {0}. You'll want to use both "Additional Problems" from the previous homework. The notation F0-x0 in the problem is not set-theoretic subtraction. It is {x-x0 : x is in F}. (Some of your books might have a typo in this problem. If you see an "F" and an "F0" in the problem, they should be the same thing.)
• For Problem 4, you can't use any part of Theorem 2.7 that was proved using polar duality (specifically the "coatomic" property and the fact that L(P)op is the face lattice of a polytope). (By the way, the problem should say "proper face".)
• For Problem 7, think about "How does your algorithm fail..." but don't write an answer to that question. For the last question in Problem 7, the notation "P with a superscript triangle" will be defined later. For this question, the only thing you need to know about it is that it is the polytope whose face lattice is L(P)op in Theorem 2.7(iv).

Assignment 5, due Friday, February 28

Long before the due date, carefully read Ziegler, Lecture 2, Sections 2.3 through 2.6.

Ziegler, Lecture 2: Problems 9, 10, 14.

These problems require some detailed comments:

• First, Problem 9 is wrong as stated. Typically the set (Fdiamond)triangle is not even bounded.
Here's a little philosophy about polar duality (and in particular a reason why Ziegler would state this wrong): The real point of polarity is that for any polytope, if you turn the face lattice upside-down, you get the face lattice of a polytope, and the new polytope is "polar dual" to the original polytope. To prove what we want about this combinatorial duality, we need an explicit geometric construction of the polar dual polytope and of its faces (the F^(diamond) thing). But once you have that construction, you want to think combinatorially. When I see (F^(diamond))^(triangle), I think "the polytope whose face lattice is dual to L(F^(diamond))." That's what Ziegler was thinking when he wrote the problem, and that's what you should think to do it.
When you do this problem, you should first correct the problem by giving the correct geometric construction of a polytope dual to Fdiamond. (It's an easy modification of what Ziegler did.) You should then forget all about "linear functionals evaluating less than or equal to 1" and think combinatorially about duality.
For the "Describe a more direct construction..." part, I will be satisfied with an answer about the iterated face figure. There is a direct, non-recursive construction. If you want to find it, I'll count that as an extra (optional) problem.

• Next, some comments about Problem 14.
First, in my book there is a typo X in the problem that should be A.
Second, in (ii) I don't see how to do it with a Farkas Lemma. (Do you?) Instead, I have a solution that looks like we're in an analysis class.
Third, there is a subtlety about (i) that bothered me for years, until I finally got it straight. For one thing, (i) can fail for polyhedra. To see this, look no further than R1. The statement fails for the polyhedron in R1 defined by x≤0. (Can you get x≤1 as a linear combination of the defining inequalities? i.e. as a multiple of x≤0?) For another thing, the statement can fail for polytopes in Rd of dimension lower than d. Again, in R1, consider the polytope (a single point, 0) given by x≤0 and x≥0. (Can you get x≤1 as a linear combination of the defining inequalities?) But nonetheless, the statement is true for d-polytopes in Rd.
Finally, when Ziegler asks about rescuing uniqueness in (iii), I think he means (iv).

I said above that there are subtleties in Problem 14 that bothered me for years. By that I mean, while I was teaching this class multiple times. So, think hard about these, but don't panic if you don't work them all out.

Assignment 6, due Friday, March 21

Long before the due date, carefully read Ziegler, Lecture 3, but in Section 3.3, you only need to read page 83.

Ziegler, Lecture 3: Problems 0, 3, 4(i), 5.

For Problem 3, find a very explicit direct solution without using Corollary 0.8. (Reduce the problem to finding a polynomial with certain properties, and then give a simple formula for the polynomial.)
For Problem 5, don't worry about the Hirsh conjecture, of course, because it's false. But do prove the inequality Ziegler asks for.

"Floating" Reading assignment (not due)

Sometime during the semester, read the part of Lecture 4 before Section 4.1 and also Sections 5.1 and 5.2, even though I'm not assigning homework on them.