Math 511: Spring; 2023
Homework Assignments

Topics and Readings

1. (1/18-20) Counting the four types of set function S → X. Falling factorials (x)_n. Bases for polynomials and basis conversion between monomials and falling factorials. Partition lattice Π_n. (Goal: Counting techniques and formulas.)
2. (1/23-27) Chapter 1; §§1-2. Omit the topology. Treat the infinite cases lightly. Our class is mainly concerned with finite combinatorics.
3. (1/27-30) §1.3. Lattices.
4. (1/30-2/1) §1.4. Partitions.
   Omit everything after Lemma 1.4.2. The only thing I care about on entropy is this characterization property. Such extremal properties are a standard topic of investigation.
5. (2/1-3) §1.3. Distributive lattices; Birkhoff's theorem.
6. (2/8) §1.5. Relations; mainly their abstract properties. Matrix rank. Poset closure.
   Omit the relative sum.
7. (2/10-22) §§2.1-2. Matchings.
8. (2/24) §2.3. Matrices.
9. (2/26-3/1) §2.4. Submodular functions; independent matchings.
10. (3/6-10) §2.6. The Birkhoff polytope of doubly stochastic matrices.
11. (3/13) §2.7. The Gale-Ryser Theorem.
12. (3/15-3/29) §3.1. The Möbius function.
13. (3/31-4/12) §3.2. Poset theorems.
14. (4/12-4/14) §3.3. Sperner theory. (Omit Littlewood–Offord at the end of the section.)
15. (4/17-4/26?) §3.5. Modular and geometric lattices. Plus: Chromatic polynomial of a graph. Regions of a hyperplane arrangement.
16. (4/28-5/1) §4.1. Generating functions.
17. (5/2-3) §4.2-3. Polynomial sequences of binomial type (lightly); umbral calculus (slightly).

Homework Problems

Additional Exercises

• 1.1.9b*. See Laura's correction to this problem in the errata. Decide whether she is right or wrong.
• A1. Prove that the set Π_n of partitions of [n] is a lattice, using the definitions of meet and join in terms of the refinement ordering.
• 2.4.1a*. Prove that the set of real-valued, normalized, submodular functions satisfying unit increase, on a finite set S, is closed under taking convex combinations and is bounded. Can you find its extreme points? Is it a convex polytope (i.e., has it a finite number of extreme points)?
• 2.4.1(b-c). See how far you can get. You can use (b) in working on (c), if necessary, even if you didn't solve (b).
• A2. Here is a beautiful matching problem suggested by Hao. He describes a game (a real game) in which there are 9 boxes and 10 different toys (called A, B, ..., J for simplicity) with no duplicate toys. Each box contains one toy. The 9 toys in the boxes are all different. You can open a box of your choice by paying $5. If the toy is J, you can sell it for a lot of money, but if it's not J, you can't get any money for it. You are provided the following information: for each box, a list of 3 toys that are not in the box.
  (a) Is it possible to decide, knowing the 9 lists, whether toy J is in a box? (You don't have to decide which box.) We assume it depends on the lists, so the question can be restated in two parts: Is is possible, for some list, to say J is in no box? Is it possible, for some list, to say J is in a box? And if so, which lists?
  A solution.
  (b) Generalize this problem in any way that occurs to you. The more, the better.
• A3. We know that if A is a maximal antichain and C is a maximal chain in a finite poset, then |A ∩ C| ≤ 1. Is it possible for A ∩ C to be empty? Prove or disprove.
• A4. In Sperner's proof of his theorem (page 137), prove that no antichain that has elements of both ranks $\frac12(n-1)$ and $\frac12(n+1)$ can have maximum size. (This is stated incorrectly in the book; see the errata.)