LARGEST MINIMAL INVERSION-COMPLETE AND PAIR-COMPLETE SETS OF PERMUTATIONS

We solve two related extremal problems in the theory of permutations.A set $Q$ of permutations of the integers 1 to $n$ is inversion-complete (resp., pair-complete)if for every inversion $(j,i)$, where $1 \le i < j \le n$, (resp., for every pair $(i,j)$, where $i\not= j$)there exists a permutation in~$Q$ where $j$ is before~$i$.It is minimally inversion-complete if in addition no proper subset of~$Q$ 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, andthat of a minimal pair-complete set of permutations.The latter problem arises in the determination of the Carath\'eodory numbers forcertain abstract convexity structures on the $(n-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 andwe 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 $n \ge 4$