5
$\begingroup$

The semigroup algebra of the Catalan monoid is isomorphic to the incidence algebra of $P_n$, where $P_n$ is 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$. This is for example proved in https://arxiv.org/pdf/1806.06531.pdf. Recall that the width of a poset is the maximum size of an antichain.

I noted that the width of the poset $P_n$ starts with 2, 3, 4, 6, 8, 13, 20, 32, 52, 90, 152 for $n=1,...,11$ and this leads to the sequence https://oeis.org/A084239 of the rank of K-groups of the Furstenberg transformation group of the $n$-torus. See table 1 in https://arxiv.org/pdf/1109.4473.pdf .

Question 1: Is this true for all $n$? Is there a deeper explanation? Does the width have a homoogical interpretation for the Catalan monoid?

The poset $P_n$ has $n+1$ connected components, for each of the $k$-subsets and one can restrict to find antichains in those subsets and put them together. But I am more curious whether there is a deeper connection to the $K$-group sequence or is this just random? One might also ask about other nice properties of $P_n$. I noted that appending a minimum and maximum to $P_n$, one obtains a lattice.

The width of $P_n$ is equal to the maximal number of covers an element can have in the distributive lattice of order ideals $L(P_n)$ of $P_n$.

Question 2: Does the incidence algebra of $L(P_n)$ have an algebraic meaning in relation to the Catalan monoid?

Question 3: Is the Coxeter matrix of $L(P_n)$ periodic?

Question 3 has a positive answer for $n=1,2,3,4$ and the periods are given by 6,12,30,42 in that case.

(Small values suggest that also the Coxeter matrix of $P_n$ might be periodic, but that might be not so good evidence since the connected compoenent have not many points for small $n$.)

$\endgroup$
8
  • 1
    $\begingroup$ You might look at the answer to this question mathoverflow.net/questions/193913/… which gives another interpretation of this poset in terms of well known geometry. $\endgroup$ – Benjamin Steinberg Sep 1 '20 at 17:38
  • 1
    $\begingroup$ Again, if we break your $P_{n}$ into the $P_{n,k}$, then the widths are given by oeis.org/A067059 by Stanley's Spernicity result. oeis.org/A084239 is the sum of the diagonals of oeis.org/A067059 $\endgroup$ – Sam Hopkins Sep 1 '20 at 18:11
  • 1
    $\begingroup$ You can translate it in a way that doesn't mention $K_0$ or $K_1$. Suppose that $A$ is the $n\times n$ matrix with $a_{i,j}=1$ if $i=j$ or $j=i+1$. Then the claim is that the largest antichain in $P_{n,r}$ is the same as the dimension of the kernel of $\bigwedge^r A-I$. $\endgroup$ – Gjergji Zaimi Sep 1 '20 at 18:11
  • 1
    $\begingroup$ @SamHopkins Thanks, that seems to be the explanation to answer question 1. If you want you can turn it into an answer. $\endgroup$ – Mare Sep 1 '20 at 18:15
  • 1
    $\begingroup$ The proof of proposition 6.30 in the Reihani-Milnes paper, is essentially very close to Stanley's proof of Spernicity for $P_{n,r}$. In particular the observation that A084239 is the sum of the diagonals of A067059 seems to be just as hard as the computation of the latter. I wonder if there is a more direct route. $\endgroup$ – Gjergji Zaimi Sep 1 '20 at 18:34
4
$\begingroup$

The distributive lattice $L(k,n-k) := [\varnothing,(n-k)^k]$, the interval between the empty partition and the rectangular shape $(n-k)^k$ in Young's lattice, is the same as the poset of subsets of $[n]:=\{1,2,\ldots,n\}$ of size $k$ ordered by $\{x_1<\cdots<x_k\}\leq \{y_1<\cdots<y_k\}$ iff $x_i \leq y_i$ for all $i=1,\ldots,k$. We also have $L(k,n-k)=J([k]\times[n-k])$, the distributive lattice of order ideals of the product $[k]\times[n-k]$ of two chains. Finally, and perhaps most importantly, $L(k,n-k)$ is the Bruhat order on the cells of the Grasmannian $\mathrm{Gr}(k,n)$.

Your $P_n$ is a disjoint union of these $L(k,n-k)$.

In "Weyl groups, the Hard Lefschetz Theorem, and the Sperner property", Stanley proved that $L(k,n-k)$ is Sperner, i.e., the maximum size of an antichain of this poset is the maximum size of one of its rank. (He proves more, namely, the strong Sperner property, and in a more general context of parabolic quotients of Weyl groups, using some basic geometry of generalized flag manifolds.)

The maximum size of a rank of $L(k,n-k)$ is easily seen to be given by the OEIS sequence https://oeis.org/A084239. Since https://oeis.org/A084239 is a sum of diagonals of https://oeis.org/A084239, this explains your observations about $P_n$.

A lot is known about $L(k,n-k)$, because of its connection to representation theory/geometry. For instance, $[k]\times[n-k]$ is a so-called "minuscule poset," which implies a lot of nice properties for $J([k]\times[n-k])$: see this paper of Proctor.

Similarly, your observation about the Coxeter transform being periodic seems to be proved by Yildirim in this paper in the more general context of minuscule posets.

EDIT: Ah, sorry, the paper of Yildirim addresses the periodicity of the Coxeter transform for $L(k,n-k)=J([k]\times[n-k])$. For $J(P_n)$, I bet what you observed only happens for small values of $n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.