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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abello J (1991) The weak Bruhat order of s σ, consistent sets, and Catalan numbers. SIAM J Discr Math 4(1):1–16
Björner A, Brenti F (2005) Combinatorics of Coxeter groups Graduate texts in mathematics. Springer, Heidelberg
Björner A, Vergnas ML, Sturmfels B, White N, Ziegler GM (1993) Oriented matriods. Number 46 in Encyclopedia of mathematics and its applications. Cambridge University Press, Cambridge
Blin J-M (1972) The general concept of multidimensional consistency: some algebraic aspects of the aggregation problem. Discussion. Papers no. 12 Northwestern University CMS–EMS
Chameni-Nembua C (1989) Regle majoritaire et distributivite dans le permutoedre. Math Inf Sci Hum 27(108):5–22
Craven J (1994) Further Notes on Craven’s Conjecture. Soc Choice Welf 11:283–285
Craven J (1996) Majority-consistent preference orderings. Soc Choice Welf 13:259–267
Felsner S, Weil H (2000) A theorem on higher Bruhat orders. Discr Comput Geomet 23(1):121–127
Felsner S (1997) On the number of arrangements of pseudolines. Discr Comput Geomet 18:257–267
Felsner S, Ziegler GM (2001) Zonotopes associated with higher Bruhat orders. Discr Math 241:301–312
Fishburn PC (1997) Acyclic sets of linear orders. Soc Choice Welf 14:113–124
Fishburn PC (2002) Acyclic sets of linear orders: a progress report. Soc Choice Welf 19:431–447
Goodman JE, Pollack R (1984) Semispaces of configurations, cell complexes of arrangements. J Combin Theory, Ser A 37:257–293
Grünbaum B (1972) Arrangements and Spreads. Number 10 in Regional conference series in mathematics. American Mathematical Societ
Guilbaud GTh, Rosenstiehl P (1963) Analyse algébrique d’n scrutin. Math Sci Hum 4:9–33
Manin YuI, Schechtman VV (1986) Higher Bruhat orders, related to the symmetric group. Funct Anal Appl 20:148–150
Manin YuI, Schechtmann VV (1989) Arrangements of hyperplanes, higher braid groups and higher Bruhat orders. In: Coates J et al, (ed), Algebraic number theory—in honor of K. Iwasawa. vol. 17 of Advanced studies in pure mathematics, Kinokuniya Company/Academic Press, pp 289–308 1989.
Marquis de Condorcet (1785) Essai sur l’application de l’analyse à la probabilté des decisions rendues à la pluralité des voix. Paris
Raz R (2000) VC-dimension of sets of permutations. combinatorica 20(2):241–255
Sen AK (1966) A possibility theorem on majority decisions. Econometrica 34(2):491–499
Stanton D, White D (1986) Constructive combinatorics. Springer, Heidelberg
Ward B (1965) Majority voting and alternative forms of public enterprises. In: Margolis J (ed) The public economy of urban communities. Johns Hopkins Press, Baltimore
Ziegler GM (1993) Higher Bruhat orders and cyclic hyperplane arrangements. Topology 32(2): 259–279
Author information
Authors and Affiliations
Corresponding author
Additional information
We would like to thank the Editor, Professor Bernard Monjardet, and two anonymous referees for their comments and additional references.
Rights and permissions
About this article
Cite this article
Galambos, Á., Reiner, V. Acyclic sets of linear orders via the Bruhat orders. Soc Choice Welfare 30, 245–264 (2008). https://doi.org/10.1007/s00355-007-0228-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00355-007-0228-1