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 {x₁,...,x_n} is affinely independent if and only if there do not exist constants c₁,...,c_n, not all zero with Σc_i=0 and Σc_ix_i=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 x₀ in a polyhedron P. Show that the lineality space of P is {y in R^d: x₀+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 F₀-x0 in the problem is not set-theoretic subtraction. It is {x-x₀ : x is in F}. (Some of your books might have a typo in this problem. If you see an "F" and an "F₀" 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 (F^diamond)^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 F^diamond. (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 R¹. The statement fails for the polyhedron in R¹ 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 R^d of dimension lower than d. Again, in R¹, 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 R^d.
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 Monday, March 24

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.

Assignment 7, due Wednesday, April 9

Long before the due date, carefully read Ziegler, Lecture 6 up to and including 6.5(a).

Ziegler, Lecture 6: Problems 1, 3, 5, 8, 13.

Note that Problem 1 is not about signed vectors. It is about the subspace a-Dep(V).
For Problem 5, I couldn't see how to use Farkas II, but succeeded in using Farkas I. (If you see Ziegler's "simple application of Farkas II" here, I'd love to hear about it.) Also in Problem 5, when you "Describe a small vector configuration...", you must find a configuration that spans the ambient space. Remember that Ziegler uses "vector configuration" (as opposed to "point configuration") to signal that we are talking about linear dependencies, values, etc.
In Problem 13, you can ignore the question "Is this really a Gale transform of C_d(n)?"
You should also think about Problem 9. What would you do? A simpler problem is to determine all 3-polytopes with 6 vertices. (Doing even the simpler problem completely is too long for homework, so don't turn anything in.)

Assignment 8, not due

However, all the reading and Lecture 7, Problems 1 and 2 and Lecture 8, Problems 13(ii), 13(iii), and 18, and Additional problem 1 might be helpful for final prep. All the problems might be useful for qual prep.

Carefully read Ziegler, Lecture 7, through Section 7.3 and Lecture 8, through Section 8.3.

Ziegler, Lecture 7: Problems 1, 2.
In Problem 2, think about how you would answer the two "What about..." questions, but you don't need to write a solution.

Ziegler, Lecture 8: Problems 13, 18, 28.
For Problem 18, you should say why the "obvious" equation is obvious.

Additional problems:

1. Find the h-vectors of all of the platonic solids that are simplicial.

2. Find the h-vectors of the dual polytopes to the permutohedra. Start at low dimension and move to higher dimension as far as seems reasonable. (For this assignment, at least you should do the 3-dimensional case.) There is a general statement, but it may take more time than you want to invest in the assignment. The nice way to get at the general statement: Any linear extension of the weak order is a shelling order on the dual permutohedron. How would one prove that? What answer does it lead to and how?

Assignment 9, not due, but recommended for qual prep

Problems:

1. Work out what Kruskal-Katona says for graphs (i.e. 1-dimensional complexes). (Be careful about what d means...in this case, d=2.) There is one equation and one inequality. For each possible number f₁ of edges from 1 to 11, what are the possible values of f₀? Explain in simple terms (in terms of graphs), what the inequality means. Remember that when we say "1-dimensional complex", we don't necessarily mean "1-dimensional pure complexes". The complex could have some 0-dimensional facets also. (Make sure you know what that means.)

For this problem, "work out" means more than just quoting the inequality for f₀. You should actually write out what the computed-out inequality says, and then explain it. 2. Work out what Kruskal-Katona says for 2-dimensional complexes. (Same warning about d and about this not meaning "2-dimensional pure complexes", and same explanation of "work out".) There is one equation and two inequalities. You can now explain one of these inequalities in very few words! (and you should write those words). For each possible number f₂ of edges from 1 to 11, what are the possible values of f₁? Think about (but don't turn in an answer to) the following questions: What does the other inequality mean? Why does the minimum possible f₁ sometimes change more and sometimes less when f₂ increases by 1? Think about this in terms of simplicial complexes, not just in terms of the statement of Kruskal-Katona.

3. Suppose Δ is a simplicial complex of dimension d-1 with f-vector (f_-1, f_-1, ..., f_d-1) as usual. Prove the following facts about the h-vector of Δ.
a. h₀ = 1
b. h₁ = f₀-d
c. h₀ + h₁ + ... + h_d = f_d-1
d. h_d is (-1)^d-1 times the reduced Euler characteristic of Δ.

4. Write down, in terms of f-vectors, what Dehn-Sommerville says about simplicial 3-polytopes. (Again, watch out for indexing issues: 3-polytopes have 2-dimensional boundary complexes, so use the version of Dehn-Sommerville for simplicial 2-spheres.) You should literally translate the equations h₀ = h₃ and h₁ = h₂ into equations relating entries of the f-vector, rather than just using Problem 18 from Lecture 18. (Why is that not the same thing?)

5. Write down, in terms of f-vectors, what Dehn-Sommerville says about simplicial 4-polytopes. (Again, watch out for indexing issues and literally translate the equations.)