Algebra and Coalgebra on Posets

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

Share and Cite:

Yuan, R. and Li, H. (2022) Algebra and Coalgebra on Posets. Open Journal of Applied Sciences, 12, 1232-1242. doi: 10.4236/ojapps.2022.127083.

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  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 , Tverberg , Pretzel  and Galvin .

In 1964, Rota  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  studied ordered structures and partitions. Later, he proved several identities associated with the binomial posets . In 1977, Trotter and Moore  studied the dimension of planar posets and the dimension of trees. In 1988, Stanley  first introduced the differential poset with combinatorial and algebraic properties. For more works on differential posets, see     .

In 2005, Aguiar and Sottile  introduced the global descents of permutations in the symmetric group ${S}_{n}$. In 2020, based on the global descents, Zhao and Li  studied a new shuffle product ${\text{ш}}_{G}$ on permutations. Later, they  defined a new product $\diamond$ and a new coproduct ${\Delta }^{*}$ on permutations, proved that $\left(\mathbb{K}S,\diamond ,\mu \right)$ is a graded $\mathbb{K}$ -algebra and $\left(\mathbb{K}S,{\Delta }^{*},\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  introduced the super-shuffle product and the cut-box coproduct on permutations and proved that $\left(\mathbb{K}S,\text{ш _},\mu \right)$ is a graded algebra and $\left(\mathbb{K}S,{\Delta }_{\diamond },\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  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   for more details. Let $R$ be an associative commutative ring with identity.

For an $R$ -module $A$, we call $\left(A,m,\mu \right)$ an $R$ -algebra if there exist two maps $m:A\otimes A\to A$ and $\mu :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,m,\mu \right)$ is graded if $A={\oplus }_{i\ge 0}\text{ }\text{ }{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,\Delta ,\nu \right)$ an $R$ -coalgebra if there exist two maps $\Delta :A\to A\otimes A$ and $\nu :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,\Delta ,\nu \right)$ is graded if $A={\oplus }_{i\ge 0}\text{ }\text{ }{A}_{i}$ and $\Delta \left({A}_{n}\right)\subseteq {\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)={\oplus }_{n\ge 0}\text{ }\text{ }{V}^{\otimes n}$, where ${V}^{\otimes 0}=\mathbb{K}$ and ${V}^{\otimes n}=\underset{n\text{\hspace{0.17em}}\text{times}}{\underset{︸}{V\otimes \cdots \otimes V}}.$

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 :\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)={\oplus }_{n\ge 0}\text{ }\text{ }{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:V\to A$, there exists a unique algebra homomorphism $g:T\left(V\right)\to A$ such that $g\iota =f$ where $\iota :V\to T\left(V\right)$ is the inclusion map.

2.2. Basic Notations

Now let’s recall some notations on posets; see   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,{\le }_{P}\right)$. The set $P$ is called the ground set of poset $\left(P,{\le }_{P}\right)$. We denote the number of elements of $P$ by $|P|$. 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,y$ in poset $P$, if $x{\le }_{P}y$ and there is no element $z$ that differs from $x,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,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,y\right)|x⋖y,x,y\in P\right\}.$

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\{2,3,4\right\}$ with $\mathcal{A}\left(P\right)=\left\{\left(2,3\right),\left(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\{1,2,3\right\}$ with $\mathcal{A}\left(Q\right)=\left\{\left(1,3\right),\left(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\{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,y\right)|x\in \text{max}\left(P\right),y\in \text{min}\left(Q\right)\right\}.$

We denote the poset $T$ as $P, which means $<$ is an operation for posets. Obviously, $<$ satisfies the associative law. For example, Let and , then $\mathcal{A}\left(P\right)=\left\{\left(4,2\right),\left(5,2\right)\right\}$, $\mathcal{A}\left(Q\right)=\left\{\varnothing \right\}$, $\text{max}\left(P\right)=\left\{2\right\}$ and $\text{min}\left(Q\right)=\left\{1,3\right\}$. Hence we have $\mathcal{A}\left(T\right)=\left\{\left(4,2\right),\left(5,2\right),\left(2,1\right),\left(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}={\cup }_{n\ge 0}\text{ }\text{ }{\mathcal{P}}_{n}+$ be the disjoint union of ${\mathcal{P}}_{n}$, and $\mathbb{K}\mathcal{P}={\oplus }_{n\ge 0}\text{ }\text{ }\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}^{↑n},{\le }_{{P}^{↑n}}\right)$ as a poset by increasing each element in $P$ by $n$ satisfying

$\left(x+n\right){\le }_{{P}^{↑n}}\left(y+n\right)⇔x{\le }_{P}y,$

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

$\left(x-n\right){\le }_{{P}^{↓n}}\left(y-n\right)⇔x{\le }_{P}y,$

for $x,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]\\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 ${\stackrel{¯}{\mathcal{P}}}_{n}$ as the subset of ${\mathcal{P}}_{n}$ containing all indecomposable posets in ${\mathcal{P}}_{n}$, and $\stackrel{¯}{\mathcal{P}}={\cup }_{n\ge 1}\text{ }\text{ }{\stackrel{¯}{\mathcal{P}}}_{n}+$.

For a nonempty set of intergers $S=\left\{{s}_{1},{s}_{2},\cdots ,{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,{\le }_{P}\right)$ be a poset, where $P$ is an interger set. We define $\text{st}\left(P,{\le }_{P}\right)=\left(\text{st}\left(P\right),{\le }_{\text{st}\left(P\right)}\right)$, where $\text{st}\left(P\right)=\left[|P|\right]$ and ${\le }_{\text{st}\left(P\right)}$ is the partial order on $\left[|P|\right]$ satisfying

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

for any $i,j$ in $P$. For convenience, we denote the $\text{st}\left(P,{\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,{\le }_{P}\right)}_{K}$ as poset $\left(K,{\le }_{K}\right)$, where ${\le }_{K}$ is the partial order on $K$ satisfying

${k}_{1}{\le }_{K}{k}_{2}⇔{k}_{1}{\le }_{P}{k}_{2},$

for any ${k}_{1},{k}_{2}$ in $K$. For convenience, we denote ${\left(P,{\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\{1,2,3\right\}}$, ${P}_{\left\{1,2,4\right\}}$ and ${P}_{\left\{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  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}^{↑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 :\mathbb{K}\to \mathbb{K}\mathcal{P}$ by $\mu \left(1\right)=ϵ$.

Example 1. Let and , then

Theorem 1. $\left(\mathbb{K}\mathcal{P},\ast ,\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 $|{P}_{i}|={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}^{↑{n}_{1}}$ and ${P}_{2}\ast {P}_{3}={P}_{2}<{P}_{3}^{↑{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}^{↑{n}_{1}}\right)<{P}_{3}^{↑{n}_{1}+{n}_{2}}$

and

${P}_{1}\ast \left({P}_{2}\ast {P}_{3}\right)={P}_{1}<{\left({P}_{2}<{P}_{3}^{↑{n}_{2}}\right)}^{↑{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}^{↑{n}_{2}}\right)}^{↑{n}_{1}}\\ ={P}_{1}<\left({P}_{2}^{↑{n}_{1}}<{P}_{3}^{↑{n}_{1}+{n}_{2}}\right)\\ =\left({P}_{1}<{P}_{2}^{↑{n}_{1}}\right)<{P}_{3}^{↑{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},\ast ,\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},\ast ,\mu \right)$ is graded.

Lemma 1. Define a linear mapping $h:T\left(\mathbb{K}\stackrel{¯}{\mathcal{P}}\right)\to \mathbb{K}\mathcal{P}$ by

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

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

${\stackrel{¯}{\mathcal{P}}}^{\otimes n}=\left\{{x}_{1}\otimes {x}_{2}\otimes \cdots \otimes {x}_{n}|{x}_{1},{x}_{2},\cdots ,{x}_{n}\in \stackrel{¯}{\mathcal{P}}\right\}.$

For any

$x={p}_{11}\otimes \cdots \otimes {p}_{1m}\in {\stackrel{¯}{\mathcal{P}}}^{\otimes m},$ (2)

and

$y={p}_{21}\otimes \cdots \otimes {p}_{2n}\in {\stackrel{¯}{\mathcal{P}}}^{\otimes n},$ (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={\sum }_{i=1}^{z-1}|{p}_{1i}|$, $h\left(x\right)={P}_{1}$ and $h\left(y\right)={P}_{2}$. If $|{p}_{1z}|=|{p}_{2z}|$, then

$\text{st}\left({\left({P}_{1}\right)}_{\left[r+1,r+|{p}_{z}|\right]}\right)={p}_{1z}\ne {p}_{2z}=\text{st}\left({\left({P}_{2}\right)}_{\left[r+1,r+|{p}_{z}|\right]}\right).$

So $h\left(x\right)\ne h\left(y\right)$. If $|{p}_{1z}|<|{p}_{2z}|$, then $r+|{p}_{1z}|$ 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 $|{p}_{1z}|>|{p}_{2z}|$, we also have $h\left(x\right)\ne h\left(y\right)$.

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

Proof It is sufficient to prove $\left(\mathbb{K}\mathcal{P},\ast ,\mu \right)$ is isomorphic to the tensor algebra $T\left(\mathbb{K}\stackrel{¯}{\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}+1,{i}_{1}\right]}\right)\otimes \cdots \otimes \text{st}\left({P}_{\left[{i}_{t-1}+1,{i}_{t}\right]}\right)\right)=P.$

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}\stackrel{¯}{\mathcal{P}}\right)$, where ${x}_{00}\in {\left(\mathbb{K}\stackrel{¯}{\mathcal{P}}\right)}^{\otimes 0}=\mathbb{K}$ and ${x}_{ki}\in \mathbb{K}\stackrel{¯}{\mathcal{P}}$ for $i=1,\cdots ,k$, $1\le k\le n$, suppose

$h\left(x\right)=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)=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}=\underset{j=1}{\overset{m}{\sum }}\text{ }\text{ }{l}_{j}{x}_{j},$

