Ask Your Question
1

Obtaining quotient posets of the Boolean lattice via Sage

asked 2020-08-20 08:34:56 -0500

klaaa gravatar image

updated 2020-08-23 11:10:28 -0500

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

Comments

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 07:34:28 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
2

answered 2020-08-23 14:57:21 -0500

jipilab gravatar image

updated 2020-08-23 15:03:45 -0500

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))
sage: QuotientPoset.show()

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

Comments

Thank you very much!

klaaa gravatar imageklaaa ( 2020-08-23 16:25:37 -0500 )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

Stats

Asked: 2020-08-20 08:34:56 -0500

Seen: 50 times

Last updated: Aug 23