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

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

Offset: 1

Author

N. J. A. Sloane, Feb 07 2009

Keywords

• nonn
• hard
• more

Comments

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]

References

• 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.

Links

• 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⟩.

Crossrefs

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

Extensions

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