Partially Ordered Sets| 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 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];
Kong & Zheng a2011 [categories].
@ 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];
Kozieł & Sulkowska a1810 [random labeled posets];
> s.a. causal sets; 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 30 dec 2020