Algebra and Coalgebra on Posets

Rongrong Yuan, Huilan Li

School of Mathematics and Statistics, Shandong Normal University, Jinan, China.

DOI: 10.4236/ojapps.2022.127083                

Abstract

A lot of combinatorial objects have algebra and coalgebra structures and posets are important combinatorial objects. In this paper, we construct algebra and coalgebra structures on the vector space spanned by posets. Firstly, by associativity and the unitary property, we prove that the vector space with the conjunction product is a graded algebra. Then by the definition of free algebra, we prove that the algebra is free. Finally, by the coassociativity and the counitary property, we prove that the vector space with the unshuffle coproduct is a graded coalgebra.

Keywords

Conjunction Product, Unshuffle Coproduct, Poset, Graded, Free

1. Introduction

A poset is a set with a binary relation satisfying reflexivity, antisymmetry and transitivity. Researches and generalizations on posets are very rich. The most famous result on posets is the decomposition theorem [1] proposed by Dilworth in 1950, also well-known as Dilworth’s Theorem, which has great combinatorial and order theoretical value. To learn more about Dilworth’s Theorem, please refer to Fulkerson [2], Tverberg [3], Pretzel [4] and Galvin [5].

In 1964, Rota [6] made the Möbius function emerge in clear view as a fundamental invariant, which unifies both enumerative and structural aspects of the theory of partially ordered sets. In 1972, Stanley [7] studied ordered structures and partitions. Later, he proved several identities associated with the binomial posets [8]. In 1977, Trotter and Moore [9] studied the dimension of planar posets and the dimension of trees. In 1988, Stanley [10] first introduced the differential poset with combinatorial and algebraic properties. For more works on differential posets, see [11] [12] [13] [14] [15].

In 2005, Aguiar and Sottile [16] introduced the global descents of permutations in the symmetric group $S_n$. In 2020, based on the global descents, Zhao and Li [17] studied a new shuffle product ${\text{ш}}_G$ on permutations. Later, they [18] defined a new product $\diamond$ and a new coproduct ${\Delta }^{\mathrm{<mo>\; *\; </mo>}}$ on permutations, proved that $\left(\mathbb{K}S,\diamond ,\mu \right)$ is a graded $\mathbb{K}$ -algebra and $\left(\mathbb{K}S\mathrm{,}{\Delta }^{\mathrm{<mo>\; *\; </mo>}}\mathrm{,}\nu \right)$ is a graded $\mathbb{K}$ -coalgebra, where $\mathbb{K}$ is a field, and studied some properties of the structures. In 2021, Liu and Li [19] introduced the super-shuffle product and the cut-box coproduct on permutations and proved that $\left(\mathbb{K}S\mathrm{,}\text{<munder accentunder="true"> <mi> ш </mi> <mo> \_ </mo> </munder>}\mathrm{,}\mu \right)$ is a graded algebra and $\left(\mathbb{K}S\mathrm{,}{\Delta }_{\diamond }\mathrm{,}\nu \right)$ is a graded coalgebra. These papers are helpful for us to study algebra and coalgebra on posets.

In 2020, Aval, Bergeron and Machacek [20] defined a product and a coproduct on posets without proofs. In this paper, we prove that the vector space spanned by posets with these operations is an algebra and a coalgebra, respectively.

We start by recalling some basic definitions of algebra and coalgebra and some notations on posets in Section 2. In Section 3, we introduce the definitions of the conjunction product and the unshuffle coproduct on the vector space spanned by posets. Then we prove the vector space with the conjunction product is a free graded algebra. And the vector space with the unshuffle coproduct is a graded coalgebra. Thus, we construct algebra and coalgebra structures on posets. Finally, we make a summary of this paper in Section 4.

2. Preliminaries

2.1. Basic Definitions

We recall some basic definitions of algebra and coalgebra; see [21] [22] for more details. Let $R$ be an associative commutative ring with identity.

For an $R$ -module $A$, we call $\left(A\mathrm{,}m\mathrm{,}\mu \right)$ an $R$ -algebra if there exist two maps $m\mathrm{<mo>\; :\; </mo>}A\otimes A\to A$ and $\mu \mathrm{<mo>\; :\; </mo>}R\to A$ such that the diagrams in Figure 1 are commutative. Here $m$ is called a product and $\mu$ a unit.

The R-algebra $\left(A\mathrm{,}m\mathrm{,}\mu \right)$ is graded if $A={{\displaystyle \oplus }}_{i\ge 0}{A}_i$ and $m\left(A_s\otimes A_t\right)\subseteq A_{s+t}$, for all $s,t$.

We reverse all the arrows in Figure 1 to get the definition of coalgebra since algebra and coalgebra are dual concepts.

