8
$\begingroup$

In a combinatorial computation, I came across the following quantity:

Consider a finite meet semilattice $L$, that is, a finite poset which is closed under $\min$. Denote the least element of $L$ by $0$. Now, define $Z := \{ S \subset L : \min S = 0 \}$. I want to compute the quantity

$$ \chi := \sum_{S \in Z} (-1)^{|S|+1}. $$

I noticed that the complement $Z^c$ of $Z$ in $2^{L}$ (the collection of subsets of $L$ whose meet is not $0$) is a simplicial complex on $L$. Moreover, since the Euler characteristic of $2^L$ is $0$, the above quantity $\chi$ is actually just equal to the Euler characteristic of $Z^c$:

$$ \chi = \sum_{S \in Z^c} (-1)^{|S|}. $$

My question is:

  1. Is there any way to efficiently compute $\chi$ or bounds on it/approximations to it using some properties of $L$? (I already know that in many of the cases I'm interested in $\chi \ne 0$).
  2. Since (1) seems likely quite difficult to answer, especially in this general context, are there any references that can tell me more about the relationship between $L$ and $Z$ or $Z^c$, $H^{\cdot}(Z^c), \chi$, etc? These seem like natural enough objects to study, but I wasn't able to find a reference on them. When I look up simplicial complexes associated to a semilattice, mostly I find references to the order complex, which seems very different. I could find something called "the ideal zero divisor complex" for rings which seems similar, but I am working with a semilattice, not a ring, and elements, not ideals. I could also find information about zero divisor graphs of semigroups, which is related, but still rather far from the idea I'm looking for.

(And of course, I am actually only concerned about a very particular family of semilattices $L$, which happen to consist of certain partitions of {1,...,N}; the meet here is given by common refinement. I don't want to say too much about them here to avoid making the question too specific, but suffice to say I don't necessarily need a completely general answer to this question.)

$\endgroup$
  • $\begingroup$ Did you find any nice numbers or sequences (even conjectural) for nice families for partitions (e.g. whole partition lattice, etc.)? $\endgroup$ – John Machacek Nov 24 '20 at 15:18
4
$\begingroup$

This is a special case of the crosscut theorem. See e.g. Corollary 3.9.4 of Enumerative Combinatorics, vol. 1, second ed. Let $L'$ be $L$ with a top element $\hat{1}$ adjoined. In Corollary 3.9.4 take $X$ to be all elements of $L'$ not equal to $1$. We get $\chi=-\mu_{L'}(0,1)$, where $\mu_{L'}$ is the Möbius function of $L'$. There is lots of information about computing Möbius functions in the above reference.

$\endgroup$
6
$\begingroup$

To get a complete answer, I think you will need to use the specific properties of your semilattices. But I think the key observation is to notice what the maximal faces of your complex $Z_c$ are:

A subset $S$ of $L$ has meet $\bigwedge S>0$ if and only if there is some atom $a$ such that every element of $S$ is above $a$. (Here, "atom" means "element that covers 0", and the "meet" $\bigwedge$ is what you are calling "min".) Thus for every atom $a$, there is a maximal face of $Z_c$, consisting of $a$ and all the elements above it.

Since you know what the maximal faces are, you will probably want to see if you can use the combinatorics of your specific semilattices to make a ("nonpure") shelling of the complex in the sense of Björner and Wachs. If you find a shelling, you can compute the Euler characteristic of the complex using techniques in their paper "Shellable Nonpure Complexes and Posets. I." (Specifically, look at Section 3.)

$\endgroup$
  • $\begingroup$ I'm now looking back at this after a week and I'm surprised that Stanley's answer has so few upvotes and hasn't been accepted. My answer was "fun" but complicated and speculative. Stanley's answer is probably the easiest way to compute $\chi$. $\endgroup$ – Nathan Reading Dec 1 '20 at 22:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.