Dedekind numbers | jblblog

Dedekind numbers

Posted on June 5, 2023 by JBL

Assigned in my graduate combinatorics class in early April, 2023:

As observed in class, $C_n \cong \mathcal{J}(\cdots \mathcal{J}({\bf 1})\cdots )$ where $\bf 1$ is the one-element poset. Let $2\cdot {\bf 1} = {\bf 1} \uplus {\bf 1}$ be the two-element antichain.

What is $\mathcal{J}(2\cdot {\bf 1})$ ?

What is $\mathcal{J}(\mathcal{J}(2\cdot {\bf 1}))$ ?

What is $\mathcal{J}(\cdots \mathcal{J}(2\cdot {\bf 1}) \cdots )$ , where $\mathcal{J}$ is iterated $n$ times? (Of course, prove it.)

The preceding questions suggest that the same thing should be easy starting with any antichain. And indeed, the first step is easy: if $n\cdot {\bf 1}$ is the $n$ -element antichain, then $\mathcal{J}(n \cdot {\bf 1}) = B_n$ is the Boolean lattice (because every subset of an antichain is an order ideal). In the next step, the poset $\mathcal{J}(\mathcal{J}({\bf n})) = \mathcal{J}(B_n)$ is the poset of order ideals of the Boolean lattice. Its cardinality (the number of order ideals in $B_n$ ) is called the $n$ th Dedekind number. Look at https://oeis.org/A000372 and https://arxiv.org/abs/2304.00895 (noting in particular the date of the preprint in the second link) and write a short paragraph about the state of human knowledge concerning Dedekind numbers, and how it makes you feel.

(Some relevant links for orientation: this is about partially ordered sets, and specifically about the Fundamental Theorem of Finite Distributive Lattices (the symbol $\mathcal{J}(P)$ is the lattice of lower sets of the poset $P$ ). Or just jump straight to reading about Dedekind numbers, which can be defined in a variety of ways.)

This entry was posted in Combinatorics, Education, Math and tagged Partially ordered sets. Bookmark the permalink.

Leave a comment