Enumeration and Properties of Partially Ordered Sets  

In General blue bullet up to posets.
* Symbols: We denote by \(\cal L\)n the set of labelled n-element posets, by \(\cal P\)n the set of unlabelled ones, and by \(\cal C\)n the set of connected ones.
* Status: As of 2000, exact numbers are known up to |\(\cal P\)14| = 1.338.193.159.771 and |\(\cal L\)16| (their values are not close to those given by the n → ∞ formula, because 16 is still too small); By 2012, numbers up to |\(\cal P\)16| and |\(\cal L\)18| were known (see the lists below).
* Results: The number of labelled, unlabelled, and connected n-element posets, for the first values of n is

n |\(\cal L\)n| |\(\cal P\)n| |\(\cal C\)n|
1 1 1 1
2 3 2 1
3 19 5 3
4 219 16 10
5 4231 63 44
6 130,023 318 238
7 6,129,859 2,045 1,650
8 431,723,379 16,999 14,512
9 44,511,042,511 183,231 163,341
10 6,611,065,248,783 2,567,284 2,360,719
11 1,396,281,677,105,899 46,749,427 43,944,974
12 414,864,951,055,853,499 1,104,891,746 1,055,019,099
13 171,850,728,381,587,059,351 33,823,827,452 32,664,984,238
14 98,484,324,257,128,207,032,183 1,338,193,159,771 1,303,143,553,205
15 77,567,171,020,440,688,353,049,939 68,275,077,901,156 66,900,392,672,168
16 83,480,529,785,490,157,813,844,256,579 4,483,130,665,195,087  4,413,439,778,321,689
17 122,152,541,250,295,322,862,941,281,269,151    
18 241,939,392,597,201,176,602,897,820,148,085,023    

* Examples: The first few sets, for n up to 3, are \(\cal P\)1 = {\(\bullet\),}, \(\cal P\)2 = {\(\bullet\,\bullet\), }, \(\cal P\)3 = {\(\bullet\bullet\bullet\), \(\bullet\) , , , }, while \(\cal C\)1 = {\(\bullet\)}, \(\cal C\)2 = {}, \(\cal C\)3 = {, , }.
@ General references: Culberson & Rawlins Ord(90) [up to n = 11]; Erné & Stege Ord(91) [up to n = 14]; Chaunier & Lygeros Ord(92) [n = 13]; Heitzig & Reinhold Ord(00), Lygeros & Zimmermann www(00) [n = 14]; Brinkmann & McKay Ord(02) [n = 15, 16], and McKay site copy.
@ Special types of posets: Lewis & Zhang JCTA(13)-a1106 [(3+1)-avoiding posets]; Stanley PAMS(74) [posets generated by disjoint unions and ordinal sums].
> Online resources: see The Online Encyclopedia of Integer Sequences (OEIS) site; Chapel Hill Poset Atlas site.

Asymptotic Properties
* Asymptotic numbers: For n → ∞, the number of labelled or unlabelled posets on n elements goes like 2n^2/4; More precisely, the asymptotic value for the number of labelled posets in the case of even n is

|\(\cal P\)n| ~ C 2n^2/4+3n/2 en nn−1,   where   C ≅ 0.8059,

and something quite similar for n odd.
* Asymptotic structure: As n → ∞, the fraction of posets that are 3-layered, with n/2 elements in the middle layer and n/4 elements in the bottom and top layers, each one linked to half of the middle-layer elements, tends to 1.
@ General references: Kleitman & Rothschild TAMS(75); Dhar PJM(80)-mr; Henson et al a1504 [onset of the Kleitman-Rothschild 3-layer structure].
@ Phase transitions: Dhar JMP(78); Kleitman & Rothschild PhyA(79); Pittel & Tungol RSA(01).


main pageabbreviationsjournalscommentsother sitesacknowledgements
send feedback and suggestions to bombelli at olemiss.edu – modified 12 jun 2020