Acyclic sets of linear orders: A progress report

Let f(n) be the maximum cardinality of an acyclic set of linear orders on {1, 2, … , n}. It is known that f(3)=4, f(4)=9, f(5)=20, and that all maximum-cardinality acyclic sets for n≤ 5 are constructed by an “alternating scheme”. We outline a proof that this scheme is optimal for n=6, where f (6)=45. It is known for large n that f (n) >(2.17)ⁿ and that no maximum-cardinality acyclic set conforms to the alternating scheme. Ran Raz recently proved that f (n)<c ⁿ for some c>0 and all n. We conjecture that f (n + m)≤f (n + 1) f (m + 1) for n , m≥ 1, which would imply f (n)<(2.591)^{n − 2} for all large n. Received: 12 April 2000/Accepted: 4 December 2000