TY - JOUR

T1 - Acyclic sets of linear orders via the Bruhat orders

AU - Galambos, Ádám

AU - Reiner, Victor

PY - 2008/2/1

Y1 - 2008/2/1

N2 - We describe Abello's acyclic sets of linear orders [SIAM J Discr Math 4(1):1-16, 1991] as the permutations visited by commuting equivalence classes of maximal reduced decompositions. This allows us to strengthen Abello's structural result: we show that acyclic sets arising from this construction are distributive sublattices of the weak Bruhat order. This, in turn, shows that Abello's acyclic sets are, in fact, the same as Chameni-Nembua's distributive covering sublattices (S.T.D.C s). Fishburn's alternating scheme is shown to be a special case of the Abello/Chameni-Nembua acyclic sets. Any acyclic set that arises in this way can be represented by an arrangement of pseudolines, and we use this representation to derive a simple closed form for the cardinality of the alternating scheme. The higher Bruhat orders prove to be a natural mathematical framework for this approach to the acyclic sets problem.

AB - We describe Abello's acyclic sets of linear orders [SIAM J Discr Math 4(1):1-16, 1991] as the permutations visited by commuting equivalence classes of maximal reduced decompositions. This allows us to strengthen Abello's structural result: we show that acyclic sets arising from this construction are distributive sublattices of the weak Bruhat order. This, in turn, shows that Abello's acyclic sets are, in fact, the same as Chameni-Nembua's distributive covering sublattices (S.T.D.C s). Fishburn's alternating scheme is shown to be a special case of the Abello/Chameni-Nembua acyclic sets. Any acyclic set that arises in this way can be represented by an arrangement of pseudolines, and we use this representation to derive a simple closed form for the cardinality of the alternating scheme. The higher Bruhat orders prove to be a natural mathematical framework for this approach to the acyclic sets problem.

UR - http://www.scopus.com/inward/record.url?scp=38149140213&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38149140213&partnerID=8YFLogxK

U2 - 10.1007/s00355-007-0228-1

DO - 10.1007/s00355-007-0228-1

M3 - Article

AN - SCOPUS:38149140213

VL - 30

SP - 245

EP - 264

JO - Social Choice and Welfare

JF - Social Choice and Welfare

SN - 0176-1714

IS - 2

ER -