Cambrian Acyclic Domains: Counting c -singletons
- PDF / 1,482,483 Bytes
- 33 Pages / 439.642 x 666.49 pts Page_size
- 21 Downloads / 173 Views
Cambrian Acyclic Domains: Counting c -singletons Jean-Philippe Labbe´ 1
· Carsten E. M. C. Lange2
Received: 7 May 2018 / Accepted: 4 December 2019 / © Springer Nature B.V. 2020
Abstract We study the size of certain acyclic domains that arise from geometric and combinatorial constructions. These acyclic domains consist of all permutations visited by commuting equivalence classes of maximal reduced decompositions if we consider the symmetric group and, more generally, of all c-singletons of a Cambrian lattice associated to the weak order of a finite Coxeter group. For this reason, we call these sets Cambrian acyclic domains. Extending a closed formula of Galambos–Reiner for a particular acyclic domain called Fishburn’s alternating scheme, we provide explicit formulae for the size of any Cambrian acyclic domain and characterize the Cambrian acyclic domains of minimum or maximum size. Keywords Acyclic sets · Enumeration · Generalized permutahedra · Pseudoline arrangements · Sortable elements · Coxeter groups
1 Introduction Examples of c-singletons include certain acyclic domains in social choice theory, natural partial orders of crossings in pseudoline arrangements as well as certain vertices of particular convex polytopes called permutahedra and associahedra in discrete geometry. We first describe these objects and outline the relationship between these incarnations. Acyclic domains are of great interest in social choice theory because of their importance for the following voting process: voters choose among a given collection of linear orders on m candidates and the result of the ballot obeys the order imposed by the majority for each pair of candidates. As already mentioned by the Marquis de Condorcet in 1785 [6], not every collection of linear orders yields a transitive order on the candidates in every
This work was supported by the DFG Collaborative Research Center TRR 109 “Discretization in Geometry and Dynamics”. The first author was partially supported by a FQRNT Doctoral scholarship. Jean-Philippe Labb´e
[email protected] Carsten E. M. C. Lange [email protected] 1
Institut f¨ur Mathematik, Freie Universit¨at Berlin, Arnimallee 2, 14195, Berlin, Germany
2
Fakult¨at f¨ur Mathematik, Technische Universit¨at M¨unchen, Boltzmannstr. 3, Garching, D-85748, Germany
Order
election. Collections that do guarantee transitivity are called acyclic domains or Condorcet domains. According to Fishburn [11, Introduction], the fundamental problem to determine the maximum cardinality of an acyclic domain for a given number of candidates is one of most fascinating and intractable combinatorial problems in social choice theory. Abello as well as Chameni-Nembua describe different constructions of “large” acyclic sets. They use maximal chains of the weak order on the symmetric group m [1] and study covering distributive sublattices of the weak order on m [5]. Galambos and Reiner [13] prove that maximal acyclic domains constructed by Abello coincide with those of Chameni-Nembua and describe them in terms of higher
Data Loading...
