4
$\begingroup$

The boolean lattice of rank $n$ (noted $B_n$) is the subset lattice of $\{1,2, \dots , n \}$.
See the Hasse diagram of $B_3$ below:
enter image description here

The Hasse diagram of $B_n$ is of length $n$, with $2^n$ vertices and $n2^{n-1}$ edges.

Question: Is the converse true? In other words:
Is a lattice with Hasse diagram of length $n$, with $2^n$ vertices and $n2^{n-1}$ edges, always boolean?

If it is not true, it would be useful (to me) to know up to which rank $n$ it is true.

$\endgroup$
4
$\begingroup$

Define a ground set $X$ of size $2^{n-1}$. Now choose $2^{n-1}-(n-1)$ subsets of $X$, each of size at least 2, such that the sum of their sizes is $(n-2)2^{n-1}+2$ (so the average size is slightly more than $n-2$), and such that no two sets overlap in more than one element.

Now take the poset consisting of the empty set, the singletons, the chosen subsets, and the full set $X$, ordered by inclusion, and then a chain upwards from $X$ so that the overall poset has height $n$. Because no two sets overlap in more than one element, the join of any two singletons in well-defined, and it follows immediately that the join is always well-defined. Since the poset is also bounded, it is a lattice. By construction, it has $2^n$ elements and $n2^{n-1}$ edges.

We now go back and check for what $n$ it will be possible to choose a set system such as we have described. This isn't hard. For odd $n$, we can consider our ground set to be points in the plane $\mathbb F^2_{2^{(n-1)/2}}$. There are more than $2^{n-1}$ affine lines in this plane, no two intersect in more than one point, and each contains at least $2^{(n-1)/2}$ points of our ground set. (This produces sets much bigger than we need, but if the sum of the sizes of our sets is too big, we can throw away elements from the sets until they are small enough. The intersection property will obviously be preserved.) Since $2^{(n-1)/2}$ is larger than $n-1$ if $n$ is at least 7, we are certainly done for all odd $n$ at least 7. A one-off construction for $n=5$ seems easy enough. Even $n$ should also be straightforward. I don't know whether or not my construction works for $n=4$, but it should have no trouble starting at $n=6$.

Edited to add: In rank 0, there is one vertex (the empty set). In rank 1, there are $2^{n-1}$. In rank 2, $2^{n-1}-(n-1)$. In ranks 3 to $n$, there is one each. The total number of vertices is therefore $2^n$.

$\endgroup$
  • $\begingroup$ Is your construction of length $n$ and non-equivalent to a boolean lattice? $\endgroup$ – Sebastien Palcoux Aug 30 '16 at 4:34
  • $\begingroup$ It is now of length $n$. (I forgot that condition to begin with.) It's clearly not equivalent to a Boolean lattice provided $n>3$. $\endgroup$ – Hugh Thomas Aug 30 '16 at 4:36
  • 1
    $\begingroup$ To show that $B_4$ is not uniquely characterized as in the question, you can take $X$ consisting of 7 elements, and a collection of 6 of the seven triples from the Fano arrangement as the collection of subsets. The rank numbers are 1, 7, 6, 1, 1; there are 16 vertices and 32 edges. $\endgroup$ – Hugh Thomas Aug 30 '16 at 5:51
  • 1
    $\begingroup$ After your modification, your construction admits now $2^n - n + 3 $ vertices. If you can't fix that then your last comment should be your answer (if you can draw it then this would be nice, otherwise I will draw it myself). $\endgroup$ – Sebastien Palcoux Aug 30 '16 at 11:46
  • 2
    $\begingroup$ Alternatively, your fake $B_4$ can be viewed as the (upside down) partition lattice of a 4-element set, with an extra bottom added (or you could also add an extra top instead; this is still another (non-isomorphic) example). (For a picture, see here) $\endgroup$ – მამუკა ჯიბლაძე Aug 30 '16 at 13:58

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.