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 / Zoltan, Furedi; Ida, Kantor; 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
MONTI, Angelo;SINAIMERI, BLERINA
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
