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) &gt; 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

#### 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.
##### Scheda breve Scheda completa Scheda completa (DC)
extremal combinatorics; ordered triples; permutations
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]
File in questo prodotto:
File
SIAM_DM10.pdf

Solo gestori archivio

Tipologia: Versione dell'editore
Licenza: DRM non definito
Dimensione 221.03 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11385/202523`