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)<Superscript>n</Superscript> and that no maximum-cardinality acyclic set conforms to the alternating scheme. Ran Raz recently proved that f (n)>c <Superscript>n</Superscript> 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)<Superscript>n − 2</Superscript> for all large n. Copyright Springer-Verlag Berlin Heidelberg 2002
Year of publication: |
2002
|
---|---|
Authors: | Fishburn, Peter C. |
Published in: |
Social Choice and Welfare. - Springer. - Vol. 19.2002, 2, p. 431-447
|
Publisher: |
Springer |
Saved in:
Online Resource
Saved in favorites
Similar items by person
-
Brams, Steven J., (2021)
-
When is size a liability? : Bargaining power in minimal winning coalitions
Brams, Steven J., (1994)
-
The responsiveness of approval voting : comments on Saari and Van Newenhizen
Brams, Steven J., (1987)
- More ...