A compact representation for modular semilattices and its applications. (English) Zbl 1484.06015
Summary: A modular semilattice is a semilattice generalization of a modular lattice. We establish a Birkhoff-type representation theorem for modular semilattices, which says that every modular semilattice is isomorphic to the family of ideals in a certain poset with additional relations. This new poset structure, which we axiomatize in this paper, is called a PPIP (projective poset with inconsistent pairs). A PPIP is a common generalization of a PIP (poset with inconsistent pairs) and a projective ordered space. The former was introduced by Barthélemy and Constantin for establishing Birkhoff-type theorem for median semilattices, and the latter by Herrmann, Pickering, and Roddy for modular lattices. We show the \(\Theta(n)\) representation complexity and a construction algorithm for PPIP-representations of \((\wedge,\vee)\)-closed sets in the product \(L^n\) of modular semilattice \(L\). This generalizes the results of Hirai and Oki for a special median semilattice \(S_k\). We also investigate implicational bases for modular semilattices. Extending earlier results of Wild and Herrmann for modular lattices, we determine optimal implicational bases and develop a polynomial time recognition algorithm for modular semilattices. These results can be applied to retain the minimizer set of a submodular function on a modular semilattice.
MSC:
| 06A12 | Semilattices |
Keywords:
modular semilattice; Birkhoff representation theorem; implicational base; submodular functionReferences:
| [1] | Aigner, M., Combinatorial Theory (1997), Berlin: Springer, Berlin · Zbl 0858.05001 |
| [2] | Ardila, F.; Owen, M.; Sullivant, S., Geodesics in CAT(0) cubical complexes., Adv. Appl. Math., 48, 1, 142-163 (2012) · Zbl 1275.05055 · doi:10.1016/j.aam.2011.06.004 |
| [3] | Arias, M., Balcázar, J.L.: Canonical Horn representations and query learning. In: Algorithmic Learning Theory (20th International Conference on Algorithmic Learning Theory, ALT 2009) [Lecture Notes in Computer Science 5809], pp 156-170. Springer, Berlin (2009) · Zbl 1262.68059 |
| [4] | Bandelt, H-J; Van de Vel, M.; Verheul, E., Modular interval space., Math. Nachrichten Ser., 163, 177-201 (1993) · Zbl 0808.46011 · doi:10.1002/mana.19931630117 |
| [5] | Barthélemy, J-P; Constantin, J., Median graphs, parallelism and posets., Discret. Math., 111, 1-3, 49-63 (1993) · Zbl 0787.05027 · doi:10.1016/0012-365X(93)90140-O |
| [6] | Berman, J.; Idziak, P.; Marković, P.; McKenzie, R.; Valeriote, M.; Willard, R., Varieties with few subalgebras of powers., Trans. Amer. Math. Soc., 362, 3, 1445-1473 (2010) · Zbl 1190.08004 · doi:10.1090/S0002-9947-09-04874-0 |
| [7] | Burris, S.; Sankappanavar, HP, A Course in Universal Algebra (1981), Berlin: Springer, Berlin · Zbl 0478.08001 |
| [8] | Fujishige, S., Submodular Functions and Optimization (2005), Amsterdam: Elsevier B. V., Amsterdam · Zbl 1119.90044 |
| [9] | Fujishige, S.: Theory of Principal Partitions Revisited. In: Cook, W.J., Lovász, L., Vygen, J. (eds.) Research Trends in Combinatorial Optimization, pp 127-162. Springer, Berlin (2009) · Zbl 1359.05019 |
| [10] | Garg, A., Gurvits, L., Oliveira, R., Wigderson, A.: Operator scaling: theory and applications. Foundations of Computational Mathematics (2019) · Zbl 1432.68617 |
| [11] | Guigues, JL; Duquenne, V., Familles minimales d’implications informatives résultant d’un tableau de données binaires, Math. Sci. Hum., 95, 5-18 (1986) · Zbl 1504.68217 |
| [12] | Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms, MIT Press, Cambridge (1989) · Zbl 0703.68046 |
| [13] | Hamada, M., Hirai, H.: Maximum vanishing subspace problem, CAT(0)-space relaxation, and block-triangularization of partitioned matrix, arXiv:1705.02060 (2017) |
| [14] | Herrmann, C.; Pickering, D.; Roddy, M., A geometric description of modular lattices., Algebra Univ., 31, 3, 365-396 (1994) · Zbl 0816.06008 · doi:10.1007/BF01221792 |
| [15] | Herrmann, C.; Wild, M., A polynomial algorithm for testing congruence modularity, Int. J. Algebra Comput., 6, 4, 379-387 (1996) · Zbl 0857.08006 · doi:10.1142/S0218196796000210 |
| [16] | Hirai, H., Discrete convexity and polynomial solvability in minimum 0-extension problems, Math. Programm. Ser. A, 155, 1-55 (2016) · Zbl 1342.90163 · doi:10.1007/s10107-014-0824-7 |
| [17] | Hirai, H., Computing DM-decomposition of a partitioned matrix with rank-1 blocks, Linear Algebra Appl., 547, 105-123 (2018) · Zbl 1390.15040 · doi:10.1016/j.laa.2018.02.008 |
| [18] | Hirai, H., L-convexity on graph structures, J. Oper. Res. Soc. Jpn., 61, 71-109 (2018) · Zbl 1391.90475 |
| [19] | Hirai, H.: Discrete Convex Functions on Graphs and Their Algorithmic Applications. In: Fukunaga, T., Kawarabayashi, K. (eds.) Combinatorial Optimization and Graph Algorithms, Communications of NII Shonan Meetings, pp 67-101. Springer Nature, Singapore (2017) · Zbl 1397.90237 |
| [20] | Hirai, H.; Oki, T., A compact representation for minimizers of k-submodular functions, J. Comb. Optim., 36, 709-741 (2018) · Zbl 1434.90099 · doi:10.1007/s10878-017-0142-0 |
| [21] | Huber, A., Kolmogorov, V.: Towards minimizing k-submodular functions. In: Proceedings of the 2nd International Symposium on Combinatorial Optimization (ISCO2012), [Lecture Notes in Computer Science 7422], pp 451—462. Springer, Berlin (2012) · Zbl 1370.90219 |
| [22] | Ito, H.; Iwata, S.; Murota, K., Block-triangularizations of partitioned matrices under similarity/equivalence transformations, SIAM J. Matrix Anal. Appl., 15, 4, 1226-1255 (1994) · Zbl 0811.15008 · doi:10.1137/S0895479892235599 |
| [23] | Iri, M.: Structural Theory for the Combinatorial Systems Characterized by Submodular Function. In: Pulleyblank, W.R. (ed.) Progress in Combinatorial Optimization, pp 197-219. Academic Press, New York (1984) · Zbl 0544.05018 |
| [24] | Ivanyos, G.; Qiao, Y.; Subrahmanyam, KV, Constructive noncommutative rank computation in deterministic polynomial time over fields of arbitrary characteristics, Comput. Complex., 27, 561-593 (2018) · Zbl 1402.68197 · doi:10.1007/s00037-018-0165-7 |
| [25] | Kolmogorov, V.; Thapper, J.; Živný, S., The power of linear programming for general-valued CSPs, SIAM J. Comput, 44, 1, 1-36 (2015) · Zbl 1456.68059 · doi:10.1137/130945648 |
| [26] | Maier, D., Minimum covers in relational database model, J. Assoc. Comput. Mach., 27, 4, 664-674 (1980) · Zbl 0466.68085 · doi:10.1145/322217.322223 |
| [27] | Maier, D.: The Theory of Relational Databases. Computer Science Press, USA (1983) · Zbl 0519.68082 |
| [28] | Murota, K., Matrices and Matroids for Systems Analysis (2000), Berlin: Springer, Berlin · Zbl 0948.05001 |
| [29] | Murota, K.; Iri, M.; Nakamura, M., Combinatorial canonical form of layered mixed matrices and its application to block-triangularization of systems of linear/nonlinear equations, SIAM J. Algebraic Discret. Methods, 8, 1, 123-149 (1987) · Zbl 0623.65033 · doi:10.1137/0608011 |
| [30] | Nielsen, M.; Plotkin, G.; Winskel, G., Petri nets, event structures and domains, part I, Theor. Comput. Sci., 13, 85-108 (1981) · Zbl 0452.68067 · doi:10.1016/0304-3975(81)90112-2 |
| [31] | Sholander, M., Medians and betweenness, Proc. Amer. Math. Soc., 5, 5, 801-807 (1954) · Zbl 0056.26101 · doi:10.1090/S0002-9939-1954-0064749-7 |
| [32] | Ueberberg, J., Foundations of Incidence Geometry (2011), Berlin: Springer, Berlin · Zbl 1237.51004 |
| [33] | Wild, M., A theory of finite closure spaces based on implications, Adv. Math., 108, 1, 118-139 (1994) · Zbl 0863.54002 · doi:10.1006/aima.1994.1069 |
| [34] | Wild, M., Optimal implicational bases for finite modular lattices, Quaest. Math., 23, 2, 153-161 (2000) · Zbl 0963.06006 · doi:10.2989/16073600009485964 |
| [35] | Wild, M., The joy of implications, aka pure H,orn formulas: Mainly a survey, Theor. Comput. Sci., 658, part B, 264-292 (2017) · Zbl 1418.03144 · doi:10.1016/j.tcs.2016.03.018 |
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.
