Types and Realizations of Posets| Types and Realizations of Posets |
In General > s.a. Hasse Diagram.
* Well founded: A poset P
is well founded if no infinite decreasing sequences occur in P.
* Well partially ordered: A well
founded poset containing no infinite antichains.
* Locally finite: A poset such that
every interval in it is finite.
* Prime poset: One such that all
its autonomous subsets are trivial.
@ General references: Bosi et al Ord(01) [interval orders, numerical representation];
Hubička & Nešetřil EJC(05) [universal partial order].
@ Types: Ng Ord(05) [linear discrepancy n−2];
Malicki & Rutkowski Ord(05) [well partially ordered];
Pouzet & Zaguia Ord(09),
Boudabbous et al Ord(10) [prime];
Dzhafarov Ord(11) [infinite saturated orders];
Bonanzinga & Matveev Ord(11) [thin posets];
Pouzet et al EJC(14)
[posets embeddable in a product of finitely many scattered chains];
> s.a. Relations [k-homogeneous].
Sphere Order > s.a. 2D geometries [Lorentzian].
* Idea: A poset realization
defined by sphere containment in Euclidean space.
* Result: Every circle order
has a normal representation, ∩i
int(Pi) ≠ 0.
* Result: For all n
> 2, ∃ P with dim(P) = n which is not a
circle order; Example: [2] × [3] × \(\mathbb N\) is not,
but perhaps all 3D finite posets are; Some infinite posets are not sphere orders in any dimension!
[@ Fon-Der-Flaass Ord(93)].
@ References: Fishburn Ord(88);
Scheinerman & Wierman Ord(88);
Hurlbert Ord(88);
Sidney et al Ord(88);
Brightwell & Winkler Ord(89);
Lin Ord(91),
Scheinerman Ord(92) [circle orders];
Meyer Ord(93);
Scheinerman & Tanenbaum Ord(97);
Fishburn & Trotter Ord(98) [survey];
Vatandoost & Bahrampour JMP(11) [and spacetime].
Other Realizations
* Path order: A representation
by finite oriented paths ordered by the existence of homomorphism between them;
Any countable (finite or infinite) partially ordered set can be realized this way.
* Function order: A proper set of
functions fi: [0,1] →
\(\mathbb R\) (two functions intersect, and cross, only a finite no of times,
but not at 0 or 1), with pi
< pj iff
fi(x)
< fj(x) for all
x ∈ [0,1]; Every poset can be represented as a function order.
@ References:
Sydney, Sydney & Urrutia Ord(88) [function orders];
Hubička & Nešetřil Ord(04),
Ord(05) [path orders];
Laison Ord(04)
[(n, i, f)-tube orders];
Berman & Blok Ord(06) [as algebras].
Special Posets
> s.a. set theory [directed set]; lattices.
* Discrete poset: One in which no two elements are comparable.
* Binomial poset: It is
locally finite; All maximal chains between two points have the same length;
Any two n-intervals contain the same number of maximal chains.
* Linear order:
Ln = The totally
ordered n-element poset; They are all 1-dimensional.
* Standard n-dimensional
poset: Hn = (u1,
..., un, v1,
..., vn);
ui < vj
for i ≠ j; χ(Hn)
= 2 for all n ≥ 3.
* Unimodular poset: A ranked poset
is unimodular if, for some j, r0
≤ r1 ≤ ...
≤ rj
≥ rj+1 ≥ ...
≥ rn,
with rk
the number of elements of rank k.
* Sperner poset: A ranked poset
which has a maximum antichain all of whose elements have the same rank.
* Spectral poset: One which is
order isomorphic to (Spec(R), ⊆) where Spec(R) is the
set of prime ideals of some commutative ring with identity R.
* Multipartite poset: A poset
P = (X, ≤) is m-partite if X has a
partition X = X1 ∩
... ∩ Xm such that
(1) each Xi forms an
antichain in P, and (2) x ≤ y implies x
∈ Xi and y
∈ Xj, where i
< j.
* Result: (Schnyder's Theorem)
The incidence poset of a graph G has dimension at most three if and only if G is planar;
> s.a. Wikipedia page.
@ Completely regular:
Künzi Ord(90).
@ Boolean, Distributive, Modular:
Chajda & Rachunek Ord(89);
Niederle Ord(95).
@ Planar: Scheinerman pr(90);
Hashemi et al Ord(97);
Barrera-Cruz & Haxell Ord(11) [Schnyder's theorem].
@ Other: Behrendt AC(90) [homogeneous];
Hanna & McMaster Ord(00) [splittability];
Bezrukov et al JCTA(04) [Macaulay posets];
Belaid & Echi T&A(04) [spectral];
Waphare & Joshi Ord(05) [uniquely complemented];
Agnarsson DM(08) [multipartite posets, dimension];
Kwaśniewski a0901,
a0903 [graded posets, zeta matrix];
Conflitti DM(09) [fences and crowns, Whitney numbers of order ideals];
Kukieła Ord(09) [reversible and bijectively related];
Streib & Trotter EJC(14) [posets with planar cover graphs];
Trotter & Wang Ord(14) [incidence posets of graphs, cover graphs of posets].
Random Posets > s.a. Relation.
* (i) Uniform random orders:
As n → ∞, most n-element orders have 3
levels; This is used for poset enumeration; 2004, We do not have a good way
to generate those random individual posets; 2015, Algorithm for generating uniform random orders.
* (ii) Random k-dimensional orders:
[Winkler Ord(85)]
Pk(n)
is the intersection of k linear orders obtained from
random permutations of the n labels, and the result
is a k-dimensional order; The height is ~ C
n1/k and the width
~ C' n1−1/k;
A variation consists in sprinkling points in Minkowski space, although there
are finite posets which cannot be embedded in flat spacetime in any dimension.
* (iii) Random graph orders:
(a.k.a. transitive percolation) Given any p ∈ [0,1],
for every pair 0 < i < j ≤ n, draw
a graph edge between ai and
aj with probability p
and interpret it as ai
< aj, and take the
transitive closure of the resulting relation; On average the poset will look
like a series of "blobs" connected by posts which are
related to every other element (the fraction of posts is
~ exp{−π2/3p} as n → ∞)
[@ Alon et al AAP(94)]; Can be generalized to classical
growth models for causal sets, the only generalization that satisfies "general
covariance" and "Bell causality" [@ Rideout & Sorkin].
* Results: For n → ∞,
every first-order property holds either in nearly all unlabelled 2D orders, or hardly any.
@ Uniform random orders: Compton I&C(88) [0-1 laws for first-order logic]; Henson et al a1504 [algorithm].
@ Random k-dimensional orders:
Winkler Ord(85),
Ord(85),
Ord(89) [general];
Winkler Ord(90) [2D];
Spencer Ord(90) [2D, first-order properties];
Bollobás & Brightwell AAP(92) [height];
Brightwell Ord(92) [width and number of linear extensions].
@ Random graph orders: Albert & Frieze Ord(89) [height, width, dimension, etc];
Bollobás & Brightwell TAMS(91)*;
Luczak Ord(91) [first-order properties];
Bollobás & Brightwell MathSci(95) [width];
Kim & Pittel JCTB(00) [interpost distance distribution];
Bombelli et al a0809 [finite, expected number of posts].
Examples and Applications
> s.a. Clustering; connection;
Filters; logic; topological
spaces; Well Ordering.
* On the set of partitions of an
integer m: A partition P1
precedes P2 if the elements of
P2 can be decomposed to give
those of P1; For m = 5,
(2,2,1) < (3,2).
* In differential geometry:
Can be used to sample Lorentzian manifolds and define distances between them.
* In graph theory: The
set of acyclic orientations of a connected graph with a given sink has
a natural poset structure.
* In quantum gravity:
The poset could be either spacetime, with causality as a partial ordering,
or space; > see causal sets.
@ Examples: Ehrenborg & Slone Ord(09) [acyclic orientations of a graph];
Endo et al T&A(10) [knots and links].
@ In physics:
Borchers & Sen CMP(90) [for physicists],
CMP(99);
Bombelli JMP(00)gq [on Lorentzian manifolds];
Baumgartner JPA(02)mp/01 [subsystems];
Coecke qp/02 [probability];
Sen 10 [causality, measurement and discrete vs differentiable structures].
main page
– abbreviations
– journals – comments
– other sites – acknowledgements
send feedback and suggestions to bombelli at olemiss.edu – modified 12 jun 2020