Signed ring families and signed posets. (4th May 2021)

• Record Type: Journal Article
• Authors: Ando, Kazutoshi; Fujishige, Satoru
• Is Part Of: Optimization methods and software. Volume 36:Number 2/3(2021)
• Page Start: 262
• Page End: 278
• Publication Date: 2021-05-04
• Subjects: Signed ring families -- signed posets -- bidirected graphs -- decomposition -- bisubmodular functions; 05C22 -- 06D05 -- 90C27; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2020.1740219
• Languages: English
• ISSNs: 1055-6788

Abstract

ABSTRACT: The one-to-one correspondence between finite distributive lattices and finite partially ordered sets (posets) is a well-known theorem of G. Birkhoff. 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, 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.