ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 10 Oct 2021 21:52:12 +0200Subposets of the Boolean lattice via Sagehttps://ask.sagemath.org/question/59291/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 helpFri, 08 Oct 2021 14:19:08 +0200https://ask.sagemath.org/question/59291/subposets-of-the-boolean-lattice-via-sage/Answer by Max Alekseyev for <p>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</p>
https://ask.sagemath.org/question/59291/subposets-of-the-boolean-lattice-via-sage/?answer=59319#post-id-59319First 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}]Sun, 10 Oct 2021 21:52:12 +0200https://ask.sagemath.org/question/59291/subposets-of-the-boolean-lattice-via-sage/?answer=59319#post-id-59319