For an $R$ -module $A$, we call $\left(A\mathrm{,}\Delta \mathrm{,}\nu \right)$ an $R$ -coalgebra if there exist two maps $\Delta \mathrm{<mo>\; :\; </mo>}A\to A\otimes A$ and $\nu \mathrm{<mo>\; :\; </mo>}A\to R$ such that the diagrams in Figure 2 are commutative. Here $\Delta$ is called a coproduct and $\nu$ a counit.

The $R$ -coalgebra $\left(A\mathrm{,}\Delta \mathrm{,}\nu \right)$ is graded if $A={{\displaystyle \oplus }}_{i\ge 0}{A}_i$ and $\Delta \left(A_n\right)\subseteq {{\displaystyle \oplus }}_i\left(A_i\otimes A_{n-i}\right)$, for all $n$.

A coalgebra $A$ is cocommutative if the diagram in Figure 3 commutes, where $\tau \left(a\otimes b\right)=b\otimes a$, for all $a,b$ in $A$.

Let $V$ be a vector space over field $\mathbb{K}$. Denote the tensor algebra on $V$ by $T\left(V\right)={{\displaystyle \oplus }}_{n\ge 0}{V}^{\otimes n}$, where $V^{\otimes 0}=\mathbb{K}$ and $V^{\otimes n}=\underset{n\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>}\text{times}}{\underset{︸}{V\otimes \cdots \otimes V}}\mathrm{.}$

Define the multiplication on $T\left(V\right)$ by the concatenation product and unit

(a) (b)

Figure 1. Associative law and unitary property. (a) Associative law; (b) Unitary property.

(a) (b)

Figure 2. Coassociative law and counitary property. (a) Coassociative law; (b) Counitary property.

Figure 3. Commutativity.

$\mu \mathrm{<mo>\; :\; </mo>}\mathbb{K}\to T\left(V\right)$ on $T\left(V\right)$ by $\mu \left(a\right)=a$, for $a\in \mathbb{K}$. Then the algebra $T\left(V\right)={{\displaystyle \oplus }}_{n\ge 0}{V}^{\otimes n}$ is free on $V$ since it satisfies the following universal property: for each $\mathbb{K}$ -algebra $A$ and each linear map $f\mathrm{<mo>\; :\; </mo>}V\to A$, there exists a unique algebra homomorphism $g\mathrm{<mo>\; :\; </mo>}T\left(V\right)\to A$ such that $g\iota =f$ where $\iota \mathrm{<mo>\; :\; </mo>}V\to T\left(V\right)$ is the inclusion map.

2.2. Basic Notations

Now let’s recall some notations on posets; see [23] [24] for more details.

A partial order relation is a binary relation satisfying reflexivity, antisymmetry and transitivity. A set $P$ together with a partial order relation ${\le }_P$ is called a poset, denoted by $\left(P\mathrm{,}{\le }_P\right)$. The set $P$ is called the ground set of poset $\left(P\mathrm{,}{\le }_P\right)$. We denote the number of elements of $P$ by $\left|P\right|$. When the ground set is empty, we have an empty poset, denoted by $ϵ$. When the partial order relation is obvious, $P$ can represent both the ground set and the poset.

For distinct elements $x\mathrm{,}y$ in poset $P$, if $x{\le }_{P}y$ and there is no element $z$ that differs from $x\mathrm{,}y$ and satisfies $x{\le }_{P}z{\le }_{P}y$, then we say that $y$ covers $x$ , denoted by $x{⋖}_{P}y$, and we also call $\left(x\mathrm{,}y\right)$ a cover relation in $P$. Define $\mathcal{A}\left(P\right)$ to be the set of all cover relations in $P$ by

$\mathcal{A}\left(P\right)=\left\{\left(x\mathrm{,}y\right)\mathrm{<mo>\; |\; </mo>}x⋖y\mathrm{,}x\mathrm{,}y\in P\right\}\mathrm{.}$

If $\mathcal{A}\left(P\right)$ is given in poset $P$, then we can get the partial order relation ${\le }_P$ corresponding to the cover relations through reflexivity, antisymmetry and transitivity. Obviously, $\mathcal{A}\left(P\right)$ and ${\le }_P$ are uniquely determined by each other.

The two elements $x$ and $y$ in poset $P$ are called comparable, if either $x{\le }_{P}y$ or $y{\le }_{P}x$. In a poset, it is not necessary that any two elements are comparable. When $x$ and $y$ are two elements of $P$ such that neither $x{\le }_{P}y$ nor $y{\le }_{P}x$, they are called incomparable.

To study posets more intuitively, we can represent posets by Hasse diagrams. A Hasse diagram is a graphical rendering of a poset displayed by the cover relations of the poset with an implied upward orientation. Drawing line segments between these elements of a poset follows these two rules:

1) If $x{\le }_{P}y$ in the poset, then the point representing $x$ is lower in the drawing than the point representing $y$.

2) Drawing line segment between the points representing elements $x$ and $y$ of the poset if $y$ covers $x$.

In addition, incomparable elements can be drawn on the same layer.

