×

Signed ring families and signed posets. (English) Zbl 1467.05102

Summary: The one-to-one correspondence between finite distributive lattices and finite partially ordered sets (posets) is a well-known theorem of G. Birkhoff [Duke Math. J. 3, 443–454 (1937; Zbl 0017.19403); Lattice theory. Third (new) ed. American Mathematical Society (AMS), Providence, RI (1967; Zbl 0153.02501)]. This implies a nice representation of any distributive lattice by its corresponding poset, where the size of the former (distributive lattice) is often exponential in the size of the underlying set of the latter (poset). A lot of engineering and economic applications bring us distributive lattices as a ring family of sets which is closed with respect to the set union and intersection. When it comes to a ring family of sets, the underlying set is partitioned into subsets (or components) and we have a poset structure on the partition. This is a set-theoretical variant of the Birkhoff theorem revealing the correspondence between finite ring families and finite posets on partitions of the underlying sets, which was pursued by Masao Iri around 1978 [M. Iri, in: Combinatorial mathematics, 2nd int. Conf., New York 1978, Ann. New York Acad. Sci. 319, 306–319 (1979; Zbl 0478.05023); in: Mathematical programming, 11th int. Symp., Bonn 1982, 158–201 (1983; Zbl 0542.05024); in: Progress in combinatorial optimization, Conf. Waterloo/Ont. 1982, 197–219 (1984; Zbl 0544.05018)], especially concerned with what is called the principal partition of discrete systems such as graphs, matroids, and polymatroids. In the present paper we investigate a signed-set version of the Birkhoff-Iri decomposition in terms of signed ring family, which corresponds to Reiner’s result on signed posets, a signed counterpart of the Birkhoff theorem. We show that given a signed ring family, we have a signed partition of the underlying set together with a signed poset on the signed partition which represents the given signed ring family. This representation is unique up to certain reflections.

MSC:

05C22 Signed and weighted graphs
06A07 Combinatorics of partially ordered sets
06D05 Structure and representation theory of distributive lattices
90C27 Combinatorial optimization

References:

