A144687 -id:A144687 - cp's OEIS frontend

A369614 Maximal size of Condorcet domain on n alternatives.

1, 1, 2, 4, 9, 20, 45, 100, 224

Offset: 0

Andrey Zabolotskiy, Jan 27 2024

A Condorcet domain is a set D of permutations of [n] such that for any i, j, k from [n] there do not exist three permutations in D in which i, j, k are ordered in all three different cyclic permutations of the order (i, j, k). If these permutations are interpreted as voters' preferences, this condition prevents the Condorcet effect.

Condorcet domains are also known as acyclic domains, acyclic sets of linear orders, consistent profiles, or consistent sets.

			For n <= 2, the set of all n! permutations is a Condorcet domain.
For n = 3, an example of a Condorcet domain of maximal size is the following set of permutations:
  123
  213
  231
  321
For n = 4, an example of a Condorcet domain of maximal size is:
  1234
  1324
  1342
  3124
  3142
  3412
  3421
  4312
  4321

Dolica Akello-Egwell, Charles Leedham-Green, Alastair Litterick, Klas Markström and Søren Riis, Condorcet Domains of Degree at most Seven, arXiv:2306.15993 [cs.DM], 2023. See the website presenting all maximal unitary Condorcet domains on 4, 5, 6, 7 alternatives.
Clemens Puppe and Arkadii Slinko, Maximal Condorcet domains: A further progress report, KIT Working Paper Series in Economics, 159 (2022).
Charles Leedham-Green, Klas Markström and Søren Riis, The largest Condorcet domain on 8 alternatives, Soc. Choice Welf., 62 (2024), 109-116.
Bernard Monjardet, Acyclic domains of linear orders: a survey, in "The Mathematics of Preference, Choice and Order: Essays in Honor of Peter Fishburn", edited by Steven Brams, William V. Gehrlein and Fred S. Roberts, Springer, 2009, pp. 139-160; preprint: halshs-00198635.
Wikipedia, Condorcet paradox.

Cf. A144685 (size of Fishburn's alternating domain), A144686 (maximal size of Condorcet domain containing a maximal chain), A144687, A289684.

A144686 Maximal size of a connected acyclic domain of permutations of n elements with diameter n*(n-1)/2.

Original entry on oeis.org

1, 2, 4, 9, 20, 45, 100

Offset: 1

N. J. A. Sloane, Feb 07 2009

a(n) is at most 2.487^n and at least 2.076^n for large enough n (see Felsner & Valtr). Originally conjectured to equal A144685, but in fact a(n) is asymptotically larger and exceeds A144685 at least for n >= 34 (see Karpov & Slinko). - Clayton Thomas, Aug 19 2019 [Updated by Andrey Zabolotskiy, Dec 31 2023]

B. Monjardet, Acyclic domains of linear orders: a survey, in "The Mathematics of Preference, Choice and Order: Essays in Honor of Peter Fishburn", edited by Steven Brams, William V. Gehrlein and Fred S. Roberts, Springer, 2009, pp. 139-160.

James Abello, The Weak Bruhat Order of S_Sigma, Consistent Sets, and Catalan Numbers, SIAM Journal on Discrete Mathematics, 4 (1991), 1-16; alternative link.
James Abello, The Majority Rule and Combinatorial Geometry (via the Symmetric Group), Annales Du Lamsade, 3 (2004), 1-13.
Vladimir I. Danilov, Alexander V. Karzanov, and Gleb Koshevoy, Condorcet domains of tiling type, Discrete Applied Mathematics 160.7-8 (2012), pages 933-940.
Stefan Felsner and Pavel Valtr, Coding and counting arrangements of pseudolines, Discrete & Computational Geometry 46.3 (2011), pages 405-416.
Alexander Karpov and Arkadii Slinko, Constructing large peak-pit Condorcet domains, Theory and Decision, 94 (2023), 97-120.
B. Monjardet, Acyclic domains of linear orders: a survey, in "The Mathematics of Preference, Choice and Order: Essays in Honor of Peter Fishburn", edited by Steven Brams, William V. Gehrlein and Fred S. Roberts, Springer, 2009, pp. 139-160 ⟨halshs-00198635⟩.

Cf. A090245 (has same initial terms but probably is unrelated), A144685, A144687, A369614.

a(1)-a(2) added and name edited by Andrey Zabolotskiy, Dec 31 2023

cp's OEIS Frontend

A369614 Maximal size of Condorcet domain on n alternatives.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs