Largest minimally inversion-complete and pair-complete sets of permutations.
(2015) , 10 pages
Files
Details
- Authors
- Abstract
- We solve two related extremal problems in the theory of permutations. A set π of permutations of the integers 1 to π is inversion-complete (resp., pair-complete) if for every inversion (π, π), where 1 β€ π < π β€ π, (resp., for every pair (π, π), where π β π) there exists a permutation in π where π is before π. It is minimally inversion-complete if in addition no proper subset of π is inversion-complete; and similarly for pair completeness. The problems we consider are to determine the maximum cardinality of a minimal inversion-complete set of permutations, and that of a minimal pair-complete set of permutations. The latter problem arises in the determination of the CarathΓ©odory numbers for certain abstract convexity structures on the (π β 1)-dimensional real and integer vector spaces. Using Mantel's Theorem on the maximum number of edges in a triangle-free graph, we determine these two maximum cardinalities and we present a complete description of the optimal sets of permutations for each problem. Perhaps surprisingly (since there are twice as many pairs to cover as inversions), these two maximum cardinalities coincide whenever π β₯ 4.
- Affiliations
Citations
Balandraud, E., Queyranne, M., & Tardella, F. (2015). Largest minimally inversion-complete and pair-complete sets of permutations. (CORE Discussion Paper 2015/09). https://hdl.handle.net/2078.5/192339