A note on Dilworth’s embedding theorem

Trotter, William T.

doi:10.1090/S0002-9939-1975-0373988-0

A note on Dilworth’s embedding theorem
HTML articles powered by AMS MathViewer

by William T. Trotter PDF

Proc. Amer. Math. Soc. 52 (1975), 33-39 Request permission

Abstract:

The dimension of a poset $X$ is the smallest positive integer $t$ for which there exists an embedding of $X$ in the cartesian product of $t$ chains. R. P. Dilworth proved that the dimension of a distributive lattice $L = {\underline 2 ^X}$ is the width of $X$. In this paper we derive an analogous result for embedding distributive lattices in the cartesian product of chains of bounded length. We prove that for each $k \geqslant 2$, the smallest positive integer $t$ for which the distributive lattice $L = {\underline 2 ^X}$ can be embedded in the cartesian product of $t$ chains each of length $k$ equals the smallest positive integer $t$ for which there exists a partition $X = {C_1} \cup {C_2} \cup \cdots \cup {C_t}$ where each ${C_i}$ is a i a chain of at most $k - 1$ points.

References

Ian Anderson, Perfect matchings of a graph, J. Combinatorial Theory Ser. B 10 (1971), 183–186. MR 276105, DOI 10.1016/0095-8956(71)90041-4
Garrett Birkhoff, Lattice theory, 3rd ed., American Mathematical Society Colloquium Publications, Vol. XXV, American Mathematical Society, Providence, R.I., 1967. MR 0227053
Kenneth P. Bogart and William T. Trotter Jr., Maximal dimensional partially ordered sets. II. Characterization of $2n$-element posets with dimension $n$, Discrete Math. 5 (1973), 33–43. MR 318014, DOI 10.1016/0012-365X(73)90025-3
R. P. Dilworth, A decomposition theorem for partially ordered sets, Ann. of Math. (2) 51 (1950), 161–166. MR 32578, DOI 10.2307/1969503
Ben Dushnik and E. W. Miller, Partially ordered sets, Amer. J. Math. 63 (1941), 600–610. MR 4862, DOI 10.2307/2371374
Tosio Hiraguti, On the dimension of orders, Sci. Rep. Kanazawa Univ. 4 (1955), no. 1, 1–20. MR 77500
G. O. H. Katona, A generalization of some generalizations of Sperner’s theorem, J. Combinatorial Theory Ser. B 12 (1972), 72–81. MR 285402, DOI 10.1016/0095-8956(72)90033-0

Extremal problems in dimension theory for partially ordered sets

Oystein Ore, Theory of graphs, American Mathematical Society Colloquium Publications, Vol. XXXVIII, American Mathematical Society, Providence, R.I., 1962. MR 0150753
Micha A. Perles, A proof of Dilworth’s decomposition theorem for partially ordered sets, Israel J. Math. 1 (1963), 105–107. MR 168496, DOI 10.1007/BF02759805
Gian-Carlo Rota and L. H. Harper, Matching theory, an introduction, Advances in Probability and Related Topics, Vol. 1, Dekker, New York, 1971, pp. 169–215. MR 0282855

Sur l’extension de l’ordre partiel

16

William T. Trotter Jr., Embedding finite posets in cubes, Discrete Math. 12 (1975), 165–172. MR 369191, DOI 10.1016/0012-365X(75)90031-X

A generalization of Hiraguchi’s inequality for posets

Helge Tverberg, On Dilworth’s decomposition theorem for partially ordered sets, J. Combinatorial Theory 3 (1967), 305–306. MR 214516, DOI 10.1016/S0021-9800(67)80079-6