A note on Dilworth’s embedding theorem
HTML articles powered by AMS MathViewer
- by William T. Trotter
- Proc. Amer. Math. Soc. 52 (1975), 33-39
- DOI: https://doi.org/10.1090/S0002-9939-1975-0373988-0
- PDF | 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 R. Kimble, Extremal problems in dimension theory for partially ordered sets, Ph. D. Thesis, M.I.T., Cambridge, Mass., 1973.
- 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 E. Szpilrajn, Sur l’extension de l’ordre partiel, Fund. Math. 16 (1930), 386-389.
- 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, J. Combinatorial Theor[ill] Ser. A (to a[ill][ill]ear).
- 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
Bibliographic Information
- © Copyright 1975 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 52 (1975), 33-39
- MSC: Primary 06A35
- DOI: https://doi.org/10.1090/S0002-9939-1975-0373988-0
- MathSciNet review: 0373988