K-Dimensional poset

[math]\displaystyle{ k }[/math]-Dimensional poset --- [math]\displaystyle{ k }[/math]-мерное чу-множество.

The order dimension [math]\displaystyle{ \dim(P) }[/math] of a poset [math]\displaystyle{ P = (V,\lt ) }[/math] is the smallest number of linear extensions [math]\displaystyle{ L_{1}, \ldots, L_{k} }[/math] of [math]\displaystyle{ P }[/math], [math]\displaystyle{ L_{i} = (V,\lt _{i}) }[/math], whose intersection is [math]\displaystyle{ P }[/math], i.e. [math]\displaystyle{ a \lt b }[/math] iff [math]\displaystyle{ a\lt _{i} b }[/math] for all [math]\displaystyle{ i = 1, \ldots, k }[/math]. A partial order [math]\displaystyle{ P }[/math] is [math]\displaystyle{ k }[/math]-dimensional poset if dim([math]\displaystyle{ P) \leq k }[/math].

See also

• n-Mesh.

The decision problem [math]\displaystyle{ DIM_{k} = \{P: \; \dim(P) \leq k\} }[/math] is NP-complete already for [math]\displaystyle{ k = 3 }[/math], whereas 2-dimensional posets can be recognized in a polynomial time.