For example, for set $P=\left\{\mathrm{2,3,4}\right\}$ with $\mathcal{A}\left(P\right)=\left\{\left(\mathrm{2,3}\right)\mathrm{,}\left(\mathrm{3,4}\right)\right\}$, i.e., 3 covers 2 and 4 covers 3, according to transitivity, we have $2{\le }_{P}4$. Further, we get poset . Similarly, if $Q=\left\{\mathrm{1,2,3}\right\}$ with $\mathcal{A}\left(Q\right)=\left\{\left(\mathrm{1,3}\right)\mathrm{,}\left(\mathrm{2,3}\right)\right\}$, then poset .

In poset $P$, an element $x$ is called maximal in $P$, if there is no other element $y$ in $P$ satisfying $x{\le }_{P}y$. Similarly, $x$ is minimal if no other element $y$ in $P$ satisfing $y{\le }_{P}x$. A partially ordered set may have more than one maximal or minimal elements. Hence, we denote $\text{max}\left(P\right)$ as the set containing all maximal elements in $P$ and $\text{min}\left(P\right)$ containing all minimal elements in $P$. From the above example, we have $\text{max}\left(P\right)=\left\{4\right\}$, $\text{min}\left(P\right)=\left\{2\right\}$, $\text{max}\left(Q\right)=\left\{3\right\}$ and $\text{min}\left(Q\right)=\left\{\mathrm{1,2}\right\}$.

Let $P$ and $Q$ be disjoint sets with partial orders ${\le }_P$ and ${\le }_Q$, respectively. Define $T$ to be the union of $P$ and $Q$ with partial order ${\le }_T$ given by the cover relations

$\mathcal{A}\left(T\right)=\mathcal{A}\left(P\right)\cup \mathcal{A}\left(Q\right)\cup \left\{\left(x\mathrm{,}y\right)\mathrm{<mo>\; |\; </mo>}x\in \text{max}\left(P\right)\mathrm{,}y\in \text{min}\left(Q\right)\right\}\mathrm{.}$

We denote the poset $T$ as $P<Q$, which means $<$ is an operation for posets. Obviously, $<$ satisfies the associative law. For example, Let and , then $\mathcal{A}\left(P\right)=\left\{\left(\mathrm{4,2}\right)\mathrm{,}\left(\mathrm{5,2}\right)\right\}$, $\mathcal{A}\left(Q\right)=\{\varnothing \}$, $\text{max}\left(P\right)=\left\{2\right\}$ and $\text{min}\left(Q\right)=\left\{\mathrm{1,3}\right\}$. Hence we have $\mathcal{A}\left(T\right)=\left\{\left(\mathrm{4,2}\right)\mathrm{,}\left(\mathrm{5,2}\right)\mathrm{,}\left(\mathrm{2,1}\right)\mathrm{,}\left(\mathrm{2,3}\right)\right\}$, i.e., .

Denote ${\mathcal{P}}_n$ to be the set of all posets on $\left[n\right]=\left\{1,2,\cdots ,n\right\}$, where ${\mathcal{P}}_0=\left\{\epsilon \right\}$. For example, when $n=3$,

Let $\mathcal{P}={\displaystyle {\cup }_{n\ge 0}}{\mathcal{P}}_n+$ be the disjoint union of ${\mathcal{P}}_n$, and $\mathbb{K}\mathcal{P}={{\displaystyle \oplus }}_{n\ge 0}\mathbb{K}{\mathcal{P}}_n$, where $\mathbb{K}{\mathcal{P}}_n$ is the linear space spanned by ${\mathcal{P}}_n$ over field $\mathbb{K}$.

For a positive integer $n$, define $\left(P^{\uparrow n}\mathrm{,}{\le }_{P^{\uparrow n}}\right)$ as a poset by increasing each element in $P$ by $n$ satisfying

$\left(x+n\right){\le }_{P^{\uparrow n}}\left(y+n\right)\iff x{\le }_{P}y\mathrm{,}$

for $x\mathrm{,}y$ in $P$. Similarly, define $\left(P^{\downarrow n}\mathrm{,}{\le }_{P^{\downarrow n}}\right)$ as a poset by reducing each element in $P$ by $n$ satisfying

$\left(x-n\right){\le }_{P^{\downarrow n}}\left(y-n\right)\iff x{\le }_{P}y\mathrm{,}$

for $x\mathrm{,}y$ in $P$. For example, let , then and .

For a poset $P$ in ${\mathcal{P}}_n$, we call $n$ a global split of $P$ if

$P=P_{\left[i\right]}<P_{\left[n\right]\backslash \left[i\right]},$

where $0\le i\le n$. If a nonempty poset has no global splits except 0 and $n$, we call it an indecomposable poset. We denote ${\bar{\mathcal{P}}}_n$ as the subset of ${\mathcal{P}}_n$ containing all indecomposable posets in ${\mathcal{P}}_n$, and $\bar{\mathcal{P}}={\displaystyle {\cup }_{n\ge 1}}{\bar{\mathcal{P}}}_n+$.

