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.
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 Dimensione Formato  
SIAM_DM10.pdf

Solo gestori archivio

Tipologia: Versione dell'editore
Licenza: DRM non definito
Dimensione 221.03 kB
Formato Adobe PDF
221.03 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11385/202523
Citazioni
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 9
social impact