Acyclic Domains of Linear Orders: A Survey
---
paper_title: How Large are Transitive Simple Majority Domains

paper_content:

It is well known that pairwise simple majority voting (smv) over n alternatives can lead to a nontransitive social outcome if the domain of possible (transitive) individual preference orderings is unrestricted. A variety of domain restrictions which ensure transitivity have been offered (the best known being single-peaked preferences) but all of course, amount to some limitation of individual preferences. Call such restricted domains transitive smv domains (tsmv) and consider the following question: how many preference orderings may transitive smv domains contain and how much range of choice is consistent with ensured transitivity? This presents a combinatorial problem of an unusual sort; a lower bound of $2^{n - 1} $ is easily proven but good upper bounds are generally harder to obtain. By using a graph representation of $S_n $ (the symmetric group on n symbols) we have been able to construct transitive smv domains of cardinality $3 \times 2^{n - 2} - 4$ for $n > 4$ which to our knowledge is the best kno...
---
paper_title: Majority-consistent preference orderings

paper_content:

This paper considers the construction of sets of preferences that give consistent outcomes under majority voting. Fishburn [7] shows that by combining the concepts of single-peaked and single-troughed preferences (which are themselves examples of value restriction) it is possible to provide a simple description of the extent of agreement between individuals that allows the construction of sets that are as large as those previously known (for fewer than 7 alternatives) and larger than those previously known (for 7 or more alternatives). This paper gives a characterisation of the preferences generated through these agreements and makes observations on the relation between the sizes of such sets as the number of alternatives increases.
---
paper_title: An Axiomatic Theory of Tournament Aggregation

paper_content:

An axiomatic theory for aggregation of individual preferences is developed. Many authors, since K. J. Arrow, have studied the case where every individual preference is an ordering. We study here the case where every individual preference is a tournament for instance, in “paired comparisons”. The original results obtained can be compared to those of the classic theory. For example, we prove, in this context, a generalisation of Arrow's theorem and we emphasize duality between Arrow's results and Black-Inada-Sen's results technically by means of a Galois connection between two lattices. We used social functions defined by means of “families of majorities” simple games,
---
paper_title: Notes on Craven's conjecture

paper_content:

Craven's conjecture says that 2n−1 is the maximum number of linear orders on {1, 2,...n} that simultaneously satisfy certain restrictions on three-element subsets of {1, 2,...n}. This is true for n=3, but the maximum exceeds 2n−1 for n≧4. There is a set of nine linear orders on {1, 2, 3, 4} that satisfy the restrictions. As n gets large, the ratio of the size of the maximum satisfying set to 2n−1 approaches infinity.
---
paper_title: The Individual Freedom Allowed by the Value Restriction Condition.

paper_content:

Abstract : The majority method (for an odd N, a is before b in the collective order iff more individual orders rank a before b than b before a) does not always yield a total order. The frequency of the so-called Condorcet effect has been extensively derived and computed. Following the proof of impossibility theorem an example of possible escape by some natural restrictions on the domain of the individual orders is given. Since that time, various other conditions have been proposed Then there began to appear some sufficient and necessary in a certain sense conditions. The value restriction condition is among them.
---
paper_title: How Large are Transitive Simple Majority Domains

paper_content:

It is well known that pairwise simple majority voting (smv) over n alternatives can lead to a nontransitive social outcome if the domain of possible (transitive) individual preference orderings is unrestricted. A variety of domain restrictions which ensure transitivity have been offered (the best known being single-peaked preferences) but all of course, amount to some limitation of individual preferences. Call such restricted domains transitive smv domains (tsmv) and consider the following question: how many preference orderings may transitive smv domains contain and how much range of choice is consistent with ensured transitivity? This presents a combinatorial problem of an unusual sort; a lower bound of $2^{n - 1} $ is easily proven but good upper bounds are generally harder to obtain. By using a graph representation of $S_n $ (the symmetric group on n symbols) we have been able to construct transitive smv domains of cardinality $3 \times 2^{n - 2} - 4$ for $n > 4$ which to our knowledge is the best kno...
---
paper_title: On permutation lattices

paper_content:

