scientific article; zbMATH DE number 4043899

From MaRDI portal
Publication:3781801





[For the entire collection see Zbl 0608.00004.] Simple majority rule produces transitive results when it is applied to those subsets of the symmetric group which do not contain a Latin square. Call such subsets consistent sets. It is our purpose here to study consistent sets from the algorithmic point of view. To this end, first we present a bijection between several seemingly different constructions of consistent sets offered in the past. This offers a new way to look at some of the known conditions for transitivity of the majority rule. Second, we discuss algorithms for recognition and construction of those maximal consistent sets which contain a saturated chain in the weak Bruhat order, \(\beta\), of the symmetric group. Those consistent sets, of cardinality at least n-1, which contain the first lexicographical chain in \(\beta\) have associated weighted complete graphs whose unique minimum spanning trees are also minimum Hamiltonian paths.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3781801)