A set F of ordered k-tuples of distinct elements of an n-set is pairwise reverse free if it does not contain two ordered k-tuples with the same pair of elements in the same pair of coordinates in reverse order. Let F(n, k) be the maximum size of a pairwise reverse-free set. In this paper we focus on the case of 3-tuples and prove limF(n, 3)/(n/3) = 5/4, more exactly, 5/14n 3 - 1/2n 2 - O(nlogn) > F(n, 3) ≥ 5/24 n 3 - 1/2n 2 + 5/8n, and here equality holds when n is a power of 3. Many problems remain open. © 2010 Societ y for Industrial and Applied Mathematics.
On reverse-free codes and permutations / Furedi, Zoltan; Kantor, Ida; Monti, Angelo; Sinaimeri, Blerina. - In: SIAM JOURNAL ON DISCRETE MATHEMATICS. - ISSN 0895-4801. - 24:3(2010), pp. 964-978. [10.1137/090774835]
On reverse-free codes and permutations
Blerina Sinaimeri
2010
Abstract
A set F of ordered k-tuples of distinct elements of an n-set is pairwise reverse free if it does not contain two ordered k-tuples with the same pair of elements in the same pair of coordinates in reverse order. Let F(n, k) be the maximum size of a pairwise reverse-free set. In this paper we focus on the case of 3-tuples and prove limF(n, 3)/(n/3) = 5/4, more exactly, 5/14n 3 - 1/2n 2 - O(nlogn) > F(n, 3) ≥ 5/24 n 3 - 1/2n 2 + 5/8n, and here equality holds when n is a power of 3. Many problems remain open. © 2010 Societ y for Industrial and Applied Mathematics.
| File | Dimensione | Formato | |
|---|---|---|---|
|
SIAM_DM10.pdf
Solo gestori archivio
Tipologia:
Versione dell'editore
Licenza:
DRM (Digital rights management) non definiti
Dimensione
221.03 kB
Formato
Adobe PDF
|
221.03 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
