Ask Your Question
0

Subposets of the Boolean lattice via Sage

asked 2021-10-08 14:19:08 +0100

klaaa gravatar image

updated 2021-10-08 14:21:12 +0100

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 flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
1

answered 2021-10-10 21:52:12 +0100

Max Alekseyev gravatar image

updated 2021-10-11 01:27:38 +0100

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}]
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2021-10-08 14:19:08 +0100

Seen: 61 times

Last updated: Oct 11 '21