Recognition of prime posets and one of its applications

Khamis, Soheir 


The paper contains a recognition algorithmic method for deciding whether a given poset, P, is prime. The algorithm is designed to determine whether there exists a proper P-autonomous set including specified two distinct elements of P. The steps are repeated for all ordered pairs of distinct elements of P, if it is prime, in a polynomial time. As an application of this test, the author counted the number of unlabeled prime posets regarding heights up to 13 elements. The height counting algorithm depends on: (1) Create the colexecographic list of all strictly upper triangular matrices satisfying the bucket from; (2) Apply the given test to choose those corresponding to prime posets; and (3) Enumerate the required number regarding height by summing the weights of accepted matrices, that are also computed in the algorithm. The algorithm added to height counting field, the original numbers of unlabeled 13-element prime posets of height k; k · 13, and verified the previously known numbers of unlabeled n-element prime posets of height k; 1 · k · n · 12, that have been introduced in [11].

Other data

Keywords Counting, enumeration, partially ordered sets, finite poset, unlabeled, prime, height, and algorithm
Issue Date 2006

Recommend this item

CORE Recommender

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