THE WEAK BRUHAT ORDER OF S-SIGMA CONSISTENT SETS, AND CATALAN NUMBERS

Chains in the weak Bruhat order beta of S-SIGMA (the symmetric group on SIGMA) belong to the class of subsets of S-SEGMA over which unrestricted choice necessarily produces transitive relations under pairwise simple majority vote (consistent sets). If for A subset-of SIGMA we let (A) = union-p-is-an-element-of-A T(p) where T(p) = {(p(i), p(j), p(k))\i < j < k} and PSI(A) = {w-is-an-element-of-S(SIGMA)\T(w) subset-of T(A)} the following theorem (among others) is obtained. THEOREM. For all q is-an-element-of S(SIGMA), if A is a saturated chain under beta then PSI(qA) is an upper semimodular sublattice of cardinality [GRAPHICS] The \SIGMA\ th Catalan number. From the Arrow's Impossibility Theorem point of view, the results obtained here indicate that majority rule produces transitive results if the collection of voters as a can be partitioned into no more than (\SIGMA\2 + \SIGMA\)/2 groups which can be ordered according to the level of disagreement they have with respect to a fixed permutation p. On the other hand, by viewing S(SIGMA) as a Coxeter group a "novel" combinatorial interpretation of the collection of maximal chains that can be obtained from one another by using only one type of Coxeter transformation is obtained.