A note on Dilworthâ€™s embedding theorem

Author:
William T. Trotter

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

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

- Ian Anderson,
*Perfect matchings of a graph*, J. Combinatorial Theory Ser. B**10**(1971), 183â€“186. MR**276105**, DOI https://doi.org/10.1016/0095-8956%2871%2990041-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 https://doi.org/10.1016/0012-365X%2873%2990025-3 - R. P. Dilworth,
*A decomposition theorem for partially ordered sets*, Ann. of Math. (2)**51**(1950), 161â€“166. MR**32578**, DOI https://doi.org/10.2307/1969503 - Ben Dushnik and E. W. Miller,
*Partially ordered sets*, Amer. J. Math.**63**(1941), 600â€“610. MR**4862**, DOI https://doi.org/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 https://doi.org/10.1016/0095-8956%2872%2990033-0
R. Kimble, - 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 https://doi.org/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, - William T. Trotter Jr.,
*Embedding finite posets in cubes*, Discrete Math.**12**(1975), 165â€“172. MR**369191**, DOI https://doi.org/10.1016/0012-365X%2875%2990031-X
---, - Helge Tverberg,
*On Dilworthâ€™s decomposition theorem for partially ordered sets*, J. Combinatorial Theory**3**(1967), 305â€“306. MR**214516**

*Extremal problems in dimension theory for partially ordered sets*, Ph. D. Thesis, M.I.T., Cambridge, Mass., 1973.

*Sur lâ€™extension de lâ€™ordre partiel*, Fund. Math.

**16**(1930), 386-389.

*A generalization of Hiraguchiâ€™s inequality for posets*, J. Combinatorial Theor[ill] Ser. A (to a[ill][ill]ear).

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC:
06A35

Retrieve articles in all journals with MSC: 06A35

Additional Information

Keywords:
Distributive lattice,
dimension of a partitially ordered set,
matching

Article copyright:
© Copyright 1975
American Mathematical Society