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 ij; χ(Hn) = 2 for all n ≥ 3.
* Unimodular poset: A ranked poset is unimodular if, for some j, r0r1 ≤ ... ≤ rjrj+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) xy implies xXi and yXj, 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; Used for poset enumeration; 2004, We do not have a good way to actually generate those random individual posets.
* (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 < jn, 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].
@ 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 pageabbreviationsjournalscommentsother sitesacknowledgements
send feedback and suggestions to bombelli at olemiss.edu – modified 22 feb 2017