No label defined (Q3781801)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4043899
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4043899 |
Statements
1986
0 references
majority rule
0 references
symmetric group
0 references
Latin square
0 references
consistent sets
0 references
saturated chain
0 references
weak Bruhat order
0 references
weighted complete graphs
0 references
minimum spanning trees
0 references
0.8521526455879211
0 references
0.7984023690223694
0 references
0.7651419043540955
0 references
0.7403100728988647
0 references
[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.
0 references