Title of article :
Reverse-free codes and permutations
Author/Authors :
Füredi، نويسنده , , Zoltلn and Kantor، نويسنده , , Ida and Monti، نويسنده , , Angelo and Sinaimeri، نويسنده , , Blerina Xhabli، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2011
Pages :
5
From page :
383
To page :
387
Abstract :
Two codewords ( a 1 , … , a k ) and ( b 1 , … , b k ) form a reverse-free pair if ( a i , a j ) ≠ ( b j , b i ) holds whenever 1 ⩽ i < j ⩽ k are indices such that a i ≠ a j . In a reverse-free code, each pair of codewords is reverse-free. The maximum size of a reverse-free code with codewords of length k and an n-element alphabet is denoted by F ¯ ( n , k ) . Let F ( n , k ) denote the maximum size of a reverse-free code with all codewords consisting of distinct entries. ermine F ¯ ( n , 3 ) and F ¯ ( n , 3 ) exactly whenever n is a power of 3, and asymptotically for other values of n. We prove non-trivial bounds for F ( n , k ) and F ¯ ( n , k ) for general k and for other related functions as well. Using VC-dimension of a matrix, we determine the order of magnitude of F ¯ ( n , k ) for n fixed and k tending to infinity.
Keywords :
extremal combinatorics , Permutations , codes , reverse-free
Journal title :
Electronic Notes in Discrete Mathematics
Serial Year :
2011
Journal title :
Electronic Notes in Discrete Mathematics
Record number :
1455850
Link To Document :
بازگشت