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.

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 [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 ш G on permutations. Later, they [18] defined a new product and a new coproduct Δ * on permutations, proved that ( K S , , μ ) is a graded K -algebra and ( K S , Δ * , ν ) is a graded K -coalgebra, where 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 ( K S , ш _ , μ ) is a graded algebra and ( K S , Δ , ν ) 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 ( A , m , μ ) an R -algebra if there exist two maps m : A A A and μ : R A such that the diagrams in Figure 1 are commutative. Here m is called a product and μ a unit.

The R-algebra ( A , m , μ ) is graded if A = i 0 A i and m ( A s A t ) 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 ( A , Δ , ν ) an R -coalgebra if there exist two maps Δ : A A A and ν : A R such that the diagrams in Figure 2 are commutative. Here Δ is called a coproduct and ν a counit.

The R -coalgebra ( A , Δ , ν ) is graded if A = i 0 A i and Δ ( A n ) i ( A i A n i ) , for all n .

A coalgebra A is cocommutative if the diagram in Figure 3 commutes, where τ ( a b ) = b a , for all a , b in A .

Let V be a vector space over field K . Denote the tensor algebra on V by T ( V ) = n 0 V n , where V 0 = K and V n = V V n times .

Define the multiplication on T ( V ) 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.

μ : K T ( V ) on T ( V ) by μ ( a ) = a , for a K . Then the algebra T ( V ) = n 0 V n is free on V since it satisfies the following universal property: for each K -algebra A and each linear map f : V A , there exists a unique algebra homomorphism g : T ( V ) A such that g ι = f where ι : V T ( V ) 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 P is called a poset, denoted by ( P , P ) . The set P is called the ground set of poset ( P , P ) . 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 P y and there is no element z that differs from x , y and satisfies x P z P y , then we say that y covers x , denoted by x P y , and we also call ( x , y ) a cover relation in P . Define A ( P ) to be the set of all cover relations in P by

A ( P ) = { ( x , y ) | x y , x , y P } .

If A ( P ) is given in poset P , then we can get the partial order relation P corresponding to the cover relations through reflexivity, antisymmetry and transitivity. Obviously, A ( P ) and P are uniquely determined by each other.

The two elements x and y in poset P are called comparable, if either x P y or y 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 P y nor y 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 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 = { 2,3,4 } with A ( P ) = { ( 2,3 ) , ( 3,4 ) } , i.e., 3 covers 2 and 4 covers 3, according to transitivity, we have 2 P 4 . Further, we get poset . Similarly, if Q = { 1,2,3 } with A ( Q ) = { ( 1,3 ) , ( 2,3 ) } , then poset .

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

Let P and Q be disjoint sets with partial orders P and Q , respectively. Define T to be the union of P and Q with partial order T given by the cover relations

A ( T ) = A ( P ) A ( Q ) { ( x , y ) | x max ( P ) , y min ( Q ) } .

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 A ( P ) = { ( 4,2 ) , ( 5,2 ) } , A ( Q ) = { } , max ( P ) = { 2 } and min ( Q ) = { 1,3 } . Hence we have A ( T ) = { ( 4,2 ) , ( 5,2 ) , ( 2,1 ) , ( 2,3 ) } , i.e., .

Denote P n to be the set of all posets on [ n ] = { 1 , 2 , , n } , where P 0 = { ε } . For example, when n = 3 ,

Let P = n 0 P n + be the disjoint union of P n , and K P = n 0 K P n , where K P n is the linear space spanned by P n over field K .

For a positive integer n , define ( P n , P n ) as a poset by increasing each element in P by n satisfying

( x + n ) P n ( y + n ) x P y ,

for x , y in P . Similarly, define ( P n , P n ) as a poset by reducing each element in P by n satisfying

( x n ) P n ( y n ) x P y ,

for x , y in P . For example, let , then and .

For a poset P in P n , we call n a global split of P if

P = P [ i ] < P [ n ] \ [ i ] ,

where 0 i n . If a nonempty poset has no global splits except 0 and n , we call it an indecomposable poset. We denote P ¯ n as the subset of P n containing all indecomposable posets in P n , and P ¯ = n 1 P ¯ n + .

For a nonempty set of intergers S = { s 1 , s 2 , , s n } with s 1 < s 2 < < s n , denote st S as a mapping from S to [ n ] by st S ( s i ) = i for each 1 i n .

Let ( P , P ) be a poset, where P is an interger set. We define st ( P , P ) = ( st ( P ) , st ( P ) ) , where st ( P ) = [ | P | ] and st ( P ) is the partial order on [ | P | ] satisfying

st P ( i ) st ( P ) st P ( j ) i P j ,

for any i , j in P . For convenience, we denote the st ( P , P ) as st ( P ) when the partial order P is obvious. We call st ( P ) the standard form of poset P . For example, . Obviously, st ( ε ) = ε .

Let K be a subset of P . Define ( P , P ) K as poset ( K , K ) , where K is the partial order on K satisfying

k 1 K k 2 k 1 P k 2 ,

for any k 1 , k 2 in K . For convenience, we denote ( P , P ) K by P K when the partial order 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 { 1,2,3 } , P { 1,2,4 } and P { 1,3 } are subposets of poset P .

In particular, P [ n ] = P and P = ϵ , for P in 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 on K P by

P Q = P < Q m ,

for P in P m and Q in P n . Obviously, P Q in P m + n , and the conjunction product is not commutive.

Define the unit μ : K K P by μ ( 1 ) = ϵ .

Example 1. Let and , then

Theorem 1. ( K P , , μ ) is a graded algebra.

Proof It is easy to verify that μ is a unit.

Let P i be in P with | P i | = n i , 1 i 3 . By the definition of conjunction product , we have P 1 P 2 = P 1 < P 2 n 1 and P 2 P 3 = P 2 < P 3 n 2 . Obviously, P 1 P 2 is in P n 1 + n 2 and P 2 P 3 is in P n 2 + n 3 . Furthermore,

( P 1 P 2 ) P 3 = ( P 1 < P 2 n 1 ) < P 3 n 1 + n 2

and

P 1 ( P 2 P 3 ) = P 1 < ( P 2 < P 3 n 2 ) n 1

are both in P n 1 + n 2 + n 3 . We have

P 1 ( P 2 P 3 ) = P 1 < ( P 2 < P 3 n 2 ) n 1 = P 1 < ( P 2 n 1 < P 3 n 1 + n 2 ) = ( P 1 < P 2 n 1 ) < P 3 n 1 + n 2 = ( P 1 P 2 ) P 3 .

From above, satisfies the associative law. Hence, ( K P , , μ ) is an algebra. From the definitions of conjunction product and unit μ , we have K P m K P n K P m + n and μ ( K ) = K P 0 . Hence, the algebra ( K P , , μ ) is graded.

Lemma 1. Define a linear mapping h : T ( K P ¯ ) K P by

h ( k = 0 n x k 1 x k k ) = k = 0 n x k 1 x k k , (1)

where x 00 ( K P ¯ ) 0 = K , x k i K P ¯ for i = 1 , , k and h ( 1 K ) = ϵ . Denote

P ¯ n = { x 1 x 2 x n | x 1 , x 2 , , x n P ¯ } .

For any

x = p 11 p 1 m P ¯ m , (2)

and

y = p 21 p 2 n P ¯ n , (3)

if x y , then h ( x ) h ( y ) .

Proof If x y , then there exists z such that p 1 i = p 2 i for 1 i z 1 but p 1 z p 2 z . We denote r = i = 1 z 1 | p 1 i | , h ( x ) = P 1 and h ( y ) = P 2 . If | p 1 z | = | p 2 z | , then

st ( ( P 1 ) [ r + 1, r + | p z | ] ) = p 1 z p 2 z = st ( ( P 2 ) [ r + 1, r + | p z | ] ) .

So h ( x ) h ( y ) . If | p 1 z | < | p 2 z | , then r + | p 1 z | is a split of h ( x ) but not a split of h ( y ) . So h ( x ) h ( y ) . Similarly, if | p 1 z | > | p 2 z | , we also have h ( x ) h ( y ) .

Theorem 2. The algebra ( K P , , μ ) is free on K P ¯ .

Proof It is sufficient to prove ( K P , , μ ) is isomorphic to the tensor algebra T ( K P ¯ ) through the mapping h in (1). Obviously, h is an algebra homomorphism. For any nonempty P in P , let 0 = i 0 < i 1 < < i t = n be all splits of P , then

h ( st ( P [ i 0 + 1, i 1 ] ) st ( P [ i t 1 + 1, i t ] ) ) = P .

Hence, h is surjective.

For x = x 00 x 11 x 21 x 22 x n 1 x n 2 x n n in T ( K P ¯ ) , where x 00 ( K P ¯ ) 0 = K and x k i K P ¯ for i = 1 , , k , 1 k n , suppose

h ( x ) = 0, (4)

i.e.,

h ( x 00 x 11 x 21 x 22 x n 1 x n 2 x n n ) = h ( x 00 ) + h ( x 11 ) + h ( x 21 x 22 ) + + h ( x n 1 x n n ) = 0. (5)

Obviously, any two terms in (5) are linearly independent because they have different numbers of splits. It means h ( x 00 ) = 0 and

h ( x k 1 x k k ) = 0, (6)

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

x k 1 x k k = j = 1 m l j x j ,

for some x j P ¯ k , l j K and m > 0 , where x i x j for i j . Then

h ( x k 1 x k k ) = h ( j = 1 m l j x j ) = j = 1 m l j h ( x j ) . (7)

By Lemma 1, { h ( x j ) } j = 1 m are linear independent. So l j = 0 for all 1 j m from (6) and (7). Then

x k 1 x k k = j = 1 m l j x j = 0 ,

for all 1 k m . Hence, x = 0 in (4), i.e., h is injective. Then K P T ( K P ¯ ) is a free algebra on K P ¯ .

Define the unshuffle coproduct Δ on K P by

Δ ( P ) = I [ n ] st ( P I ) st ( P [ n ] \ I ) ,

where I traverses all subsets of [ n ] , for any non-empty poset P in P n and Δ ( ϵ ) = ϵ ϵ . Obviously, the unshuffle coproduct Δ is cocommutive. Define the counit ν : K P K by

ν ( P ) = { 1, P = ϵ , 0, otherwise ,

for P in P .

Example 2. Let , then

Theorem 3. ( K P , Δ , ν ) is a graded coalgebra.

Proof It is easy to verify that ν is a counit. For P in P n ,

Δ ( P ) = I [ n ] st ( P I ) st ( P [ n ] \ I ) .

We have

( id Δ ) Δ ( P ) = ( id Δ ) ( I [ n ] st ( P I ) st ( P [ n ] \ I ) ) = I [ n ] st ( P I ) Δ ( st ( P [ n ] \ I ) ) = I [ n ] st ( P I ) ( J [ n ] \ I st ( P J ) st ( P ( [ n ] \ I ) \ J ) )

and

( Δ id ) Δ ( P ) = ( Δ id ) ( I [ n ] st ( P I ) st ( P [ n ] \ I ) ) = I [ n ] Δ ( st ( P I ) ) st ( P [ n ] \ I ) = I [ n ] ( A I st ( P A ) st ( P I \ A ) ) st ( P [ n ] \ I ) = A I I [ n ] st ( P A ) st ( P I \ A ) st ( P [ n ] \ I ) = A [ n ] st ( P A ) ( B [ n ] \ A st ( P B ) st ( P ( [ n ] \ A ) \ B ) ) .

Therefore

( id Δ ) Δ ( P ) = ( Δ id ) Δ ( P ) .

From above, Δ satisfies the coassociative law. Hence, ( K P , Δ , ν ) is a coalgebra.

From the definitions of Δ and ν , we have Δ ( K P n ) i = 0 n ( K P i K P n i ) and ν ( K P 0 ) = K . Hence, the coalgebra ( K P , Δ , ν ) is graded.

4. Conclusions

Let K P be the vector space spanned by posets. Firstly, we give the definitions of conjunction product and unshuffle coproduct Δ on K P . Then we prove that the conjunction product satisfies the associativity. So ( K P , , μ ) is an algebra. Futhermore, we prove that ( K P , , μ ) is graded and free on K P ¯ , where P ¯ contains all indecomposable posets in P . Finally, we prove that unshuffle coproduct Δ satisfies the coassociativity and ( K P , Δ , ν ) 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

Copyright © 2023 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.