for some ${x}_{j}\in {\stackrel{¯}{\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(\underset{j=1}{\overset{m}{\sum }}\text{ }\text{ }{l}_{j}{x}_{j}\right)=\underset{j=1}{\overset{m}{\sum }}\text{ }\text{ }{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}=\underset{j=1}{\overset{m}{\sum }}\text{ }\text{ }{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}\stackrel{¯}{\mathcal{P}}\right)$ is a free algebra on $\mathbb{K}\stackrel{¯}{\mathcal{P}}$.

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

$\Delta \left(P\right)=\underset{I\subseteq \left[n\right]}{\sum }\text{ }\text{ }\text{st}\left({P}_{I}\right)\otimes \text{st}\left({P}_{\left[n\right]\I}\right),$

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 :\mathbb{K}\mathcal{P}\to \mathbb{K}$ by

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

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

Example 2. Let , then

Theorem 3. $\left(\mathbb{K}\mathcal{P},\Delta ,\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)=\underset{I\subseteq \left[n\right]}{\sum }\text{ }\text{ }\text{st}\left({P}_{I}\right)\otimes \text{st}\left({P}_{\left[n\right]\I}\right).$

We have

$\begin{array}{c}\left(\text{id}\otimes \Delta \right)\circ \Delta \left(P\right)=\left(\text{id}\otimes \Delta \right)\circ \left(\underset{I\subseteq \left[n\right]}{\sum }\text{ }\text{ }\text{st}\left({P}_{I}\right)\otimes \text{st}\left({P}_{\left[n\right]\I}\right)\right)\\ =\underset{I\subseteq \left[n\right]}{\sum }\text{ }\text{ }\text{st}\left({P}_{I}\right)\otimes \Delta \left(\text{st}\left({P}_{\left[n\right]\I}\right)\right)\\ =\underset{I\subseteq \left[n\right]}{\sum }\text{ }\text{ }\text{st}\left({P}_{I}\right)\otimes \left(\underset{J\subseteq \left[n\right]\I}{\sum }\text{ }\text{ }\text{st}\left({P}_{J}\right)\otimes \text{st}\left({P}_{\left(\left[n\right]\I\right)\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(\underset{I\subseteq \left[n\right]}{\sum }\text{ }\text{ }\text{st}\left({P}_{I}\right)\otimes \text{st}\left({P}_{\left[n\right]\I}\right)\right)\\ =\underset{I\subseteq \left[n\right]}{\sum }\text{ }\text{ }\Delta \left(\text{st}\left({P}_{I}\right)\right)\otimes \text{st}\left({P}_{\left[n\right]\I}\right)\\ =\underset{I\subseteq \left[n\right]}{\sum }\left(\underset{A\subseteq I}{\sum }\text{ }\text{ }\text{st}\left({P}_{A}\right)\otimes \text{st}\left({P}_{I\A}\right)\right)\otimes \text{st}\left({P}_{\left[n\right]\I}\right)\\ =\underset{A\subseteq I}{\sum }\text{ }\text{ }\underset{I\subseteq \left[n\right]}{\sum }\text{ }\text{ }\text{st}\left({P}_{A}\right)\otimes \text{st}\left({P}_{I\A}\right)\otimes \text{st}\left({P}_{\left[n\right]\I}\right)\\ =\underset{A\subseteq \left[n\right]}{\sum }\text{ }\text{ }\text{st}\left({P}_{A}\right)\otimes \left(\underset{B\subseteq \left[n\right]\A}{\sum }\text{ }\text{ }\text{st}\left({P}_{B}\right)\otimes \text{st}\left({P}_{\left(\left[n\right]\A\right)\B}\right)\right).\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).$

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

From the definitions of $\Delta$ and $\nu$, we have $\Delta \left(\mathbb{K}{\mathcal{P}}_{n}\right)\subseteq {\underset{}{{\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},\Delta ,\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},\ast ,\mu \right)$ is an algebra. Futhermore, we prove that $\left(\mathbb{K}\mathcal{P},\ast ,\mu \right)$ is graded and free on $\mathbb{K}\stackrel{¯}{\mathcal{P}}$, where $\stackrel{¯}{\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},\Delta ,\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.

  Dilworth, R.P. (1950) A Decomposition Theorem for Partially Ordered Sets. Annals of Mathematics, 51, 161-166. https://doi.org/10.2307/1969503  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  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  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  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  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  Stanley, R.P. (1972) Ordered Structures and Partitions. Memoirs of the American Mathematical Society, No. 119. https://doi.org/10.1090/memo/0119  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  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  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  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.  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  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  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  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  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  Zhao, M. and Li, H. (2020) A Hopf Algebra Structure on Permutations. Journal of Shandong Normal University (Natural Science), 4, 395-401.  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  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  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  Sweedler, M.E. (1969) Hopf Algebras. Mathematics Lecture Note Series. W. A. Benjamin, Inc., New York, 41-91.  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  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  Ehrenborg, R. (1996) On Posets and Hopf Algebras. Advances in Mathematics, 119, 1-25. https://doi.org/10.1006/aima.1996.0026     customer@scirp.org +86 18163351462(WhatsApp) 1655362766  Paper Publishing WeChat 