Comments on homework sets

Problem Set 6

1. Watch out for initial conditions! A lot of students correctly reasoned that $r(A^3_m) - r(A^3_{m-1}) = r(A^2_{m-1})$. Summing up $r(A^2_i)$ from $i=0$ to $m-1$ is not quite exactly what we want, though -- we need to add $1$ to account for $r(A^3_0) = 1$.
2. An isomorphism of posets is stronger than just a bijection -- the bijection must be compatible with the partial order in both directions (it's not even enough to say $x < y$ implies $f(x) < f(y)$).
3. There were no complete solutions to this problem. Many students successfully showed $rank(A) \geq n-k$, and a few identified the remaining snag: how do we know that there aren't intersections of dimension less than $k$ whose Mobius function values cancel? One reason is that the intersection poset of a hyperplane arrangement always has a Mobius function which alternates in sign along ranks (this itself is not necessarily obvious and needs to be proved), so Mobius function values on the same rank can never cancel.
4. Generally quite good -- students who didn't already do so might want to think of a combinatorial reason for the region count (i.e., a proof for the count that doesn't use Theorem 2.5).
5. The final step of at least one path through this problem involves coming up with the exponential generating function for set partitions where the parts are ordered. We can use something analogous to the Exponential Formula here -- whereas $e^{(e^x-1)}$ counts (unordered) set partitions, $1/(1-(e^x-1))$ counts ordered set partitions -- why? This can be seen as an example of the Compositional Formula (ECII, Theorem 5.1.4), which is a more general (though not that often more useful) version of the Exponential Formula.