Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
Vidit, I'm indeed well aware that Forman and Brown's papers both apply to regular CW complexes (and indeed even a bit more broadly). But 1) regular CW-complexes correspond pretty directly with simplicial complexes via barycentric subdivision, and 2) a regular CW-complex is still a geometric object. I was saying, if somewhat imprecisely, that discrete Morse Theory questions are interesting on the order complex of the poset, and not so much on the poset itself.
I stand corrected -- there are indeed some other variants of discrete Morse theory that apply to other objects. Maybe there is also one for posets. Certainly a similar matching technique will always help calculate the Moebius number (but this is near trivial.) In any case, I was thinking of the original theory of Forman, Brown, et al. I'll try to edit to reflect.
The discrete Morse matching exactly gives you in this case a CW complex with some number of 0 cells and some number of (n-1) cells. What can such a complex look like?
The nonnesting (or possibly noncrossing) arc diagrams, items (p) and (q) on Stanley's list, look like a promising object to find a bijection with. One would just need to find a good way of labeling the vertices with nonnegative integers that describes the arc pattern...
@quid: I edited to correct and avoid confusion. Perhaps someone else will know more about the history of the conjecture, and why it is credited to Frankl rather than Duffus.
@quid: Maybe not. I certainly didn't track it down! I saw a reference (Doug West's page on the conjecture, IIRC) which gave a year of 1979 and referred to the Handbook of Combinatorics. But it's possible that the conjecture was made at a conference/similar, and not written down until much later; this would make giving a reference quite difficult.
How are your matroids represented? If you have them represented as a set of circuits, then there's a clear algorithm that will check your condition in time $m^2$ (where $m$ is the total number of circuits). But I believe passing from the maximal independent set representation to the circuit representation to be NP-hard...
This is an example of the general technique of using indicator variables to calculate an expected value. Some more (easier) examples are worked out at mikespivey.wordpress.com/2011/12/01/indicator-variables or in your favorite Intro Probability textbook.
@Greg Martin: Every step in the real game involves 2 colors, say $i$ and $j$, and is counted by $X_i$ and $X_j$. Thus, the number of steps in the real game is half the sum of the $X_i$'s. (But as you note, for any fixed $i$, there are steps in the real game that are ignored by $X_i$.) Linearity of expectation then says that the expectation of the sum is the sum of the expectations.
