Partially
Ordered Sets |

**In General** > s.a. poset enumeration; set of posets [including
operations and generalizations]; types of posets [including applications].

* __Idea__: A partial order on a set is a relation specifying which elements precede which others, and which pairs are incomparable without being the same.

$ __Def__: A pair (*P*,<) of
a set *P* and a partial order (reflexive, transitive, antisymmetric) relation <.

* __In category theory terms__:

* __Remark__: Poset theory
is a first-order language, with a binary relation <,
variables *x* *y* *z* ..., = ∃ ∀, and logical connectors.

* __History__: Originated
in the XIX century (Boole, Peirce, Schröder,
Dedekind); Developed from the 1930s with G Birkhoff.

**Subsets of a Poset** > s.a. Chain.

* __Antichain__: A subset
in which no two elements are related.

* __Interval__:
A subset of a poset defined by [*x*,* y*]:=
{*z* | *x* < *z* < *y*}.

* __Dense subset__: *P'* ⊂ *P*
is dense if for all *x*, *y* ∈ *P*, *x* < *y*,
∃ *z* ∈ *P'*
with *x* < *z* < *y*.

* __Stem__: A subset which
contains its own past.

* __Autonomous subset__: A subset *A* of* P* such that every element of *P* not in *A* is either less than or greater than or incomparable to all elements of *A*; The empty set, the singletons from *P* and the set *P* are autonomous subsets and are called trivial.

**Poset Functions** > s.a. causal
sets; dimension.

* __Dimension__: The smallest
number of linear orders whose intersection is
the poset; There is also a notion of *k*-dimension, for *k* > 1 an integer.

* __Bump number__: *b*(*P*):=
min {*b*(*L*,* P*) | *L* linear extension
of *P*, * b*(*L*,* P*) = number of consecutive *x*,
*y* ∈ *L*, *x *<_{P}* y*}.

* __Crossing number__: For
a set *f* of functions, *χ*(*f*):= max number of
times 2 elements of *f* intersect; Then, *χ*(*P*):=
min{*χ*(*f*) | *f* a
function order representing *P*}; __Properties__: *χ*(*P*)
= 0 iff dim(*P*) = 1; *χ*(*P*)
= 1 iff dim(*P*) = 2; if dim(*P*) = *n*, then *χ*(*P*) ≤ *n*–1;
If *P* is a circle order, then *χ*(*P*) ≤ 2.

* __Height__: The length of the longest (maximal) chain.

* __Width__:
The number of elements in the largest (maximal) antichain.

* __Linear discrepancy__: The
smallest integer *k* such that there is a linear extension *L* of *P* such
that if *x* and *y* are
incomparable in *P*, then |*h*(*x*)–*h*(*y*)| ≤ *k*,
where *h*(*x*) is the height of *x* in *L*; In other words, the largest difference in
labels for an unrelated pair in a minimizing labeling.

@ __Dimension__: Novák CzJM(63) [*k*-dimension]; Kelly & Trotter in(82);
Alon & Scheinerman Ord(88);
El-Zahar & Sauer Ord(88)
[2D]; Barmak & Minian Ord(07)
[2D, topological point of view]; Foldes & Szigeti Ord(07)
[half-space approach].

@ __Other dimensions__: Brightwell & Scheinerman Ord(92) [fractional];
Brightwell & Franciosa
Ord(96) [Boolean].

@ __Linear discrepancy__: Fishburn et al Ord(01);
Tanenbaum et al Ord(01);
Howard et al Ord(07)
[linear discrepancy = 2].

@ __Other invariants__: Hofmann & Keimel 72 [character]; Behrendt AC(87)
[complexity].

**Posets and Topological Spaces** > s.a. morse
theory; topology.

* __Idea__: One may obtain a topological space from a poset in different ways, (1) Using the
fact that finite quasiordered structures correspond to finite topological
spaces; (2) Constructing the simplicial complex Δ_{P} of
its non-empty chains; (3)+(4) Constructing one of two other simplicial complexes
*K*_{P} and *L*_{P} associated
with the relation <.

@ __References__: Alexandroff MS(37); in Birkhoff 67; Bell & Ginsburg Ord(87);
Khalimsky et al T&A(90)
[finite posets]; Erné & Stege
Ord(91);
Minian Ord(10)m.CO/07; Barmak JCTA(11) [sufficient conditions for a map between two posets to be a homotopy equivalence at the level of complexes].

**Other Structures** > s.a. connection and curvature; Incidence Algebra.

* __Covering relation__: The relation between elements *x* and *y* such that *x* < *y* but there is no other element between them; > s.a. Wikipedia page.

* __Lattice__: From lattices
with the given poset of meet-irreducible elements [@ Šešelja & Tepavčević Ord(00)].

* __Hypergraph__: The hypergraph
of incomparable pairs [@ Felsner & Trotter
Ord(00)].

* __Ranking__: A map *r*: *P* → \(\mathbb N\) such
that *p*_{1} < *p*_{2} implies
*r*(*p*_{1}) < *r*(*p*_{2}),
equivalent to a linear extension by *P* ⊂ \(\mathbb N\).

@ __General references__: Hozo ElJC(95)
[Lie algebra]; Wicks Ord(95)
[non-standard analysis, and completion]; Ercolessi et al RVMP(98)qa/96 [as representations of non-commutative algebras],
qa/96 [K-theory];
Bosi & Herden Ord(05) [re refinements by linear orders];
Güldürdek & Richmond Ord(05) [preorders and pseudodistances];
Roberts et al AiM(09)-a0707,
a0802 [bundles];
Civan Ord(13) [upper-maximal graphs of posets].

@ __Topological ordered spaces__: Marlow IJTP(80) [generalized topology];
Minguzzi JPCS(13) [and quantum spacetime];
Lindenhovius a1405 [Grothendieck topologies].

@ __Partially ordered measure spaces__: Arveson AM(74);
Bollobás & Brightwell TAMS(91)*;
Cooper & Russell a1102 [and thermodynamics];
Bombelli et al a1212 [and spacetime structure].

**References** > s.a. axiom of choice [Kuratowski lemma];
group types; topology.

@ __General__: Dushnik & Miller AJM(41);
Rota ZW(64);
Aigner DM(81) [complexity];
Rival ed-82;
Fishburn 85; Fraïssé 86;
Neggers & Kim 98
[II, amazon];
Stanley 01; Davey & Priestley 02;
Trotter 02 [especially dimension];
Schröder 03;
Stanley 11;
Rudeanu 12 [and set theory];
in Vermani & Vermani 12 [discrete mathematics].

@ __Algebraic approach__: Romanowska & Smith 85;
Leutola & Nieminen AU(83).

@ __Fixed-point theory__: Baclawski & Björner AiM(79);
Nieto & Rodríguez-López Ord(05) [and odes];
Carl & Heikkilä 11.

@ __Computer generation__: Henson et al a1504
[Markov-Chain-Monte-Carlo algorithm]; > s.a. quantum computing [search algorithm].

@ __Related topics__: Wagner Ord(90),
Pikhurko Ord(99)
[decomposition]; Kratsch & Rampon Ord(94),
Schröder Ord(01), Ord(02)
[reconstruction], Ord(04) [neighborhood deck];
Haviar & Lihová Ord(05)
[variety of posets]; Lehtonen EJC(08).

> __Online resources__: see MathWorld page; nLab page; Wikipedia page.

main page – abbreviations – journals – comments – other
sites – acknowledgements

send feedback and suggestions to bombelli at olemiss.edu – modified 29 aug 2016