[1] Ando, K. and Fujishige, S., \(####\)-closed families and signed posets, Rep. No. 93813, Research Institute for Discrete Mathematics, University of Bonn, Bonn, 1994.
[2] Ando, K.; Fujishige, S., On structures of bisubmodular polyhedra, Math. Program., 74, 293-317 (1996) · Zbl 0855.68107
[3] Ando, K.; Fujishige, S.; Naitoh, T., Balanced bisubmodular systems and bidirected flows, J. Oper. Res. Soc. Jpn, 40, 437-447 (1997) · Zbl 0901.05051 · doi:10.15807/jorsj.40.437
[4] Ando, K.; Fujishige, S.; Nemoto, T., Decomposition of a bidirected graph into strongly connected components and its signed poset structure, Discrete Appl. Math., 68, 237-248 (1996) · Zbl 0872.05029 · doi:10.1016/0166-218X(95)00068-3
[5] Bilbao, J. M.; Fernández, J. R.; Jiménez, N.; López, J. J., Biprobabilistic values for bicooperative games, Discrete Appl. Math., 156, 2698-2711 (2008) · Zbl 1153.91320 · doi:10.1016/j.dam.2007.11.007
[6] Birkhoff, G., Rings of sets, Duke Math. J., 3, 443-454 (1937) · Zbl 0017.19403 · doi:10.1215/S0012-7094-37-00334-X
[7] Birkhoff, G., Lattice Theory (1967) · Zbl 0153.02501
[8] Bouchet, A.; Cunningham, W. H., Delta-matroids, jump systems and bisubmodular polyhedra, SIAM J. Discrete Math., 8, 17-32 (1995) · Zbl 0821.05010 · doi:10.1137/S0895480191222926
[9] Chandrasekaran, R.; Kabadi, S. N., Pseudomatroids, Discrete Math., 71, 205-217 (1988) · Zbl 0656.05023 · doi:10.1016/0012-365X(88)90101-X
[10] Dunstan, F. D.J.; Welsh, D. J.A., A greedy algorithm for solving a certain class of linear programmes, Math. Program., 5, 338-353 (1973) · Zbl 0297.90050 · doi:10.1007/BF01580137
[11] Fujimoto, K.; Murofushi, T.; Sugeno, M., k-additivity and \(####\)-decomposability of bi-capacities and its integral, Fuzzy Sets Syst., 158, 1698-1712 (2007) · Zbl 1127.28012 · doi:10.1016/j.fss.2007.03.002
[12] Fujishige, S., Submodular Functions and Optimization · Zbl 1119.90044
[13] Fujishige, S., A min-max theorem for bisubmodular polyhedra, SIAM J. Discrete Math., 10, 294-308 (1997) · Zbl 0873.52012 · doi:10.1137/S0895480194264344
[14] Fujishige, S., Theory of principal partitions revisited, in Research Trends in Combinatorial Optimization, W. Cook, L. Lovász, and J. Vygen, eds., Springer, Berlin, 2009, pp. 127-162. · Zbl 1359.05019
[15] Fujishige, S., Bisubmodular polyhedra, simplicial divisions, and discrete convexity, Discrete Optim., 12, 115-120 (2014) · Zbl 1308.90146 · doi:10.1016/j.disopt.2014.02.002
[16] Fujishige, S., Parametric bisubmodular function minimization and its associated signed ring family, Discrete Appl. Math., 227, 142-148 (2017) · Zbl 1365.05119 · doi:10.1016/j.dam.2017.04.047
[17] Fujishige, S.; Iwata, S., Bisubmodular function minimization, SIAM J. Discrete Math., 19, 1065-1073 (2006) · Zbl 1122.90067 · doi:10.1137/S0895480103426339
[18] Fujishige, S.; Tanigawa, S., Polynomial combinatorial algorithms for skew-bisubmodular function minimization, Math. Program. Ser. A, 171, 87-114 (2018) · Zbl 1405.90110 · doi:10.1007/s10107-017-1171-2
[19] Fujishige, S.; Tanigawa, S.; Yoshida, Y., Generalized skew bisubmodularity: A characterization and a min-max theorem, Discrete Optim., 12, 1-9 (2014) · Zbl 1308.90147 · doi:10.1016/j.disopt.2013.12.001
[20] Grabisch, M.; Labreuche, C., Bi-capacities. I. definition, Möbius transform and interaction, Fuzzy Sets Syst., 151, 211-236 (2005) · Zbl 1106.91023 · doi:10.1016/j.fss.2004.08.012
[21] Grabisch, M.; Labreuche, C., Bi-capacities. II. the choquet integral, Fuzzy Sets Syst., 151, 237-259 (2005) · Zbl 1114.91028 · doi:10.1016/j.fss.2004.08.013
[22] Iri, M., The maximum-rank minimum-term-rank theorem for the pivotal transforms of a matrix, Linear. Algebra. Appl., 2, 427-446 (1969) · Zbl 0206.04001 · doi:10.1016/0024-3795(69)90015-9
[23] Iri, M., A review of recent work in Japan on principal partitions of matroids and their applications, Ann. N. Y. Acad. Sci., 319, 306-319 (1979) · Zbl 0478.05023 · doi:10.1111/j.1749-6632.1979.tb32805.x
[24] Iri, M., Applications of matroid theory, in Mathematical Programming - The State of the Art, A. Bachem, M. Grötschel and B. Korte, eds., Springer, Berlin, 1983, pp. 158-201. · Zbl 0542.05024
[25] Iri, M., Structural theory for the combinatorial systems characterized by submodular functions, in Progress in Combinatorial Optimization, W.R. Pulleyblank, ed., Academic Press, Toronto, 1984, pp. 197-219. · Zbl 0544.05018
[26] Iwata, S., Dulmage-Mendelsohn type decomposition for general graphs, RIMS preprint (1995), RIMS-1017, Kyoto University. · Zbl 0829.15008
[27] Iwata, S., Block triangularization of skew-symmetric matrices, Linear. Algebra. Appl., 273, 215-226 (1998) · Zbl 0892.65027 · doi:10.1016/S0024-3795(97)00375-3
[28] Kishi, G.; Kajitani, Y., Maximally distant trees in a linear graph (in Japanese), Trans. Inst. Electron. Commun. Eng. Jpn, 51A, 196-203 (1968)
[29] Lovász, L.; Plummer, M. D., Matching Theory (1986), AMS Chelsea Publishing, Providence · Zbl 0618.05001
[30] McCormick, S. T.; Fujishige, S., Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization, Math. Program. Ser. A, 122, 87-120 (2010) · Zbl 1190.65099 · doi:10.1007/s10107-008-0242-9
[31] Qi, L., Directed submodularity, ditroids and directed submodular flows, Math. Program., 42, 579-599 (1988) · Zbl 0665.90075 · doi:10.1007/BF01589420
[32] Reiner, V., Signed posets, J. Comb. Theory Ser. A, 62, 324-360 (1993) · Zbl 0773.06008 · doi:10.1016/0097-3165(93)90052-A
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.