For a nonempty set of intergers $S=\left\{s_1\mathrm{,}{s}_2\mathrm{,}\cdots \mathrm{,}{s}_n\right\}$ with $s_1<s_2<\cdots <s_n$, denote ${\text{st}}_S$ as a mapping from $S$ to $\left[n\right]$ by ${\text{st}}_S\left(s_i\right)=i$ for each $1\le i\le n$.

Let $\left(P\mathrm{,}{\le }_P\right)$ be a poset, where $P$ is an interger set. We define $\text{st}\left(P\mathrm{,}{\le }_P\right)=\left(\text{st}\left(P\right)\mathrm{,}{\le }_{\text{st}\left(P\right)}\right)$, where $\text{st}\left(P\right)=\left[\left|P\right|\right]$ and ${\le }_{\text{st}\left(P\right)}$ is the partial order on $\left[\left|P\right|\right]$ satisfying

${\text{st}}_P\left(i\right){\le }_{\text{st}\left(P\right)}{\text{st}}_P\left(j\right)\iff i{\le }_{P}j\mathrm{,}$

for any $i\mathrm{,}j$ in $P$. For convenience, we denote the $\text{st}\left(P\mathrm{,}{\le }_P\right)$ as $\text{st}\left(P\right)$ when the partial order ${\le }_P$ is obvious. We call $\text{st}\left(P\right)$ the standard form of poset $P$. For example, . Obviously, $\text{st}\left(\epsilon \right)=\epsilon$.

Let $K$ be a subset of $P$. Define ${\left(P\mathrm{,}{\le }_P\right)}_K$ as poset $\left(K\mathrm{,}{\le }_K\right)$, where ${\le }_K$ is the partial order on $K$ satisfying

$k_1{\le }_K{k}_2\iff k_1{\le }_P{k}_2\mathrm{,}$

for any $k_1\mathrm{,}{k}_2$ in $K$. For convenience, we denote ${\left(P\mathrm{,}{\le }_P\right)}_K$ by $P_K$ when the partial order ${\le }_P$ is obvious, and call $P_K$ the restriction of $P$ on $K$, and $P_K$ a

subposet of poset $P$. For example, let poset , then

Obviously, $P_{\left\{\mathrm{1,2,3}\right\}}$, $P_{\left\{\mathrm{1,2,4}\right\}}$ and $P_{\left\{\mathrm{1,3}\right\}}$ are subposets of poset $P$.

In particular, $P_{\left[n\right]}=P$ and $P_{\varnothing }=ϵ$, for $P$ in ${\mathcal{P}}_n$.

3. Conjunction Product and Unshuffle Coproduct

In 2020, Aval, Bergrron and Machacek [20] defined a product and coproduct on posets, which are called the conjunction product and the unshuffle coproduct, respectively, without proofs. Here, we prove that the vector space spanned by posets with these operations is an algebra and a coalgebra.

Define the conjunction product $\ast$ on $\mathbb{K}\mathcal{P}$ by

$P\ast Q=P<Q^{\uparrow m},$

for $P$ in ${\mathcal{P}}_m$ and $Q$ in ${\mathcal{P}}_n$. Obviously, $P\ast Q$ in ${\mathcal{P}}_{m+n}$, and the conjunction product $\ast$ is not commutive.

Define the unit $\mu \mathrm{<mo>\; :\; </mo>}\mathbb{K}\to \mathbb{K}\mathcal{P}$ by $\mu \left(1\right)=ϵ$.

Example 1. Let and , then

Theorem 1. $\left(\mathbb{K}\mathcal{P}\mathrm{,}\ast \mathrm{,}\mu \right)$ is a graded algebra.

Proof It is easy to verify that $\mu$ is a unit.

Let $P_i$ be in $\mathcal{P}$ with $\left|P_i\right|=n_i$, $1\le i\le 3$. By the definition of conjunction product $\ast$, we have $P_1\ast P_2=P_1<P_2^{\uparrow n_1}$ and $P_2\ast P_3=P_2<P_3^{\uparrow n_2}$. Obviously, $P_1\ast P_2$ is in ${\mathcal{P}}_{n_1+n_2}$ and $P_2\ast P_3$ is in ${\mathcal{P}}_{n_2+n_3}$. Furthermore,

$\left(P_1\ast P_2\right)\ast P_3=\left(P_1<P_2^{\uparrow n_1}\right)<P_3^{\uparrow n_1+n_2}$

and

$P_1\ast \left(P_2\ast P_3\right)=P_1<{\left(P_2<P_3^{\uparrow n_2}\right)}^{\uparrow n_1}$

are both in ${\mathcal{P}}_{n_1+n_2+n_3}$. We have

