# Subposets of the Boolean lattice via Sage

Let $B_n$ be the Boolean lattice of a set with $n$ elements. Is there a quick method via Sage to obtain all subposets $P$ of $B_n$ containing the empty set and having the property that with x in $P$ also the complement of the set x is in P and such that with x and y in P also the union of x and y is in P if x and y are disjoint? (probably this works only for small $n$ but $n \leq 6$ would already be interesting) Thanks for any help

edit retag close merge delete

Sort by ยป oldest newest most voted

First notice that for $x,y\in P$, if $x\subseteq y$ then $x\cap \overline{y}=\emptyset$ and thus $y\setminus x = \overline{x\cup\overline{y}}\in P$. It follows that each set in $P$ is formed by the disjoint union of some minimal elements of $P$, and furthermore $P$ is completely defined by the set of its minimal elements.

We can search for the set of minimal elements of $P$ among the antichains of $B_n$. A candidate antichain $a$ must satisfy the property that the complement of each element of $a$ is the disjoint union of elements of $a$. Here is a sample code that lists such antichains.

def test(n,a):
u = Set(1..n)
for s in a:
c = u.difference(s)
for t in a:
if t.issubset(c):
c = c.difference(t)
if c.is_empty():
break
if not c.is_empty():
return False
return True

def minels(n):
for a in posets.BooleanLattice(n, use_subsets=True).antichains():
if test(n,a):
print(a)


For example, minels(4) lists the following candidate sets of minimal elements of $P\subseteq B_4$:

[]
[{2}, {1}, {3}, {4}]
[{2}, {1}, {3, 4}]
[{2}, {3}, {1, 4}]
[{2}, {1, 3}, {4}]
[{2}, {1, 3, 4}]
[{1}, {3}, {2, 4}]
[{1}, {2, 3}, {4}]
[{1}, {2, 3, 4}]
[{1, 2}, {3}, {4}]
[{1, 2}, {1, 3}, {2, 3}, {1, 4}, {2, 4}, {3, 4}]
[{1, 2}, {1, 3}, {2, 4}, {3, 4}]
[{1, 2}, {2, 3}, {1, 4}, {3, 4}]
[{1, 2}, {3, 4}]
[{3}, {1, 2, 4}]
[{1, 3}, {2, 3}, {1, 4}, {2, 4}]
[{1, 3}, {2, 4}]
[{2, 3}, {1, 4}]
[{1, 2, 3}, {4}]
[{1, 2, 3, 4}]

more