Ask Your Question

Obtaining quotient posets of the Boolean lattice via Sage

asked 2020-08-20 15:34:56 +0200

klaaa gravatar image

updated 2020-08-23 18:10:28 +0200

Let $G$ be a subgroup of the symmetric group $S_n$ that acts in a natural way on the Boolean lattice $B_n$, see for example chapter 5 of the book on algebraic combinatorics by Stanley.

$B_n/G$ for a subgroup $G$ of the symmetric group $S_n$ (that acts naturally on $B_n$) is defined as the poset of orbits under the natural order (that is one orbit $a$ is $\geq$ another orbit $b$ if and only if there exists elements $a' \in a$ and $b' \in b$ such that $a' \geq b'$).

The posets $B_n /G$ are graded of rank $n$, rank-symmetric, rank-unimodal, and Sperner. See theorem 5.8. in the book of Stanley. In this book one can also find open problems about such posets and thus it might be a good class to study in Sage.

For example when $n=3$ and $G$ is generated by the permutation (1,2) then the resulting poset is isomorphic to the product of the chain with 2 elements and the chain with 3 elements.

My question is how one can obtain the quotient poset $B_n /G$ in Sage when one inputs the group G generated by cycles?

The Boolean lattice on n points can be obtained in Sage via B4=posets.BooleanLattice(4) . Im not sure how to obtain a subgroup of the symmetric group acting on $B_n$ in SAGE and the resulting quotient poset.

Also is it possible to obtain the list of all connected posets obtained in this way for a given $n$? (meaning all connected posets of the form $B_n /G$ where $G$ is a subgroup of $S_n$). This will be a huge list but maybe for n<=5 it is possible to obtain it via sage.

edit retag flag offensive close merge delete


If you already have code to define $B_n$ and $G$, please provide it.

Use the simplest example to illustrate the question: lowest $n$ and simplest $G$.

slelievre gravatar imageslelievre ( 2020-08-23 14:34:28 +0200 )edit

1 Answer

Sort by ยป oldest newest most voted

answered 2020-08-23 21:57:21 +0200

jipilab gravatar image

updated 2020-08-23 22:03:45 +0200

Here is a snippet of code that can be used to produce the desired quotient poset. It is not meant to be the most optimal way, but it does return the desired object.

sage: G = PermutationGroup([[(1,2)],[(3,4)]])
sage: S = Set([1,2,3,4])
sage: GroundSet = S.subsets()
sage: Orbits = Set([Set(G.orbit(s, action = "OnSets")) for s in GroundSet])
sage: def quotient_order(a,b):
....:     for s1 in a:
....:         ss1 = set(s1)
....:         for s2 in b:
....:             ss2 = set(s2)
....:             if ss1.issubset(ss2):
....:                 return True
....:     return False
sage: QuotientPoset = Poset((Orbits,quotient_order))

To obtain all of the quotient posets, one should then loop over all permutation subgroups of $S_n$. These subgroups can be obtained this way:

sage: SG = SymmetricGroup(4)
sage: SG.subgroups()
edit flag offensive delete link more


Thank you very much!

klaaa gravatar imageklaaa ( 2020-08-23 23:25:37 +0200 )edit

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


Asked: 2020-08-20 15:34:56 +0200

Seen: 174 times

Last updated: Aug 23 '20