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
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