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 <= i < j <= n (resp., for every pair (i<> j), where i 6= 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 Caratheodory numbers for certain abstract convexity structures on the (n1)-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 when ever n>=4.
Largest minimally inversion-complete and pair-complete sets of permutations / Balandraud, Eric; Queyranne, Maurice; Tardella, Fabio. - In: COMBINATORICA. - ISSN 0209-9683. - STAMPA. - 38:1(2018), pp. 29-41. [10.1007/s00493-016-3426-6]
Largest minimally inversion-complete and pair-complete sets of permutations
TARDELLA, Fabio
2018
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 1 <= i < j <= n (resp., for every pair (i<> j), where i 6= 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 Caratheodory numbers for certain abstract convexity structures on the (n1)-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 when ever n>=4.File | Dimensione | Formato | |
---|---|---|---|
Tardella_Largest-minimal-Preprint_2018.pdf
accesso aperto
Note: Articolo caricato sul server arXiv
Tipologia:
Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
176.38 kB
Formato
Adobe PDF
|
176.38 kB | Adobe PDF | |
Tardella_Largest-minimal_2018.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
397.56 kB
Formato
Adobe PDF
|
397.56 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.