Title :
Superimposed codes are almost big distance ones
Author :
Füredi, Zoltán ; Ruszinkó, Miklòs
Author_Institution :
Dept. of Math., Illinois Univ., Urbana, IL, USA
fDate :
29 Jun-4 Jul 1997
Abstract :
Let T(r,n) denote the maximum number of subsets of an n-set satisfying the condition that no set is covered by the union of r others, while let T*(ε,n) be the maximum size of a <ε part intersecting family, i.e. of a family where the size of the intersection of any two sets is < than the εth part of the smaller one. By partially answering to a question posed by Hwang and Sos (1987), we prove, that superimposed codes (r-cover-free families) are large distance ones (almost <1/r part intersecting families). More precisely, our theorem says that the rate of an r-cover-free family is ⩽ than the rate of a loglogr/r part intersecting family, i.e. for n>n0(r)logT(r,n)/n⩽logT*(loglogr/r,n)/n
Keywords :
binary sequences; group theory; binary codes; intersecting family; large distance codes; maximum size; r-cover-free families; subsets; superimposed codes; union; Artificial intelligence; Binary codes; Compression algorithms; Information theory; Testing;
Conference_Titel :
Information Theory. 1997. Proceedings., 1997 IEEE International Symposium on
Conference_Location :
Ulm
Print_ISBN :
0-7803-3956-8
DOI :
10.1109/ISIT.1997.613033