nor's blog

[Tutorial] Generalized Möbius Inversion on Posets
By nor, 3 years ago, In English

https://nor-blog.codeberg.page/posts/2021-12-27-mobius-inversion-on-posets/

  • Vote: I like it
  • +364
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +32 Vote: I do not like it

One question I've always had about this kind of generalized Mobius inversion/PIE: what techniques are there to effectively find a closed form for the Mobius function of some nontrivial poset? You can find terms computationally using general formula, but this could be quadratic time or otherwise too slow for some reason. Are there any good general techniques? For instance, how can you find the Mobius function for the poset of partitions of $$$n$$$ labelled elements, compared by inclusion?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    I've had this question for a while now as well. I usually tend to go for guessing and induction, but there is a technique that's quite useful when there is a nice substructure property.

    • If $$$P, Q$$$ are two locally finite posets, then the Mobius function for $$$P \times Q$$$ is just the product of the Mobius function for $$$P$$$ and the Mobius function for $$$Q$$$.
    • If we restrict the Mobius function of a poset $$$P$$$ to the interval $$$[x, y]$$$ for some $$$x, y \in P$$$, the resulting function is the Mobius function of the poset $$$[x, y]$$$.

    Using these for the poset (actually lattice) of partitions, let $$$A$$$ and $$$B$$$ be two partitions, with $$$B$$$ being a refinement of $$$A$$$. Then it suffices to solve for the case when $$$A$$$ is the trivial partition (we can take the products for the Mobius function corresponding to each block that $$$A$$$ partitions the set into). Then using a simple induction, if there are $$$n$$$ blocks in $$$B$$$, the Mobius function in the case when $$$A$$$ is the trivial partition is $$$(-1)^{n - 1}(n - 1)!$$$.

    There are some more results here but I'm not sure which ones make computing the Mobius function computationally feasible in the general case.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      By the way, in this special case, there's an interesting view of this closed form: we're doing PIE on permutations which do not alter the partition. When doing PIE on permutations, each permutation should just be weighted by its sign. $$$(-1)^{n-1}$$$ is precisely the sign of an $$$n$$$-cycle, and $$$(n-1)!$$$ is precisely the number of possible $$$n$$$-cycles.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        I was trying to understand the argument, but didn't understand what you meant by "doing PIE on permutations which do not alter the partition". How do you relate this to the Mobius function in this case, and what exactly does PIE on permutations mean? Thanks in advance!

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +16 Vote: I do not like it

          Consider the problem of trying to count the number of sequences of $$$n$$$ distinct elements satisfying some condition, using PIE to cancel out sequences where some particular subsets of elements (a partition) are equal; the weights in this are precisely the Mobius function.

          Then, we can count this using PIE on permutations which fix the sequence. For any sequence with possibly equal elements, the sum of the signs of permutations which fix the sequence is 1 iff all elements are distinct, and 0 otherwise. This is exactly the condition we wanted for our Mobius function, so grouping permutations back up by their cycle decomposition partition, we get the original desired Mobius function.

          → Reply
»
3 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Good blog!

For russian speakers there is, for example, this video where prof. Andrei Raigorodskii explains exactly this (but more briefly). Actually, there is probably a recording of almost every lecture of this course (basic combinatorics and number theory) since 2013 (though not all of them are on youtube).

→ Reply