Sublattices of product spaces: Hulls, representations and counting. (English) Zbl 1170.06002
Let \(L\) be a lattice. The authors call \(L\) a product space, if \(L\) can be written as a direct product of (simpler) lattices: \(L=T_I=\prod (T_i: i\in I).\) Having a non-empty subset \(H\) of the product space \(L\), they investigate the sublattice \([H]\) of \(L\) generated by \(H\). The sublattice \([H]\) is said to be a sublattice hull of \(H.\) In the paper the following questions are considered: (i) descriptions of \([H]\) or, in other words, representations of \([H]\); (ii) recognitions of sublattices of product spaces, i.e., a process showing whether a subset \(K\) of \(L\) is a sublattice of \(L\) or not; (iii) counting sublattices in finite product spaces with finite chains (Birkhoff’s problem). Note that for many applications it is often important to be able to represent a sublattice in a computationally or algebraically convenient way. It is also useful to be able to recognize if a given subset \(K\) of \(L\) is a sublattice and, if not, to construct \([K].\)
Some results: (1) Let \(\pi_i: L=T_I\rightarrow T_i\) denote the \(i\)-th projection for \(i\in I\), i.e., if \(x=x_I=(x_i)_{i\in I}\in L,\) then \(\pi_i(x)=x_i.\) Similarly, if \(J\subseteq I,\) then \(\pi_J(x)=(x_i)_{i\in J}=x_J.\) In addition, if \(H\subseteq T_J\), then the cylinder Cyl\(_I(H)\) is the set \(\{x\in T_I: x_J\in H\}.\) Now, let \(H\subseteq L\) for a product space \(L.\) It is known that \([H]\subseteq \bigcap(\text{Cyl}_I([\pi_{i,j}(H)]): i\neq j\) and \(i,j\in I).\) The authors find sufficient conditions under which equality holds in the above inclusion. This description of \([H]\) is called a representation by projections. (2) There is another description of \([H]\), namely the representation with proper boundary epigraphs. (3) The authors provide upper and lower bounds on the number of sublattices, giving a partial solution to Birkhoff’s problem.
Observe that the authors extend results of D. M. Topkis [Pac. J. Math. 65, 525–532 (1976; Zbl 0333.06002)] and A. F. Veinott jun. [Linear Algebra Appl. 114/115, 681–704 (1989; Zbl 0669.06002)].
Some results: (1) Let \(\pi_i: L=T_I\rightarrow T_i\) denote the \(i\)-th projection for \(i\in I\), i.e., if \(x=x_I=(x_i)_{i\in I}\in L,\) then \(\pi_i(x)=x_i.\) Similarly, if \(J\subseteq I,\) then \(\pi_J(x)=(x_i)_{i\in J}=x_J.\) In addition, if \(H\subseteq T_J\), then the cylinder Cyl\(_I(H)\) is the set \(\{x\in T_I: x_J\in H\}.\) Now, let \(H\subseteq L\) for a product space \(L.\) It is known that \([H]\subseteq \bigcap(\text{Cyl}_I([\pi_{i,j}(H)]): i\neq j\) and \(i,j\in I).\) The authors find sufficient conditions under which equality holds in the above inclusion. This description of \([H]\) is called a representation by projections. (2) There is another description of \([H]\), namely the representation with proper boundary epigraphs. (3) The authors provide upper and lower bounds on the number of sublattices, giving a partial solution to Birkhoff’s problem.
Observe that the authors extend results of D. M. Topkis [Pac. J. Math. 65, 525–532 (1976; Zbl 0333.06002)] and A. F. Veinott jun. [Linear Algebra Appl. 114/115, 681–704 (1989; Zbl 0669.06002)].
Reviewer: T. Katriňák (Bratislava)
MSC:
| 06B15 | Representation theory of lattices |
| 05A16 | Asymptotic enumeration |
| 06B05 | Structure theory of lattices |
| 68W05 | Nonnumerical algorithms |
Keywords:
lattices; sublattice hull membership; sublattice generated by a subset; sublattice representation; counting sublatticesReferences:
| [1] | Birkhoff, G., Rings of sets, Duke Math. J., 3, 443-454 (1937) · Zbl 0017.19403 |
| [2] | G. Birkhoff, Lattice Theory, American Mathematical Society Colloquium Publications, third ed., vol. 25, American Mathematical Society, Providence, RI, 1967 (First ed. 1940).; G. Birkhoff, Lattice Theory, American Mathematical Society Colloquium Publications, third ed., vol. 25, American Mathematical Society, Providence, RI, 1967 (First ed. 1940). · JFM 66.0100.04 |
| [3] | G. Birkhoff, Lattices and their applications, in: K.A. Baker, R. Wille (Eds.), Lattice Theory and its Applications, Darmstadt, 1991, Research and Exposition in Mathematics, vol. 23, Heldermann, Lemgo, 1995, pp. 7-25.; G. Birkhoff, Lattices and their applications, in: K.A. Baker, R. Wille (Eds.), Lattice Theory and its Applications, Darmstadt, 1991, Research and Exposition in Mathematics, vol. 23, Heldermann, Lemgo, 1995, pp. 7-25. · Zbl 0843.06001 |
| [4] | Davey, B. A.; Priestley, H. A., Introduction to Lattices and Order (1990), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 0701.06001 |
| [5] | K. Elbassioni, An algorithm for dualization in products of lattices and its applications, in: Algorithms—ESA 2002: 10th Annual European Symposium, Rome, Italy, September 17-21, 2002, Proceedings, Lecture Notes in Computer Science, vol. 2461, Springer, Berlin, 2002, pp. 424-435.; K. Elbassioni, An algorithm for dualization in products of lattices and its applications, in: Algorithms—ESA 2002: 10th Annual European Symposium, Rome, Italy, September 17-21, 2002, Proceedings, Lecture Notes in Computer Science, vol. 2461, Springer, Berlin, 2002, pp. 424-435. · Zbl 1019.68130 |
| [6] | Frank, A., Submodular functions in graph theory, Discrete Math., 111, 231-243 (1993) · Zbl 0788.05078 |
| [7] | Fujishige, S., Submodular functions and optimization, Ann. Discrete Math., 47 (1991) · Zbl 0728.90056 |
| [8] | M. Grötschel, L. Lovász, A. Schrijver, Geometric algorithms and combinatorial optimization, Springer, Berlin, 1988.; M. Grötschel, L. Lovász, A. Schrijver, Geometric algorithms and combinatorial optimization, Springer, Berlin, 1988. · Zbl 0634.05001 |
| [9] | Hardy, G. H.; Littlewood, J. E.; Polya, G., Inequalities (1952), Cambridge University Press: Cambridge University Press Cambridge, England, (Reprinted 1997) · Zbl 0047.05302 |
| [10] | Kleitman, D. J.; Rothschild, B. L., Asymptotic enumeration of partial orders on a finite set, Trans. Amer. Math. Soc., 205, 205-220 (1975) · Zbl 0302.05007 |
| [11] | Luxemburg, W. A.J.; Zaanen, A. C., Riesz Spaces, vol. I (1971), North-Holland: North-Holland Amsterdam · Zbl 0231.46014 |
| [12] | Milgrom, P.; Shannon, C., Monotone comparative statics, Econometrica, 62, 1, 157-180 (1994) · Zbl 0789.90010 |
| [13] | H. Narayanan, Submodular Functions and Electrical Networks, Ann. Discrete Math. 54 (1997).; H. Narayanan, Submodular Functions and Electrical Networks, Ann. Discrete Math. 54 (1997). · Zbl 0921.05021 |
| [14] | A. Recski, Matroid theory and its applications, Springer, Berlin, 1989.; A. Recski, Matroid theory and its applications, Springer, Berlin, 1989. · Zbl 0723.05023 |
| [15] | Schrijver, A., Combinatorial Optimization: Polyhedra and Efficiency (2003), Springer: Springer Berlin · Zbl 1041.90001 |
| [16] | Topkis, D. M., The structure of sublattices of the product of \(n\) lattices, Pacific J. Math., 65, 525-532 (1976) · Zbl 0333.06002 |
| [17] | Topkis, D. M., Supermodularity and Complementarity (1998), Princeton University Press: Princeton University Press Princeton, NJ |
| [18] | Veinott, A. F., Representation of general and polyhedral subsemilattices and sublattices of product spaces, Linear Algebra Appl., 114/115, 681-704 (1989) · Zbl 0669.06002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