$\begin{array}{c}{P}_1\ast \left(P_2\ast P_3\right)=P_1<{\left(P_2<P_3^{\uparrow n_2}\right)}^{\uparrow n_1}\\ =P_1<\left(P_2^{\uparrow n_1}<P_3^{\uparrow n_1+n_2}\right)\\ =\left(P_1<P_2^{\uparrow n_1}\right)<P_3^{\uparrow n_1+n_2}\\ =\left(P_1\ast P_2\right)\ast P_3.\end{array}$

From above, $\ast$ satisfies the associative law. Hence, $\left(\mathbb{K}\mathcal{P}\mathrm{,}\ast \mathrm{,}\mu \right)$ is an algebra. From the definitions of conjunction product $\ast$ and unit $\mu$, we have $\mathbb{K}{\mathcal{P}}_m\ast \mathbb{K}{\mathcal{P}}_n\subseteq \mathbb{K}{\mathcal{P}}_{m+n}$ and $\mu \left(\mathbb{K}\right)=\mathbb{K}{\mathcal{P}}_0$. Hence, the algebra $\left(\mathbb{K}\mathcal{P}\mathrm{,}\ast \mathrm{,}\mu \right)$ is graded.

Lemma 1. Define a linear mapping $h\mathrm{<mo>\; :\; </mo>}T\left(\mathbb{K}\bar{\mathcal{P}}\right)\to \mathbb{K}\mathcal{P}$ by

$h\left(\underset{k=0}{\overset{n}{{\displaystyle \oplus }}}{x}_{k1}\otimes \cdots \otimes x_{kk}\right)={\displaystyle \underset{k=0}{\overset{n}{\sum }}}{x}_{k1}\ast \cdots \ast x_{kk}\mathrm{,}$ (1)

where $x_{00}\in {\left(\mathbb{K}\bar{\mathcal{P}}\right)}^{\otimes 0}=\mathbb{K}$, $x_{ki}\in \mathbb{K}\bar{\mathcal{P}}$ for $i=1,\cdots ,k$ and $h\left(1_{\mathbb{K}}\right)=ϵ$. Denote

${\bar{\mathcal{P}}}^{\otimes n}=\left\{x_1\otimes x_2\otimes \cdots \otimes x_n\mathrm{<mo>\; |\; </mo>}{x}_1\mathrm{,}{x}_2\mathrm{,}\cdots \mathrm{,}{x}_n\in \bar{\mathcal{P}}\right\}\mathrm{.}$

For any

$x=p_{11}\otimes \cdots \otimes p_{1m}\in {\bar{\mathcal{P}}}^{\otimes m}\mathrm{,}$ (2)

and

$y=p_{21}\otimes \cdots \otimes p_{2n}\in {\bar{\mathcal{P}}}^{\otimes n}\mathrm{,}$ (3)

if $x\ne y$, then $h\left(x\right)\ne h\left(y\right)$.

Proof If $x\ne y$, then there exists $z$ such that $p_{1i}=p_{2i}$ for $1\le i\le z-1$ but $p_{1z}\ne p_{2z}$. We denote $r={\displaystyle {\sum }_{i=1}^{z-1}}\left|p_{1i}\right|$, $h\left(x\right)=P_1$ and $h\left(y\right)=P_2$. If $\left|p_{1z}\right|=\left|p_{2z}\right|$, then

$\text{st}\left({\left(P_1\right)}_{\left[r+\mathrm{1,}r+\left|p_z\right|\right]}\right)=p_{1z}\ne p_{2z}=\text{st}\left({\left(P_2\right)}_{\left[r+\mathrm{1,}r+\left|p_z\right|\right]}\right)\mathrm{.}$

So $h\left(x\right)\ne h\left(y\right)$. If $\left|p_{1z}\right|<\left|p_{2z}\right|$, then $r+\left|p_{1z}\right|$ is a split of $h\left(x\right)$ but not a split of $h\left(y\right)$. So $h\left(x\right)\ne h\left(y\right)$. Similarly, if $\left|p_{1z}\right|>\left|p_{2z}\right|$, we also have $h\left(x\right)\ne h\left(y\right)$.

Theorem 2. The algebra $\left(\mathbb{K}\mathcal{P}\mathrm{,}\ast \mathrm{,}\mu \right)$ is free on $\mathbb{K}\bar{\mathcal{P}}$.

Proof It is sufficient to prove $\left(\mathbb{K}\mathcal{P}\mathrm{,}\ast \mathrm{,}\mu \right)$ is isomorphic to the tensor algebra $T\left(\mathbb{K}\bar{\mathcal{P}}\right)$ through the mapping $h$ in (1). Obviously, $h$ is an algebra homomorphism. For any nonempty $P$ in $\mathcal{P}$, let $0=i_0<i_1<\cdots <i_t=n$ be all splits of $P$, then

