Ask Your Question

Obtaining the poset of the Catalan monoid

asked 2020-08-30 15:36:26 +0200

klaaa gravatar image

updated 2020-08-30 15:37:17 +0200

The poset $P_n$ is defined as the poset consisting of subsets of { 1,...,n } where for two subsets $X \leq Y$ if and only if $X$ and $Y$ have the same cardinality and if X= {x_1 < ... < x_k } and Y= {y_1 < ... < y_k } we have $x_i \leq y_i$ for $i=1,...,k$. See for example .

My question is whether the is an easy way to obtain this poset for a given $n$ with Sage?

edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted

answered 2020-08-30 19:24:17 +0200

FrédéricC gravatar image

Like this maybe (not checked)

sage: def cata(n): 
....:     S = Subsets(list(range(n))) 
....:     def rel(x, y):
....:        return len(x)==len(y) and all(u<=v for u, v in zip(sorted(x),sorted(y))) 
....:     return Poset((S, rel))                              
sage: cata(4)                                                                   
Finite poset containing 16 elements
edit flag offensive delete link more


Thank you very much. Here is an interesting observations: Appending a unique minimum and maximum to this poset gives a lattice. The width of this lattice starts with 2, 3, 4, 6, 8, 13, 20, 32, 52, 90, 152 for $n=1,...,11$ and it seems likely that it is given by . Is there any direct connection to this sequence?

klaaa gravatar imageklaaa ( 2020-08-30 21:39:26 +0200 )edit

Another observation: For $n=1,2,3,4$ the Coxeter transformation of the distributive lattice of order ideals of this poset was periodic with periods 6,12,30,42.

klaaa gravatar imageklaaa ( 2020-08-30 22:21:09 +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-30 15:36:26 +0200

Seen: 144 times

Last updated: Aug 30 '20