 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, yP, x < y, ∃ zP' 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, yL, 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 KP and LP 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 p1 < p2 implies r(p1) < r(p2), 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 pageabbreviationsjournalscommentsother sitesacknowledgements
send feedback and suggestions to bombelli at olemiss.edu – modified 29 aug 2016