Acyclic sets of linear orders via the Bruhat orders

Ádám Galambos, Victor Reiner

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)245-264
Number of pages20
JournalSocial Choice and Welfare
Volume30
Issue number2
DOIs
StatePublished - Feb 1 2008

Fingerprint Dive into the research topics of 'Acyclic sets of linear orders via the Bruhat orders'. Together they form a unique fingerprint.

Cite this