jump to navigation

## A question for the combinatorialists				August 21, 2009

Posted by Ben Webster in blegs, combinatorics.
trackback

One of the points of combinatorics I never really learned is how to play correctly with Mobius functions. I mean, I can state Mobius inversion for an arbitrary poset if you give me a moment, but it all ends up a bit hard to manipulate.

This is particularly frustrating since I know that there are a certain number of people out there in the world who know all these tricks by heart. One of them should make a cheat sheet for all these identities.

So, here’s a question that might be easy to answer, but that I can’t quite muddle my way through. Let $P$ be a ranked poset (in my example, it’s flats of a matroid) with unique minimal element 0 and maximal 1 and Mobius function $\mu$. Is there any better expression for the sum

$\sum_{p\in P} (-1)^{\mathrm{rk}(p)}\mu(0,p)\mu(p,1)$?

About these ads

Like Loading...

## Comments»

1. David Speyer - August 21, 2009

I thought about this for a bit this morning, but didn’t reach any strong conclusions — I couldn’t do anything with it, but it looks like the sort of thing that should simplify. Maybe this note will inspire someone else to come out of the woodwork.

I find the easiest way to think about mobius function identities is to think about the matrix M whose (i,j) entry is mu(i,j). So M^{-1}, as you no doubt know, is the (0,1) matrix encoding the poset relation. You are interested in MDM, where D is the diagonal matrix keeping track of the sign twist. That didn’t get me anywhere, though…

2. Gil - August 21, 2009

It does not look to me as something that should simplify for general posets. (But I will be happy to learn otherwise.)

3. Harrison - August 21, 2009

Have you worked through some nontrivial proportion of the exercises in the appropriate chapter of Stanley? (Yeah, I haven’t either, but there’s no royal road to combinatorics, and that’s probably the best way — maybe the only way — to really learn it. Certainly it’s the only way to learn algebraic geometry.)

Alternatively, I guess, you could try asking Stanley himself…

4. Hugh Thomas - August 28, 2009

A couple of thoughts:
* the Mobius function of the lattice of flats of a matroid (a “geometric lattice”) is described by Rota’s NBC basis theorem. See, for example, Blass and Sagan’s 1997 paper in Advances, which generalizes it. (Though Rota’s result could be in EC1 too; I don’t have my copy around.)
* geometric lattices are EL-shellable. This means that there is a labelling of the edges of the Hasse diagram of the poset such that the Mobius function of an interval is the number of unrefinable chains from the bottom to the top of the interval such that the labels strictly decrease as you read up the chain. Your sum is capturing chains which increase at most once (though with what seems an odd choice of sign) and with the chains which are decreasing everywhere counting either once or zero times, depending on the parity of the rank of the whole poset. (I guess there is a way to state your formula in terms of the “flag f-vector” of the poset, but so far as I know, that doesn’t help.)

Neither of these ideas seems to obviously yield something useful, but maybe it’ll make more sense in context. If you want more details/references, let me know.

%d bloggers like this:
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 3, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9355035424232483, "perplexity_flag": "head"}