Inequalities for the number of monotonic functions of partial orders

✍ Scribed by Jacqueline W Daykin

• Publisher: Elsevier Science
• Year: 1986
• Tongue: English
• Weight: 682 KB
• Volume: 61
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(86)90026-9

✦ Synopsis

Let P be a finite poset and let x, y e P. Let C be a finite chain. Define NS(i, j) to be the number of strict order-preserving maps to: P--~C satisfying to(x)=i and to(y)=j. Various inequalities are proved, commencing with Theorem 2: If r, s, t, u, v, w are non-negative integers then NS(r, u + v + w)NS(r + s + t, u) <-NS(r + s, u + w)NS(r + t, u + v). The case v = w = 0 is a theorem of Daykin, Daykin and Paterson, which is an analogue of a theorem of Stanley for linear extensions.

a,ar+s+ t <-ar+sar+ ~ for non-negative integers r, s, t.

We will adopt the following notation. Let 7/+ denote the non-negative integers. If xl, . . . , Xk is a fixed subset in P and t t, ..., tk ~ 7/+, then define N° (tt, . . . , tk) to be the number of order-preserving maps too: p_._> C such that toO(Xh)-th for 1 <~ h ~< k. Similarly define NS (tt,..., tk) , NI(tt,..., tk) and NL (tl,..., tk) for the other classes g2, A ~ and A respectively. Further,