cp's OEIS Frontend

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

%I A144686 #36 Mar 02 2024 03:00:11
%S A144686 1,2,4,9,20,45,100
%N A144686 Maximal size of a connected acyclic domain of permutations of n elements with diameter n*(n-1)/2.
%C A144686 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 A144686 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 A144686 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 A144686 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 A144686 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 A144686 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 A144686 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 A144686 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 A144686 Cf. A090245 (has same initial terms but probably is unrelated), A144685, A144687, A369614.
%K A144686 nonn,hard,more
%O A144686 1,2
%A A144686 _N. J. A. Sloane_, Feb 07 2009
%E A144686 a(1)-a(2) added and name edited by _Andrey Zabolotskiy_, Dec 31 2023