Largest minimal inversion-complete and pair-complete sets of permutations

DOI10.1007/S00493-016-3426-6MaRDI QIDQ1747991zbMATH OpenOpenAlexFDO

Authors Maurice Queyranne, Fabio Tardella, Éric Balandraud

Publication date 27 April 2018

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.00228

zbMATH Keywords

permutationMantel's theoreminversion-completeoptimal set of permutationspair-complete

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Extremal combinatorics (05D99)

Abstract: 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 $1leiextlessjlen$, (resp., for every pair $(i,j)$, where $iot=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, and that of a minimal pair-complete set of permutations. The latter problem arises in the determination of the Carath'eodory numbers for certain 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 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 $nge4$.

Recommendations

• Extremal problems on permutations under cyclic equivalence
• On the maximum number of permutations with given maximal or minimal distance
• The maximal-inversion statistic and pattern-avoiding permutations
• The maximum cardinality of minimal inversion complete sets in finite reflection groups
• scientific article; zbMATH DE number 861420

Cites work

• scientific article; zbMATH DE number 439012 (Why is no real title available?)
• Combinatorics of permutations
• Discrete Convex Analysis
• Minimal scrambling sets of simple orders
• Permutation lattices revisited
• Suitable permutations, binary covering arrays, and Paley matrices
• The maximum cardinality of minimal inversion complete sets in finite reflection groups

Cited in

(5)

• Suitable sets of permutations, packings of triples, and Ramsey's theorem
• Minimal inversion complete sets and maximal abelian ideals
• scientific article; zbMATH DE number 861420 (Why is no real title available?)
• The largest and the smallest fixed points of permutations
• The maximum cardinality of minimal inversion complete sets in finite reflection groups

This page was built for publication: Largest minimal inversion-complete and pair-complete sets of permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1747991)