$h\left(\text{st}\left(P_{\left[i_0+\mathrm{1,}{i}_1\right]}\right)\otimes \cdots \otimes \text{st}\left(P_{\left[i_{t-1}+\mathrm{1,}{i}_t\right]}\right)\right)=P\mathrm{.}$

Hence, $h$ is surjective.

For $x=x_{00}\oplus x_{11}\oplus x_{21}\otimes x_{22}\oplus \cdots \oplus x_{n1}\otimes x_{n2}\otimes \cdots \otimes x_{nn}$ in $T\left(\mathbb{K}\bar{\mathcal{P}}\right)$, where $x_{00}\in {\left(\mathbb{K}\bar{\mathcal{P}}\right)}^{\otimes 0}=\mathbb{K}$ and $x_{ki}\in \mathbb{K}\bar{\mathcal{P}}$ for $i=1,\cdots ,k$, $1\le k\le n$, suppose

$h\left(x\right)=\mathrm{0,}$ (4)

i.e.,

$\begin{array}{l}h\left(x_{00}\oplus x_{11}\oplus x_{21}\otimes x_{22}\oplus \cdots \oplus x_{n1}\otimes x_{n2}\otimes \cdots \otimes x_{nn}\right)\\ =h\left(x_{00}\right)+h\left(x_{11}\right)+h\left(x_{21}\otimes x_{22}\right)+\cdots +h\left(x_{n1}\otimes \cdots \otimes x_{nn}\right)\\ =0.\end{array}$ (5)

Obviously, any two terms in (5) are linearly independent because they have different numbers of splits. It means $h\left(x_{00}\right)=0$ and

$h\left(x_{k1}\otimes \cdots \otimes x_{kk}\right)=\mathrm{0,}$ (6)

for all $1\le k\le n$. By the associative law of tensor product, we have

$x_{k1}\otimes \cdots \otimes x_{kk}={\displaystyle \underset{j=1}{\overset{m}{\sum }}}{l}_j{x}_j,$

for some $x_j\in {\bar{\mathcal{P}}}^{\otimes k}$, $l_j\in \mathbb{K}$ and $m>0$, where $x_i\ne x_j$ for $i\ne j$. Then

$h\left(x_{k1}\otimes \cdots \otimes x_{kk}\right)=h\left({\displaystyle \underset{j=1}{\overset{m}{\sum }}}{l}_j{x}_j\right)={\displaystyle \underset{j=1}{\overset{m}{\sum }}}{l}_{j}h\left(x_j\right).$ (7)

By Lemma 1, ${\left\{h\left(x_j\right)\right\}}_{j=1}^m$ are linear independent. So $l_j=0$ for all $1\le j\le m$ from (6) and (7). Then

$x_{k1}\otimes \cdots \otimes x_{kk}={\displaystyle \underset{j=1}{\overset{m}{\sum }}}{l}_j{x}_j=0,$

for all $1\le k\le m$. Hence, $x=0$ in (4), i.e., $h$ is injective. Then $\mathbb{K}\mathcal{P}\cong T\left(\mathbb{K}\bar{\mathcal{P}}\right)$ is a free algebra on $\mathbb{K}\bar{\mathcal{P}}$.

Define the unshuffle coproduct $\Delta$ on $\mathbb{K}\mathcal{P}$ by

$\Delta \left(P\right)={\displaystyle \underset{I\subseteq \left[n\right]}{\sum }}\text{st}\left(P_I\right)\otimes \text{st}\left(P_{\left[n\right]\backslash I}\right)\mathrm{,}$

where $I$ traverses all subsets of $\left[n\right]$, for any non-empty poset $P$ in ${\mathcal{P}}_n$ and $\Delta \left(ϵ\right)=ϵ\otimes ϵ$. Obviously, the unshuffle coproduct $\Delta$ is cocommutive. Define the counit $\nu \mathrm{<mo>\; :\; </mo>}\mathbb{K}\mathcal{P}\to \mathbb{K}$ by

