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

Abstract | References | Similar Articles | Additional Information

Abstract: The dimension of a poset is the smallest positive integer for which there exists an embedding of in the cartesian product of chains. R. P. Dilworth proved that the dimension of a distributive lattice is the width of . 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 , the smallest positive integer for which the distributive lattice can be embedded in the cartesian product of chains each of length equals the smallest positive integer for which there exists a partition where each is a i a chain of at most points.

**[1]**Ian Anderson,*Perfect matchings of a graph*, J. Combinatorial Theory Ser. B**10**(1971), 183–186. MR**0276105****[2]**Garrett Birkhoff,*Lattice theory*, Third edition. American Mathematical Society Colloquium Publications, Vol. XXV, American Mathematical Society, Providence, R.I., 1967. MR**0227053****[3]**Kenneth P. Bogart and William T. Trotter Jr.,*Maximal dimensional partially ordered sets. II. Characterization of 2𝑛-element posets with dimension 𝑛*, Discrete Math.**5**(1973), 33–43. MR**0318014**, https://doi.org/10.1016/0012-365X(73)90025-3**[4]**R. P. Dilworth,*A decomposition theorem for partially ordered sets*, Ann. of Math. (2)**51**(1950), 161–166. MR**0032578**, https://doi.org/10.2307/1969503**[5]**Ben Dushnik and E. W. Miller,*Partially ordered sets*, Amer. J. Math.**63**(1941), 600–610. MR**0004862**, https://doi.org/10.2307/2371374**[6]**Tosio Hiraguti,*On the dimension of orders*, Sci. Rep. Kanazawa Univ.**4**(1955), no. 1, 1–20. MR**0077500****[7]**G. O. H. Katona,*A generalization of some generalizations of Sperner’s theorem*, J. Combinatorial Theory Ser. B**12**(1972), 72–81. MR**0285402****[8]**R. Kimble,*Extremal problems in dimension theory for partially ordered sets*, Ph. D. Thesis, M.I.T., Cambridge, Mass., 1973.**[9]**Oystein Ore,*Theory of graphs*, American Mathematical Society Colloquium Publications, Vol. XXXVIII, American Mathematical Society, Providence, R.I., 1962. MR**0150753****[10]**Micha A. Perles,*A proof of Dilworth’s decomposition theorem for partially ordered sets*, Israel J. Math.**1**(1963), 105–107. MR**0168496**, https://doi.org/10.1007/BF02759805**[11]**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****[12]**E. Szpilrajn,*Sur l'extension de l'ordre partiel*, Fund. Math.**16**(1930), 386-389.**[13]**William T. Trotter Jr.,*Embedding finite posets in cubes*, Discrete Math.**12**(1975), 165–172. MR**0369191**, https://doi.org/10.1016/0012-365X(75)90031-X**[14]**-,*A generalization of Hiraguchi's inequality for posets*, J. Combinatorial Theor[ill] Ser. A (to a[ill][ill]ear).**[15]**Helge Tverberg,*On Dilworth’s decomposition theorem for partially ordered sets*, J. Combinatorial Theory**3**(1967), 305–306. MR**0214516**

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

Retrieve articles in all journals with MSC: 06A35

Additional Information

DOI:
https://doi.org/10.1090/S0002-9939-1975-0373988-0

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

Article copyright:
© Copyright 1975
American Mathematical Society