2
$\begingroup$

In perusing A kind of Eulerian numbers connected to Whitney numbers of Dowling lattices I have gotten confused over what seems a very elementary point. The beginning of section 2 of the paper is

Let $X = \{x_1, \dots , x_n\}$ be a finite set with $n$ elements. A partial partition of $X$ is a partition of a subset of $X$. That is, $\alpha = \{A_1, \dots , A_r\}$ is a partial partition of $X$, when $A_i \ne \varnothing$ $(i = 1,\dots, r)$, $A_i \cap A_j = \varnothing$ $(i \ne j)$ and $\cup_{i=1}^r A_i \subset X$ [ed. here I think $\cup_{i=1}^r A_i \subseteq X$ is really intended]. The elements of $\alpha$ are called blocks. Let $Q_n$ be the set of all partial partitions of $X$. The set $Q_n$ can be partially ordered: let $\alpha \le \beta$ if every block in $\beta$ is a union of blocks from $\alpha$. So ordered, $Q_n$ is isomorphic to the lattice of partitions of an $(n + 1)$-set $X \cup \{x_{n+1}\}$.

While it is certainly true that these two lattices (viz., partial partitions of $[n]$ and partitions of $[n+1]$) have the same number of elements, I don't see how the last sentence above can be true. For instance, the lattice $\Pi_3$ of partitions of $[3]$ has three maximal chains, while as far as I can tell the lattice $Q_2$ has only two. Am I missing something or is the quoted claim (which appears immaterial to the actual thrust of the paper) incorrect?

$\endgroup$
  • $\begingroup$ The claim sounds correct, with the natural mapping that elements not contained in any block of a partial partition get lumped with $x_{n+1}$ in the full partition. $\endgroup$ – hardmath Jan 25 '16 at 14:16
  • $\begingroup$ @hardmath - your mapping is why the two lattices clearly have the same size. But when I draw $Q_2$ I get two maximal chains, viz. $() \le (1) \le (1)(2) \le (12)$ and $() \le (2) \le (1)(2) \le (12)$, while for $\Pi_3$ the three maximal chains are $(1)(2)(3) \le (12)(3) \le (123)$, $(1)(2)(3) \le (13)(2) \le (123)$, and $(1)(2)(3) \le (1)(23) \le (123)$. $\endgroup$ – S Huntsman Jan 25 '16 at 14:27
  • 2
    $\begingroup$ It's not true that $(1)\le(1)(2)$: $(2)$ is not a union of blocks of $(1)$. In fact, $\alpha\le\beta$ implies that $\bigcup\alpha\supseteq\bigcup\beta$. $\endgroup$ – Brian M. Scott Jan 25 '16 at 15:23
  • $\begingroup$ @BrianM.Scott- thanks for your comment. I'd been using the order for $\Pi_{\le n}$ (a la Hanlon, Hersh, and Shareshian) instead of $Q_n$ and didn't notice these were different. $\endgroup$ – S Huntsman Jan 25 '16 at 16:13
2
$\begingroup$

You don't have $(1) \le (1)(2)$ because $(2)$ is not a reunion of blocks from $(1)$, just like you don't have $(1)(23) \le (1)(2)(3)$ because $(2)$ isn't a reunion of blocks from $(1)(23)$.

You can prove that the natural bijection $f : \alpha \mapsto \alpha \cup \{ \{x_{n+1}\} \cup X \setminus \bigcup \alpha \}$ preserves the ordering.

If $\alpha \le \beta$ then every block of $f(\beta)$ that was in $\beta$ is still a reunion of blocks from $\alpha$ hence of blocks of $f(\alpha)$. And the new block in $f(\beta)$ is the reunion of the unused blocks from $\alpha$ and the new block in $f(\alpha)$. So $f(\alpha) \le f(\beta)$

Conversely, if $f(\alpha) \le f(\beta)$ this is almost direct because the blocks of $\beta$ are also in $f(\beta)$ so they must be reunions of blocks of $f(\alpha)$. Since blocks in $\beta$ don't contain $x_{n+1}$ they can't use the new block of $f(\alpha)$ so they can only take blocks of $\alpha$. So $\alpha \le \beta$.

$\endgroup$
  • $\begingroup$ It didn't occur to me that the partial order they used might be different than the one I had in mind, so obviously this is what I missed. Thanks! $\endgroup$ – S Huntsman Jan 25 '16 at 15:50

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.