Exact Counting of Unlabeled Rigid Interval Posets Regarding or Disregarding Height

Khamis S. 


Abstract


In this paper, the author gives the exact counting of unlabeled rigid interval posets regarding or disregarding the height by using generating functions. The counting technique follows those introduced in El-Zahar (1989), Hanlon (Trans Amer Math Soc 272:383-426, 1982), Khamis (Discrete Math 275:165-175, 2004). The main advantage of the suggested technique is that a very simple recursive construction of unlabeled rigid interval poset from small ones leads to derive the given generating function for unlabeled rigid interval posets whose coefficients can be easily computed. Moreover, it is proven that the sets of n-element unlabeled rigid interval posets and upper triangular 0-1 matrices with n ones and no zero rows or columns are in one-to-one correspondence. In addition, n-element unlabeled interval posets are counted for n ≥ 1, using the given generating function for rigid ones. Upper and lower bounds for the number of n-element unlabeled rigid interval posets are given. Also, an asymptotic estimate for the required numbers is obtained. Numerical results for unlabeled interval posets coincide with those given in El-Zahar (1989) and Khamis (Discrete Math 275:165-175, 2004). The exact numbers of n-element unlabeled rigid and general interval posets with and without height k are included, for 1 ≤ k ≤ n ≤ 15. © 2011 Springer Science+Business Media B.V.


Other data

Keywords Counting • Poset • Interval poset • Rigid • Height • Generating function •Upper bound • Lower bound • Asymptotic estimate
Issue Date 1-Oct-2012
Journal Order 
URI http://research.asu.edu.eg/123456789/1119
DOI 3
https://api.elsevier.com/content/abstract/scopus_id/84867098138
443
29
10.1007/s11083-011-9213-5


File Description SizeFormat 
10.1007%2Fs11083-011-9213-5.pdf388.01 kBAdobe PDFView/Open
Recommend this item

CORE Recommender
2
Citations

3
Views

1
Downloads


Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.