$\begin{array}{l}\nu \left(P\right)=\{\begin{array}{ll}\mathrm{1,}\hfill & P=ϵ\mathrm{,}\hfill \\ \mathrm{0,}\hfill & \text{otherwise}\mathrm{,}\hfill \end{array}\hfill \end{array}$

for $P$ in $\mathcal{P}$.

Example 2. Let , then

Theorem 3. $\left(\mathbb{K}\mathcal{P}\mathrm{,}\Delta \mathrm{,}\nu \right)$ is a graded coalgebra.

Proof It is easy to verify that $\nu$ is a counit. For $P$ in ${\mathcal{P}}_n$,

$\Delta \left(P\right)={\displaystyle \underset{I\subseteq \left[n\right]}{\sum }}\text{st}\left(P_I\right)\otimes \text{st}\left(P_{\left[n\right]\backslash I}\right)\mathrm{.}$

We have

$\begin{array}{c}\left(\text{id}\otimes \Delta \right)\circ \Delta \left(P\right)=\left(\text{id}\otimes \Delta \right)\circ \left({\displaystyle \underset{I\subseteq \left[n\right]}{\sum }}\text{st}\left(P_I\right)\otimes \text{st}\left(P_{\left[n\right]\backslash I}\right)\right)\\ ={\displaystyle \underset{I\subseteq \left[n\right]}{\sum }}\text{st}\left(P_I\right)\otimes \Delta \left(\text{st}\left(P_{\left[n\right]\backslash I}\right)\right)\\ ={\displaystyle \underset{I\subseteq \left[n\right]}{\sum }}\text{st}\left(P_I\right)\otimes \left({\displaystyle \underset{J\subseteq \left[n\right]\backslash I}{\sum }}\text{st}\left(P_J\right)\otimes \text{st}\left(P_{\left(\left[n\right]\backslash I\right)\backslash J}\right)\right)\end{array}$

and

$\begin{array}{c}\left(\Delta \otimes \text{id}\right)\circ \Delta \left(P\right)=\left(\Delta \otimes \text{id}\right)\circ \left({\displaystyle \underset{I\subseteq \left[n\right]}{\sum }}\text{st}\left(P_I\right)\otimes \text{st}\left(P_{\left[n\right]\backslash I}\right)\right)\\ ={\displaystyle \underset{I\subseteq \left[n\right]}{\sum }}\Delta \left(\text{st}\left(P_I\right)\right)\otimes \text{st}\left(P_{\left[n\right]\backslash I}\right)\\ ={\displaystyle \underset{I\subseteq \left[n\right]}{\sum }}\left({\displaystyle \underset{A\subseteq I}{\sum }}\text{st}\left(P_A\right)\otimes \text{st}\left(P_{I\backslash A}\right)\right)\otimes \text{st}\left(P_{\left[n\right]\backslash I}\right)\\ ={\displaystyle \underset{A\subseteq I}{\sum }}{\displaystyle \underset{I\subseteq \left[n\right]}{\sum }}\text{st}\left(P_A\right)\otimes \text{st}\left(P_{I\backslash A}\right)\otimes \text{st}\left(P_{\left[n\right]\backslash I}\right)\\ ={\displaystyle \underset{A\subseteq \left[n\right]}{\sum }}\text{st}\left(P_A\right)\otimes \left({\displaystyle \underset{B\subseteq \left[n\right]\backslash A}{\sum }}\text{st}\left(P_B\right)\otimes \text{st}\left(P_{\left(\left[n\right]\backslash A\right)\backslash B}\right)\right)\mathrm{.}\end{array}$

Therefore

$\left(\text{id}\otimes \Delta \right)\circ \Delta \left(P\right)=\left(\Delta \otimes \text{id}\right)\circ \Delta \left(P\right)\mathrm{.}$

From above, $\Delta$ satisfies the coassociative law. Hence, $\left(\mathbb{K}\mathcal{P}\mathrm{,}\Delta \mathrm{,}\nu \right)$ is a coalgebra.

From the definitions of $\Delta$ and $\nu$, we have $\Delta \left(\mathbb{K}{\mathcal{P}}_n\right)\subseteq {\underset{}{{\displaystyle {{\displaystyle \oplus }}_{}}}}_{i=0}^n\left(\mathbb{K}{\mathcal{P}}_i\otimes \mathbb{K}{\mathcal{P}}_{n-i}\right)$ and $\nu \left(\mathbb{K}{\mathcal{P}}_0\right)=\mathbb{K}$. Hence, the coalgebra $\left(\mathbb{K}\mathcal{P}\mathrm{,}\Delta \mathrm{,}\nu \right)$ is graded.

4. Conclusions

Let $\mathbb{K}\mathcal{P}$ be the vector space spanned by posets. Firstly, we give the definitions of conjunction product $\ast$ and unshuffle coproduct $\Delta$ on $\mathbb{K}\mathcal{P}$. Then we prove that the conjunction product $\ast$ satisfies the associativity. So $\left(\mathbb{K}\mathcal{P}\mathrm{,}\ast \mathrm{,}\mu \right)$ is an algebra. Futhermore, we prove that $\left(\mathbb{K}\mathcal{P}\mathrm{,}\ast \mathrm{,}\mu \right)$ is graded and free on $\mathbb{K}\bar{\mathcal{P}}$, where $\bar{\mathcal{P}}$ contains all indecomposable posets in $\mathcal{P}$. Finally, we prove that unshuffle coproduct $\Delta$ satisfies the coassociativity and $\left(\mathbb{K}\mathcal{P}\mathrm{,}\Delta \mathrm{,}\nu \right)$ is a graded coalgebra.

Acknowledgements

This work is supported by the National Natural Science Foundation of China (Nos. 11701339, 12071265 and 11771256).

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Dilworth, R.P. (1950) A Decomposition Theorem for Partially Ordered Sets. Annals of Mathematics, 51, 161-166. https://doi.org/10.2307/1969503
[2]	Fulkerson, D.R. (1956) Note on Dilworth’s Decomposition for Partially Ordered Sets. Proceedings of the American Mathematical Society, 7, 701-702. https://doi.org/10.1090/S0002-9939-1956-0078334-6
[3]	Tverberg, H. (1967) On Dilworth’s Decomposition Theorem for Partially Ordered Sets. Journal of Combinatorial Theory, Series A, 3, 305-306. https://doi.org/10.1016/S0021-9800(67)80079-6
[4]	Pretzel, O. (1979) Another Proof of Dilworth’s Decomposition Theorem. Discrete Mathematics, 25, 91-92. https://doi.org/10.1016/0012-365X(79)90157-2
[5]	Galvin, F. (1994) A proof of Dilworth’s Chain Decomposition Theorem. The American Mathematical Monthly, 101, 352-353. https://doi.org/10.1080/00029890.1994.11996954
[6]	Rota, G.C. (1964) On the Foundations of Combinatorial Theory I. Theory of Möbius Functions. Probability Theory and Related Fields, 2, 340-368. https://doi.org/10.1007/BF00531932
[7]	Stanley, R.P. (1972) Ordered Structures and Partitions. Memoirs of the American Mathematical Society, No. 119. https://doi.org/10.1090/memo/0119
[8]	Stanley, R.P. (1976) Binomial Posets, Möbius Inversion, Permutation Enumeration. Journal of Combinatorial Theory, Series B, 20, 336-356. https://doi.org/10.1016/0097-3165(76)90028-5
[9]	Trotter, W.T. and Moore, J.I. (1977) The Dimension of Planar Posets. Journal of Combinatorial Theory, Series B, 22, 54-67. https://doi.org/10.1016/0095-8956(77)90048-X
[10]	Stanley, R.P. (1988) Differential Posets. Journal of the American Mathematical Society, 1, 919-961. https://doi.org/10.1090/S0894-0347-1988-0941434-9
[11]	Stanley, R.P. (1990) Variations on Differential Posets. In: Stanton, D., Ed., Invariant Theory and Tableaux, The IMA Volumes in Mathematics and Its Applications, Vol. 19, Springer-Verlag, New York, 145-165.
[12]	Lam, T. (2008) Signed Differential Posets and Sign-Imbalance. Journal of Combinatorial Theory, Series A, 115, 466-484. https://doi.org/10.1016/j.jcta.2007.07.003
[13]	Lewis, J.B. (2007) On Differential Posets. Undergraduate Thesis, Harvard University, Cambridge. https://cpb-us-e1.wpmucdn.com/blogs.gwu.edu/dist/5/693/files/2018/04/JBLHarvardSeniorThesis-20drube.pdf
[14]	Miller, A. (2013) Differential Posets Have Strict Rank Growth, a Conjecture of Stanley. Order, 30, 657-662. https://doi.org/10.1007/s11083-012-9268-y
[15]	Miller, A. and Reiner, V. (2009) Differential Posets and Smith Normal Forms. Order, 26, 197-228. https://doi.org/10.1007/s11083-009-9114-z
[16]	Aguiar, M. and Sottile, F. (2005) Structure of the Malvenuto-Reutenauer Hopf Algebra of Permutations. Advances in Mathematics, 191, 225-275. https://doi.org/10.1016/j.aim.2004.03.007
[17]	Zhao, M. and Li, H. (2020) A Hopf Algebra Structure on Permutations. Journal of Shandong Normal University (Natural Science), 4, 395-401.
[18]	Zhao, M. and Li, H. (2021) A Pair of Dual Hopf Algebras on Permutations. AIMS Mathematics, 6, 5106-5123. https://doi.org/10.3934/math.2021302
[19]	Liu, M. and Li, H. (2021) A Hopf Algebra on Permutations Arising from Super-Shuffle Product. Symmetry, 13, 1010. https://doi.org/10.3390/sym13061010
[20]	Aval, J.C., Bergeron, N. and Machacek, J. (2020) New Invariants for Permutations, Orders and Graphs. Advances in Applied Mathematics, 121, Article ID: 102080. https://doi.org/10.1016/j.aam.2020.102080
[21]	Sweedler, M.E. (1969) Hopf Algebras. Mathematics Lecture Note Series. W. A. Benjamin, Inc., New York, 41-91.
[22]	Joni, S.A. and Rota, G.C. (1979) Coalgebras and Bialgebras in Combinatorics. Studies in Applied Mathematics, 61, 93-139. https://doi.org/10.1002/sapm197961293
[23]	Milnor, J.W. and Moore, J.C. (1965) On the Structure of Hopf Algebras. Annals of Mathematics, 81, 211-264. https://doi.org/10.2307/1970615
[24]	Ehrenborg, R. (1996) On Posets and Hopf Algebras. Advances in Mathematics, 119, 1-25. https://doi.org/10.1006/aima.1996.0026