Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%I #36 Mar 02 2024 03:00:11
%S 1,2,4,9,20,45,100
%N Maximal size of a connected acyclic domain of permutations of n elements with diameter n*(n-1)/2.
%C 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]
%D 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.
%H James Abello, <a href="https://doi.org/10.1137/0404001">The Weak Bruhat Order of S_Sigma, Consistent Sets, and Catalan Numbers</a>, SIAM Journal on Discrete Mathematics, 4 (1991), 1-16; <a href="http://www.mgvis.com/Papers/Comb_Alg_Comp/bruhat.pdf">alternative link</a>.
%H James Abello, <a href="http://www.mgvis.com/Papers/MajorityRuleAbello.pdf">The Majority Rule and Combinatorial Geometry (via the Symmetric Group)</a>, Annales Du Lamsade, 3 (2004), 1-13.
%H Vladimir I. Danilov, Alexander V. Karzanov, and Gleb Koshevoy, <a href="https://arxiv.org/abs/1011.2888">Condorcet domains of tiling type</a>, Discrete Applied Mathematics 160.7-8 (2012), pages 933-940.
%H Stefan Felsner and Pavel Valtr, <a href="http://page.math.tu-berlin.de/~felsner/Paper/new-pla.pdf">Coding and counting arrangements of pseudolines</a>, Discrete & Computational Geometry 46.3 (2011), pages 405-416.
%H Alexander Karpov and Arkadii Slinko, <a href="https://doi.org/10.1007/s11238-022-09878-9">Constructing large peak-pit Condorcet domains</a>, Theory and Decision, 94 (2023), 97-120.
%H B. Monjardet, <a href="https://halshs.archives-ouvertes.fr/halshs-00198635">Acyclic domains of linear orders: a survey</a>, 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⟩.
%Y Cf. A090245 (has same initial terms but probably is unrelated), A144685, A144687, A369614.
%K nonn,hard,more
%O 1,2
%A _N. J. A. Sloane_, Feb 07 2009
%E a(1)-a(2) added and name edited by _Andrey Zabolotskiy_, Dec 31 2023