R.N. Yadav et al. / BIBECHANA 13 (2016) 132-136: RCOST p.132 (Online Publication: Dec., 2015) BIBECHANA A Multidisciplinary Journal of Science, Technology and Mathematics ISSN 2091-0762 (Print), 2382-5340 (0nline) Journal homepage: http://nepjol.info/index.php/BIBECHANA Publisher: Research Council of Science and Technology, Biratnagar, Nepal Finite partially ordered set and some of its properties R. N. Yadav1, S. K. Chakrabarti2*, I. S. Jha2 and U. P. Yadav1 1Department of Mathematics, M. M. A. M. Campus, Tribhuvan University, Biratnagar, Nepal 2Department of Physics, M. M. A. M. Campus, Tribhuvan University, Biratnagar, Nepal *E-mail: skc_2007@yahoo.com Article history: Received 21 July, 2015; Accepted 29 November, 2015 DOI: http://dx.doi.org/10.3126/bibechana.v13i0.13985 Abstract This paper focuses on some main properties of the finite partially ordered sets. These properties are furnished in the form of theorems. Here we have presented three such theorems. The first theorem is called as ‘duality theorem’. This fundamental theorem was first obtained by Greene. Few years later it was rediscovered and given an alternative proof by Fomin. The second theorem bestows the functionality property. The proof of this was also done by Greene. However, Gansner gave an alternative proof of the theorem taking advantage of a connection between poset and linear algebra. The proof of the third theorem is fully due to us. This theorem gives rise to a recursive computation of the shape. In the present paper we have discussed the first two properties through suitable illustrations only whereas a complete proof is furnished for the last one. ©RCOST: All rights reserved. Keywords: Poset; ferrers shape; duality theorem; functionality; recursive computation. 1. Introduction A set is a well-defined collection of objects called as elements [1]. An ordered set is a sequence of elements that is distinguished from the other sequences of the same element by the order of the elements. A partially ordered set (or poset) is a set in which a relation as ‘less than or equal to’ holds for some pairs of elements of the set but not for all. Formally, a poset is defined as an ordered pair P = (X, ≤), where X is called the ground set of P and ≤ is the partial order of P. An element u in a partially ordered set (X, ≤) is said to be an upper bound for a subset S of X if for every s  S, we have s ≤ u. Similarly, a lower bound for a subset S is an element l such that for every s  S, l ≤ s. If there are an upper bound and a lower bound for X, then the poset (X, ≤) is said to be finite. Here we bring together some main properties of finite posets in the form of theorems. In this spirit, we R.N. Yadav et al. / BIBECHANA 13 (2016) 132-136: RCOST p.133 (Online Publication: Dec., 2015) begin our presentation by stating Greene’s fundamental theorem that introduces the map P  (P). The next theorem asserts that the shape (p) grows as new maximal elements added to the poset P. The third theorem, representing a recursive computational property, is furnished with our proof of the same. 2. Properties 2.1. Theorem 1 Let P be a finite partially ordered set of cardinality n. A chain is a totally ordered subset of P. An antichain is a subset of P in which no two elements are comparable. According to Dilworth, the maximal size of an antichain in P is equal to the minimal number of chain into which P can be partitioned [2]. This has an easy ‘dual’ counterpart in which the words ‘chain’ and ‘antichain’ can be interchanged. Such duality has a beautiful and powerful common generalisation due to Greene. For k = 0, 1, 2, 3, ..., let ak (resp. ck) denotes the maximal cardinality of a union of k antichains (resp. chains) in P. Let k = ck – ck-1 and = ak – ak-1 for all k ≥ 1. Theorem : For any finite partially ordered set P the sequences  = (1, 2, …) and = ( , , …) are weakly decreasing and form conjugate partitions of the number n = [P]. For posets this is the fundamental theorem called as ‘duality theorem’. This Theorem was first obtained by Greene as a corollary of another result due to Greene and Kleitman [3, 4]. Few years later Fomin gave an alternative proof of it [5]. Other proofs appeared as well [6–8]. The duality theorem associates to every finite poset having Ferrers shape whose row lengths are 1, 2,  … and column lengths , , … . We have identified this shape with the partition  and denoted it by P(). (a) P (b) (P) Fig. 1 : Duality theorem. To illustrate, let us consider the poset P in Fig. 1. For this poset we have c0 = 0, c1 = 4, c2 = c3 = … = 6 f d e b c a R.N. Yadav et al. / BIBECHANA 13 (2016) 132-136: RCOST p.134 (Online Publication: Dec., 2015) implying  = (4, 2) while a0 = 0, a1 = 2, a2 = 4, a3 = 5, a4 = a5 = … = 6 imply that = (2, 2, 1, 1), a shape conjugate to . Various attempts have been made to generalise Theorem 1 to directed graphs [9–11]. The following ‘functionality’ result shows that the shape of a poset contains the shape of its arbitrary order ideal. 2.2. Theorem 2 Theorem : If p be a maximal (or minimal) element of a finite partially ordered set P, then (P – {p})  (P). For example, the poset P in Fig. 1 has maximal elements e and f. The shapes (P–{e}) and (P–{f}) are shown in Fig. 2; both are contained in (P). (a) (P – {e}) (b) (P – {f}) Fig. 2 : Theorem 2. In Theorem 2 the restriction for p  P to be an extremal element cannot be dropped. A counter-example is given in Fig. 3. Fig. 3 : A counter-example : (P – {p})  (P). Fig. 4 : A linear extension and the associated standard tableau. p 6 4 5 2 3 1 1 2 3 5 4 6 R.N. Yadav et al. / BIBECHANA 13 (2016) 132-136: RCOST p.135 (Online Publication: Dec., 2015) This theorem implies that any linear extension  : P [n] = {1, 2, 3, …, n} of P gives rise to a standard Young tableau T of shape (P) defined by the condition that the entries 1, 2, 3, …, k of T form [12] the shape ( [1, k]). As an example, let us consider the poset in Fig. 1 and its linear extension given by (a) = 1, (b) = 2, …, (f) = 6. The resulting standard tableau is given in Fig. 4. It is also Greene who deduced this theorem. However, Gansner gave an alternative proof of it by the connection of poset with linear algebra. A generalisation of the theorem to path families in acyclic directed graphs was also given by Gansner [13]. 2.3. Theorem 3 Let p1 p2 be the fall list of maximal elements in P. Then the shape  = (P) is uniquely determined by the shapes (P–{p1}), (P–{p2}), (P–{p3}), …, (P–{Pk}). Theorem : If (P – {p1}) = (P – {p2}) = (P – {p3}) = … = (P – {pk}) = , then  is obtained by adding a box into the kth row of . Theorem 3 represents a recursive computational property. We furnish below a proof of this Theorem. The proof is fully due to us. 3. Proof In order to prove Theorem 3 let us recall the lemma : if C = {C1, C2, C3, ..., Cl} and A = {A1, A2, A3, …, Ak} are the chain and antichain respectively, then C and A are orthogonal if and only if : (i) C is a maximal chain l-family, (ii) A is a maximal antichain k-family and (iii) the point (k, l) lies on the outer boundary of the shape (P). It will be convenient to assume that p1, p2, p3, …, pk is the complete list or minimal (rather than maximal) elements of P. The resulting statement is equivalent to Theorem 3 if we pass to the dual poset. Let us assume that (P – {p1}) = (P – {pk}) = . The shape (P) is obtained by adding a box to . Say, this box lies in row r and column s. We need to show that r = k. The number of elements covered by a maximal chain r-family decreases by 1 if any of the pi is removed from P. Hence, any maximal chain r-family in P covers all the pi, implying r  k. Let A = {A1, A2, A3, …} be a maximal antichain s-family in P and, furthermore, assume that A is of canonical form. Since the number of elements covered by such a family decreases if any of the pi is removed, we conclude that all the pi are covered by A and, therefore, contained in A1. Since any element of P is comparable to some of the pi, the antichain A1 may not contain any other elements. And its cardinality is equal to k. On the other hand, by the above lemma, A is orthogonal to any maximal chain r- family. Therefore, any antichain A (inducting A1) must contain at least r elements. Thus k  r and we are done. 4. Conclusion The correspondence P  (P) is intimately related to at least three areas of discrete mathematics : combinatorial optimisation, lattice theory and combinatorics of tableaux. The theorems enumerated here R.N. Yadav et al. / BIBECHANA 13 (2016) 132-136: RCOST p.136 (Online Publication: Dec., 2015) furnish some main properties of finite partially ordered sets. Theorem 3, which we have proved above from a poset-theoretic viewpoint, describes a simple recursive algorithm for computing the shapes λ(P') for all order ideals P' of a given finite poset P. Such ideals form a distributive lattice. References [1] H.S. Sharma and S.S. Seth, Modern Algebra, Ram Prasad and Sons, Agra, (1981. [2] R.P. Dilworth, Ann. Math., 102 (1956) 161. [3] C. Greene, J. Combin, Th. Ser., A 20 (1976) 69. [4] C. Greene and D.J. Kleitman, J. Combin. Th. Ser., A 20 (1976) 41. [5] S.V. Fomin, Soviet Math., D 19 (1978) 1510. [6] A. Frank, J. Combin. Th. Ser., B 29 (1980) 176. [7] S. Felsner, J. Combin. Th. Ser., B 57 (1993) 309. [8] K. Engel, Spencer Theory, Cambridge University Press, Cambridge, 1997. [9] N. Linial, J. Combin. Th. Ser., A 30 (1981) 331. [10] D.B. West, Graphs and Order, Reidel, Boston, 1985. [11] I.B.A. Hartman, F. Saleh and D. Hershkowitz, J. Graph Th., 18 (1994) 169. [12] R.P. Stanley, Enumerative Combinatories, Cambridge University Press, Cambridge, 1999. [13] E.R. Gansner, SIAM J. Algebra Disc. Methods, 2 (1981) 429.