PRIMALITY TESTING AND COUNTING THE NUMBER OF UNLABELED PRIME POSETS ON THIRTEEN ELEMENTS

S. M. Khamis ; Khamis, Soheir 


Abstract


This paper gives a new polynomial algorithm for testing whether or not a given poset, P , is prime. The basic idea of the given algorithm depends on finding a proper autonomous set of elements of P. The algorithm decides that P is prime if each pair of elements of P does not belong to a proper autonomous set. Via this test, unlabeled prime posets on n elements are counted. The strategy of the suggested counting algorithm is: (1) Create an upper triangular matrix satisfying the bucket form; (2) Apply the primality test to accept a constructed matrix if it corresponds to a prime poset; and (3) Compute the weight of the accepted matrix of enumeration. The three steps are repeated to obtain the sum of the weights of all upper triangular matrices with bucket form that correspond to prime posets. In constructing these matrices, we follow a colexecographic (colex.) order w.r.t. rows. As a result, the previously known numbers of such posets on n  12 recorded in [3] 1997 are verified. A new number on n = 13 is computed.


Other data

Keywords Counting, enumerating, partially ordered sets, finite poset, unlabeled, prime, and algorithm.
Issue Date 1997
Conference The International Conference on Mathematics Trends and Developments, Egyptian Mathematical Society 
URI http://research.asu.edu.eg/123456789/1129


Recommend this item

CORE Recommender
5
Views


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