Abstract The lattice perm( n ) of permutations of an n -element set n ={1,…, n , ‘rooted’ at (1,…, n ), is shown to be meet-and join-semidistributive, which implies known results such as the non-existene of M 3 -sublattices, and that the complementation defines a congruence relation in Perm( n ) with 2 n −1 classes. The meet-core of Perm( n ) is shown to be the set of meet-irreducible elements together with all the elements that have two upper covers that moreover generate a covering sublattice isomorphic to Perm( 3 ); this shows that the meet operation is completely expressible in terms of reversing adjacent pairs. A recursive construction of Perm( n ) as a Galois lattice - via a kind ofsummation process - is given, which has been a key for obtaining clear drawings of Perm( 4 ) and Perm( 5 ) with our new PC/VGA graphic program GLAD (General Lattice Analysis and Design). Finally, the congruence lattice C (Perm( n )) is recursively characterized through the order of its meet-irreducible elements.
---
paper_title: The Lattice of Permutations is Bounded

paper_content:

The purpose of this paper is to show that the lattice Sn of permutations on a n-element set is bounded. This result strengthens the semi-distributive nature of the lattice Sn. To prove this property, we use a characterization of the class of bounded lattices in terms of arrows relations defined on the join-irreductible elements of a lattice or, more precisely, in terms of the A-table of a lattice.
---
paper_title: The Majority Rule and Combinatorial Geometry (Via the Symmetric Group)

paper_content:

The Marquis du Condorcet recognized 200 years ago that majority rule can produce intransitive group preferences if the domain of possible (transitive) individual preference orders is unrestricted. We present results on the cardinality and structure of those maximal sets of permutations for which majority rule produces transitive results (consistent sets). Consistent sets that contain a maximal chain in the Weak Bruhat Order inherit from it an upper semimodular sublattice structure. They are intrinsically related to a special class of hamiltonian graphs called persistent graphs. These graphs in turn have a clean geometric interpretation: they are precisely visibility graphs of staircase polygons. We highlight the main tools used to prove these connections and indicate possible social choice and computational research directions.
---
paper_title: The Individual Freedom Allowed by the Value Restriction Condition.

paper_content:

Abstract : The majority method (for an odd N, a is before b in the collective order iff more individual orders rank a before b than b before a) does not always yield a total order. The frequency of the so-called Condorcet effect has been extensively derived and computed. Following the proof of impossibility theorem an example of possible escape by some natural restrictions on the domain of the individual orders is given. Since that time, various other conditions have been proposed Then there began to appear some sufficient and necessary in a certain sense conditions. The value restriction condition is among them.
---
paper_title: The median procedure in cluster analysis and social choice theory

paper_content:

Abstract Classical approachs for fitting and aggregation problems, specially in cluster analysis, social choice theory and paired comparisons methods, consist in the minimization of a remoteness function between relational data and a relational model. The notion of median, with its algebraic, metric, geometrical and statistical aspects, allow a unified treatment of many of base problems. Properties of median procedures are organized according to four directions: stabilities and axiomatic characterizations; Arrow-like properties; combinatorial properties; effective computational possibilities. Finally, interesting mathematical problems, related to the notion of median are surveyed.
---
paper_title: VC-Dimension of Sets of Permutations

paper_content:

of a set of permutations \(\) to be the maximal k such that there exist distinct \(\) that appear in A in all possible linear orders, that is, every linear order of \(\) is equivalent to the standard order of \(\) for at least one permutation \(\).
---
paper_title: Higher Bruhat orders and cyclic hyperplane arrangements

paper_content:

We study the higher Bruhat orders $B(n,k)$ of Manin & Schechtman [MaS] and - characterize them in terms of inversion sets, - identify them with the posets $U(C^{n+1,r},n+1)$ of uniform extensions of the alternating oriented matroids $C^{n,r}$ for $r:=n-k$ (that is, with the extensions of a cyclic hyperplane arrangement by a new oriented pseudoplane), - show that $B(n,k)$ is a lattice for $k =1$ and for $r\le 3$, but not in general, - show that $B(n,k)$ is ordered by inclusion of inversion sets for $k=1$ and for $r\le 4$. However, $B(8,3)$ is not ordered by inclusion. This implies that the partial order $B_\subseteq (n,k)$ defined by inclusion of inversion sets differs from $B(n,k)$ in general. We show that the proper part of $B_\subseteq (n,k)$ is homotopy equivalent to $S^{r-2}$. Consequently, - $B(n,k)\simeq S^{r-2}$ for $k=1$ and for $r\le 4$. In contrast to this, we find that the uniform extension poset of an affine hyperplane arrangement is in general not graded and not a lattice even for $r=3$, and that the proper part is not always homotopy equivalent to $S^{r(M)-2}$.
---
paper_title: Acyclic Sets of Linear Orders via the Bruhat Orders

paper_content:

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.
---
paper_title: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected

paper_content:

Several enumeration and reliability problems are shown to be # P-complete, and hence, at least as hard as NP-complete problems. Included are important problems in network reliability analysis, namely, computing the probability that a graph is connected and counting the number of minimum cardinality $(s,t)$-cuts or directed network cuts. Also shown to be # P-complete are counting vertex covers in a bipartite graph, counting antichains in a partial order, and approximating the probability that a graph is connected and the probability that a pair of vertices is connected.
---
paper_title: Stable matching with preferences derived from a psychological model

paper_content:

We study a special case of the Stable Roommates problem in which preferences are derived from a psychological model common in social choice literature. When preferences are 'single-peaked' and 'narcissistic', there exists a unique stable matching, and it can be constructed in O(n) time. We also show how to recognize quickly, when a set of preferences is single-peaked.
---
paper_title: The weak Bruhat order of σ consistent sets, and Catalan numbers

paper_content:

Chains in the weak Bruhat order$\beta $ of $\text{S}_\Sigma $ (the symmetric group on $\Sigma $) belong to the class of subsets of $\text{S}_\Sigma $ over which unrestricted choice necessarily produces transitive relations under pairwise simple majority vote (consistent sets). If for $\text{A} \subset \text{S}_\Sigma $ we let $\text{T}( \text{A} ) \equiv \cup _{\text{p} \in \text{A}} \text{T} ( \text{p} )$ where $\text{T}( \text{p} ) = \{ ( \text{p}_{\text{i}} , \text{p}_{\text{j}} ,\text{p}_{\text{k}} )| \text{i} < \text{j} < \text{k} \}$ and $\Psi ( \text{A} ) \equiv \{ \text{w} \in \text{S}_\Sigma \mid \text{T} ( \text{w} ) \subset \text{T} ( \text{A} ) \}$ the following theorem (among others) is obtained.Theorem. For all${\text{q}} \in {\text{S}}_\Sigma $, if${\text{A}}$is a saturated chain under$\beta $ then $\Psi ( {\text{qA}} )$is an upper semimodular sublattice of cardinality$|\Psi ( {{\text{qA}}} )|\leqq \frac{1}{{|\Sigma | + 1}} (\begin{smallmatrix} 2|\Sigma | \\ |\Sigma | \end{smallmatrix}) \eq...
---
paper_title: Decision theory and discrete mathematics

paper_content:

Abstract This paper discusses recent developments that emphasize the role of discrete mathematics in decision theory. It focuses on three topics which illustrate this role. The first is the transitive simple majorities problem of determining the maximum number of linear orders on n candidates that prevent the occurrence of cyclic majorities when voters' preferences are confined to those orders. The second involves the varieties of unique solutions to simple systems of n — 1 linearly independent homogeneous linear equations in n variables of types that arise from qualitative equivalence comparisons in the measurement of subjective probabilities and utility differences. The third topic describes a computer-efficient hierarchy of stochastic-dominance relations for comparisons of risky alternatives whose outcomes lie in a unidimensional set of evenly spaced points. Although the paper is primarily expository, new results and new conjectures are included.
---
paper_title: Acyclic Sets of Linear Orders via the Bruhat Orders

paper_content:

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.
---
paper_title: A polynomial time algorithm for unidimensional unfolding representations

paper_content:

Abstract Two conditions on a collection of simple orders - unimodality and straightness - are necessary but not jointly sufficient for unidimensional unfolding representations. From the analysis of these conditions, a polynomial time algorithm is derived for the testing of unidimensionality and for the construction of a representation when one exists.
---
paper_title: Acyclic sets of linear orders: A progress report

paper_content:

Let f(n) be the maximum cardinality of an acyclic set of linear orders on {1, 2, … , n}. It is known that f(3)=4, f(4)=9, f(5)=20, and that all maximum-cardinality acyclic sets for n≤ 5 are constructed by an “alternating scheme”. We outline a proof that this scheme is optimal for n=6, where f (6)=45. It is known for large n that f (n) >(2.17)n and that no maximum-cardinality acyclic set conforms to the alternating scheme. Ran Raz recently proved that f (n) 0 and all n. We conjecture that f (n + m)≤f (n + 1) f (m + 1) for n , m≥ 1, which would imply f (n)<(2.591)n − 2 for all large n.
---

Title: Acyclic Domains of Linear Orders: A Survey

Section 1: Notations and preliminaries
Description 1: This section introduces the basic notations and concepts used throughout the paper, including definitions of alternatives, linear orders, and combinatorial constructs relevant to acyclic domains.

Section 2: Remark
Description 2: Explanation of the chosen notation and its alignment with poset theory conventions, as well as an introduction to majority rule and its historical context.

Section 3: The beginnings: small maximal acyclic domains
Description 3: A historical overview of initial discoveries in the field, discussing small-scale maximal acyclic domains such as Black's single-peaked preferences.

Section 4: Abello's work
Description 4: Detailed exploration of Abello’s contributions including his use of the weak Bruhat order and the permutoèdre lattice to construct maximal connected acyclic domains.

Section 5: Chameni-Nembua's work
Description 5: Examination of Chameni-Nembua’s findings, focusing on the distributive lattice structure of certain acyclic domains and their connections to the permutoèdre lattice.

Section 6: Fishburn's and Craven's works
Description 6: Analysis of Fishburn and Craven’s significant results, including iterative constructions and replacement schemes to find large acyclic domains, along with relevant conjectures.

Section 7: Galambos and Reiner's work
Description 7: Presentation of Galambos and Reiner’s unification of known results and their advancements in computing bounds for acyclic domains using lattice theory.

Section 8: Conclusion
Description 8: Summarization of key findings, remaining challenges in the field, and noteworthy algorithmic and theoretical problems. Includes final remarks and conjectures proposed by the authors.