Enumeration and Properties of Partially Ordered Sets| Enumeration and Properties of Partially Ordered Sets |
In General 
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 n−n−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 page
– abbreviations
– journals – comments
– other sites – acknowledgements
send feedback and suggestions to bombelli at olemiss.edu – modified 12 jun 2020