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,2

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

Table of n, a(n) for n=1..7.

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.

Sequence in context: A219229 A091620 A208738 * A108469 A085584 A369614

Adjacent sequences: A144683 A144684 A144685 * A144687 A144688 A144689

Keyword

nonn,hard,more

Author

N. J. A. Sloane, Feb 07 2009

Extensions

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

Status

approved