4
$\begingroup$

A question on accurate attribution/description:

Lemma.- Let $Q$ be a collection of subsets of a finite set $V$, and let $S_0\subset Q$. Then $$\left|\mathop{\sum_{S_0\subset S\subset Q}}_{\bigcup S = V} (-1)^{|S|}\right|\leq 2^{|V|},$$ where we write $|X|$ for the number of elements of a finite set $X$.

The proof isn't hard (basically three lines - use inclusion-exclusion, then change the order of summation, then use inclusion-exclusion again). Taking a look at the proof of Rota's cross-cut theorem, it seems to me that the idea of the proof is the same in both cases.

Question: is it accurate to call this Lemma a special case of Rota's cross-cut theorem? (Question 2: is it really just a rephrasing of Rota's cross-cut theorem, i.e., equivalent to it?)

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ I should add that the connection to Rota's cross-cut theorem was pointed out to me in an answer to mathoverflow.net/questions/364743/… $\endgroup$
    – H A Helfgott
    Commented Aug 19, 2020 at 13:33
  • $\begingroup$ This might depend on what you mean by the cross-cut theorem. The version for the Mobius function is a consequence of the topological cross cut theorem which says the order complex of a poset is homotopy equivalent to a certain simplicial complex built from the cross cut. The Mobius function result then follows from computing Euler characteristics. $\endgroup$
    – Benjamin Steinberg
    Commented Aug 19, 2020 at 14:09
  • $\begingroup$ I meant the cross-cut theorem for the Möbius function. $\endgroup$
    – H A Helfgott
    Commented Aug 19, 2020 at 14:19
  • 2
    $\begingroup$ I normally think of Rota's crosscut theorem not as an inequality but as an equality (giving a formula for the Möbius function), so for that reason alone I would hesitate to call your lemma a "special case" of Rota's theorem. As for whether it's equivalent, Rota's theorem applies to an arbitrary geometric lattice, and unless I'm missing something, it doesn't seem that an arbitrary geometric lattice can be easily reduced to the setting of your lemma as stated. You might try emailing Bruce Sagan directly because he has thought a lot about generalizations of Rota's theorem. $\endgroup$
    – Timothy Chow
    Commented Aug 19, 2020 at 18:33
  • $\begingroup$ So, should I call it an immediate consequence of Rota's crosscut theorem (to which I might as well give a self-contained proof)? Or is it not really an immediate consequence? $\endgroup$
    – H A Helfgott
    Commented Aug 19, 2020 at 20:20

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .