Can you provide a symmetric presentation of this partition lattice?

Question

I have a question about the partition lattice on a set with four elements, shown here:

Equivalently, this is the lattice of equivalence relations on that set.

An observant person will notice that the lattice is nearly symmetric from left-to-right, but not quite. For example, the partition at lower left connects to the next level in a slightly different manner than the partition at lower right.

Question. Is there a left-to-right symmetric presentation of this lattice? If not, how do we see this?

Of course, in an abstract sense, there are many symmetries of this lattice, since any permutation of the points in the set acts on the partitions. What I want to know is whether I can present the Hasse diagram of this lattice in the plane in a way that has a vertical line symmetry.

I am confused about how to think about this. I would have similar questions for larger partition lattices. The lattice of partitions on a three-element set does have a symmetric presentation.

Answer 1

To answer this question, there is not a symmetric left to right presentation of the Directed acyclic graph (which also induces a lattice structure on the vertices). To see this, I am going to concentrate on a subgraph. That subgraph consists of those vertices corresponding to 3+1 , and the 2+1+1 partitions, pictured below. Restricted Graph

This One may easily see that this directed graph has automorphism group isomorphic to the symmetric group on four letters, and that the automorphisms of the top four vertices determine the automorphisms of the entire subgraph (and the entire lattice I believe, But I do not need to reach that issue here!). Therefore the desired layouts (suitably define), are determined by the ordering of the six vertices in the lower level. However, when we look at which of the six vertices corresponds to the {2,3} subset, it either has to be the first three, or the last three, which makes the desired left to right symmetry impossible.

Unfinished Buisness

1. Ascertain whether or not the automorphism group of the entire DAG (and therefore lattice) is in fact the syymetric group on four letters.

2. Do the same for the lattice and poset for N= 5 , and then for all N.

3. Write a careful definition of a layout.

Answer 2

Update: We have a general answer for $n \ge 4$. But I'm keeping the $P_5$ and $P_7$ special cases at the bottom of the answer as a prehistory.

General case: $n \ge 4$ elements

Claim: $P_n$ has no symmetric drawing if $n \ge 4$.

Proof: The coatoms are the 2-piece-partitions of the base set. For $k=1,\ldots,\lfloor n/2 \rfloor$, let $C_k$ be the set of coatoms whose piece sizes are $k$ and $n-k$.

In $C_1$ we have $n$ coatoms (any one element separated from the rest), and each has downdegree $D_1=2^{n-2}-1$, because the $n-1$ elements can be split into two parts in that many ways.

In $C_k$ ($k>1$) each coatom has downdegree $D_k=(2^{k-1}-1) + (2^{n-k-1}-1)$, by splitting either the $k$ elements or the $n-k$ elements.

So the $C_1$ coatoms are distinguished from all other coatoms by downdegree, because $D_k < D_1$ for $k>1$. Thus the drawing of $C_1$ has to be symmetric in itself. Now $C_1$ contains at least four coatoms; at least two on the left, and at least two on the right. (If $|C_1|$ is odd, one is on the midline, and the rest are not; if even, none of them are on the midline.)

Assume without loss of generality that

• $(1|-)$ is on the left, and $(4|-)$ is its mirror image on the right,
• $(2|-)$ is on the left, and $(3|-)$ is its mirror image on the right.

Partitions are here written in shorthand notation, with parts separated by $|$, and the last part ("all other elements") written as $-$.

Let $a = (1|-) \wedge (4|-) = (1|4|-)$. Now $a$ has two upper covers symmetric about the midline, so $a$ must itself be on the midline. Its updegree is three, and the third upper cover $c=(14|-)$ must likewise be on the midline. Note that $c$ is a coatom (of type $C_2$).

Similarly let $b = (2|-) \wedge (3|-) = (2|3|-)$. It must similarly be on the midline.

Suppose (without loss of generality) that $a$ is drawn below $b$. Then we have two choices:

1. If $c$ is below $b$, then the edge from $c$ to top goes through $b$ (red edge in picture below, left).
2. If $c$ is above $b$, then the edge from $a$ to $b$ goes through $c$ (red edge in picture below, right).

Both placements are invalid, so $P_n$ has no symmetric drawing.

7 elements

$P_7$, the partition lattice of 7 elements, does not have a symmetric drawing.

Proof: There are 3 kinds of coatoms (2-part partitions):

• type A, partitions to 1+6 elements: 7 of them
• type B, partitions to 2+5 elements: 21 of them
• type C: partitions to 3+4 elements: 35 of them

The three types are distinguished by their down-degrees (number of lower covers). To wit:

• type A vertices have down-degree 31 (you can split to 1+1+5 elements in 6 ways; to 1+2+4 elements in 15 ways; and to 1+3+3 elements in 10 ways)
• type B vertices have down-degree 16 (you can split to 1+1+5 elements in 1 way; 2+1+4 elements in 5 ways; and to 2+2+3 elements in 10 ways)
• type C vertices have down-degree 10 (you can split to 1+2+4 elements in 3 ways; 3+1+3 elements in 4 ways; and to 3+2+3 elements in 3 ways)

Because the types are distinguished, coatoms of different types cannot be mirror images. So the drawing of type-A vertices must be symmetric in itself, and because it has an odd number of vertices, at least one must be on the midline; call it $a$. Similarly, the drawing of type-B vertices must be symmetric, at least one of them must be on the midline, call it $b$.

Now $a$ and $b$ are both coatoms on the midline. Whichever is drawn lower, it has a vertical upward edge to the top, going falsely through the upper-drawn vertex, which is not allowed. (Even if you allow curved edges, as in the picture in the question, this is an edge between two midline vertices, so for symmetry it must be drawn vertical.)

The same kind of reasoning might give an easy proof for some other $P_n$ too, if the types of coatoms are distinguished (e.g. by downdegree, or by some finer structure of their neighborhoods) and there are at least two types that have odd counts.

5 elements

The A-vertices and B-vertices are distinguished by their downdegrees (A have 7 and B have 4). So in particular, A-vertices must have a symmetric drawing, with one on the midline, two on left, and two on right. They cannot have more than one on the midline as they are all coatoms.

Without loss of generality (by naming the elements suitably), let's say

• $c_3=(3,1245)$ is on the midline,
• $c_1=(1,2345)$ is on the left,
• $c_5=(5,1234)$ is on the right symmetric with $c_1$.

Now consider the vertex $u=c_1 \wedge c_5 = (1,5,234)$. Because it has two upper covers symmetric about the midline, it must itself be on the midline. But the updegree of $u$ is three; the third upper cover is $v=(15,234)$, which must now also be on the midline for symmetry. Now $v$ is a coatom on the midline, which conflicts with $c_3$.

So $P_5$ does not have a symmetric drawing.