New results from an algorithm for counting posets

DOI10.1007/BF00383201MaRDI QIDQ1177709zbMATH OpenFDO

Authors J. Culberson, Gregory J. E. Rawlins

Publication date 26 June 1992

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF00383201

zbMATH Keywords

algorithmcomputer enumeration of partial ordersnumber of natural partial ordersnumber of partial ordersposet of posetsrecurrences

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Software, source code, etc. for problems pertaining to ordered structures (06-04) Combinatorics of partially ordered sets (06A07) Combinatorics in computer science (68R05)

Review text

The authors describe an algorithm used to generate a computer enumeration of the number of unlabeled posets on \(n\) elements and \(r\) relations, for \(0\leq n\leq 11\) and \(0\leq r\leq{n-1 \choose 2}\). They report on a new technique for computing based on the partial orders ordered by containment. They verified results of Möhring for \(n\leq 9\), claim additional 35 posets for \(n=10\) and give results for \(n=11\). They also extend the work of Avann from \(n=5\) to \(n=9\) in counting the number of natural partial orders. Further they discovered and verified the existence of some interesting recurrences that hold for the number of partial orders and for the number of natural partial orders.

Recommendations

• The number of unlabeled orders on fourteen elements
• scientific article; zbMATH DE number 1156638
• The number of nonisomorphic posets having 12 elements
• On recursion relations in the problem of enumeration of posets

Cites work

• A Machine Representation of Finite T ₀ Topologies
• Asymptotic Enumeration of Partial Orders on a Finite Set
• Enumeration of Posets Generated by Disjoint Unions and Ordinal Sums
• scientific article; zbMATH DE number 3841924 (Why is no real title available?)
• scientific article; zbMATH DE number 6157245 (Why is no real title available?)
• Note on Finite Topological Spaces
• On the cardinalities of finite topologies and the number of antichains in partially ordered sets
• On the computer enumeration of finite topologies
• Orderly algorithms for generating restricted classes of graphs
• Producing posets
• The lattice of natural partial orders
• The number of partially ordered sets with more points than incomparable pairs

Cited in

(19)

• Counting finite posets and topologies
• The number of partially ordered sets with more points than incomparable pairs
• The number of orders with thirteen elements
• The number of nonisomorphic posets having 12 elements
• On the poset of all posets on n elements
• Height counting of unlabeled interval and \(N\)-free posets.
• On recursion relations in the problem of enumeration of posets
• A framework for the systematic determination of the posets on n points with at least 2ⁿ downsets
• Recognition of prime posets and one of its applications
• On numerical counting of prime, UPO, and the general type of posets according to heights
• scientific article; zbMATH DE number 6375591 (Why is no real title available?)
• scientific article; zbMATH DE number 25381 (Why is no real title available?)
• scientific article; zbMATH DE number 1156638 (Why is no real title available?)
• scientific article; zbMATH DE number 2052742 (Why is no real title available?)
• An exact enumeration of the unlabeled disconnected posets
• On recurrence relation in the problem of enumeration of finite posets
• Efficiently counting representations of finite posets
• Partition coefficients of acyclic graphs
• Posets on up to 16 points

This page was built for publication: New results from an algorithm for counting posets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1177709)