Partially
Ordered Sets| Partially
Ordered Sets |
In General > s.a. set of posets [including
operations and generalizations], types of posets.
$ Def: A set with a partial
order (reflexive, transitive, antisymmetric) relation.
* 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.
Enumeration
* Results: The number of
labelled, unlabelled, and connected n-element posets, for the
first
values
of n is
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| n| |
1 | 3 | 19 | 219 | 4231 | 130,023 | |||||||
| n| |
1 | 2 | 5 | 16 | 63 | 318 | 2,045 | 16,999 | 183,231 | 2,567,284 | 46,749,427 | 1,104,891,746 | 33,823,827,452 |
| n| |
1 | 1 | 3 | 10 | 44 | 238 |
Exact numbers are known up to |unlab,
14|
and |lab,
16|,
as of 2000 (they are not close to the values given
by
the n → 
formula,
because 16 is still too small).
* Examples: 2 = {
,
},
3 = {, , 
, 
, 
}.
* Asymptotic: For n → ,
the number of labelled posets is asymptotic to |n|
C 2n^2/4+3n/2 en n–n–1,
where C 
0.8059,
for n even, and something quite similar for n odd.
@ References: Kleitman & Rothschild TAMS(75);
Dhar PJM(80)-mr;
Culberson & Rawlins Ord(90);
Erné & Stege
Ord(91);
Chaunier & Lygeros Ord(92)
[n = 13]; Heitzig & Reinhold
Ord(00)
[n = 14]; Brinkmann & McKay Ord(02)
[n = 15, 16].
Poset Functions > s.a. causal
sets; dimension.
* Dimension: The smallest number of linear orders whose intersection
is
the poset.
* 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: 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].
Topologies on Posets > s.a. topology.
* Idea: Finite quasiordered structures correspond to finite topological
spaces.
@ References: in Birkhoff 67; Bell & Ginsburg Ord(87);
Khalimsky et
al
T&A(90)
[finite posets]; Erné & Stege
Ord(91).
Other Structures > s.a. connection and curvature.
* Lattice: From lattices
with the given poset of meet-irreducible elements [@ Seselja & Tepavcevic
Ord(00)].
* Hypergraph: The hypergraph
of incomparable pairs [@ Felsner & Trotter
Ord(00)].
* Ranking: A map r: P → N such
that p1 < p2 implies
r(p1) < r(p2),
equivalent
to a linear extension by P N.
* Incidence algebra: Given
any
locally finite poset P, the incidence
algebra I(P) (over C, say) is the vector space
of functions f : S(P) → C, where S(P)
is the set of
intervals [x, y] 
Ø,
made into an
associative algebra by the multiplication (convolution) fg([x, y]):=
z in
[x,y] f([x, z]) g([z, y]);
The identity
is 
([x, y])
= (x, y).
@ References: Marlow IJTP(80)
[generalized topology]; 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];
Sorkin MPLA(03)m.CO-in
[incidence
algebras]; Bosi & Herden Ord(05)
[re refinements by linear orders]; Güldürdek & Richmond Ord(05)
[preorders
and pseudodistances]; Roberts et al a0707,
a0802 [bundles].
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; Stanley 86; Davey & Priestley 90; Neggers & Kim
98 [II]; Stanley 99; Trotter 02 [especially dimension]; Schröder 03.
@ Algebraic approach: Romanowska & Smith 85; Leutola & Nieminen
AU(83).
@ Fixed-point theorems: Baclawski & Björner AiM(79);
Nieto & Rodríguez-López Ord(05)
[and ode's].
@ Phase transitions: Dhar JMP(78);
Kleitman & Rothschild PhyA(79);
Pittel &. Tungol RSA(01).
@ 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); > s.a. quantum
computing [search
algorithm].
> Online resources: see Wikipedia
page.
main page – abbreviations – journals – comments – other
sites – acknowledgements
send feedback and suggestions to bombelli at olemiss.edu – modified 20
aug
2009