Codes and Xor graph products

被引:5
作者
Alon, Noga [1 ]
Lubetzky, Eyal
机构
[1] Tel Aviv Univ, Raymond & Beverly Sackler Fac Exact Sci, Sch Math & Comp Sci, IL-69978 Tel Aviv, Israel
[2] Tel Aviv Univ, Raymond & Beverly Sackler Fac Exact Sci, Dept Comp Sci, IL-69978 Tel Aviv, Israel
基金
以色列科学基金会;
关键词
05C69; 94A15;
D O I
10.1007/s00493-007-0042-5
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
What is the maximum possible number, f(3)(n), of vectors of length n over {0,1,2} such that the Hamming distance between every two is even? What is the maximum possible number, g(3)(n), of vectors in {0,1,2} n such that the Hamming distance between every two is odd? We investigate these questions, and more general ones, by studying Xor powers of graphs, focusing on their independence number and clique number, and by introducing two new parameters of a graph G. Both parameters denote limits of series of either clique numbers or independence numbers of the Xor powers of G ( normalized appropriately), and while both limits exist, one of the series grows exponentially as the power tends to infinity, while the other grows linearly. As a special case, it follows that f(3)(n) = theta(2(n)) whereas g(3)(n) = theta(n).
引用
收藏
页码:13 / 33
页数:21
相关论文
共 13 条
[1]   Graph products, Fourier analysis and spectral techniques [J].
Alon, N ;
Dinur, I ;
Friedgut, E ;
Sudakov, B .
GEOMETRIC AND FUNCTIONAL ANALYSIS, 2004, 14 (05) :913-940
[2]   REPEATED COMMUNICATION AND RAMSEY GRAPHS [J].
ALON, N ;
ORLITSKY, A .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1995, 41 (05) :1276-1289
[3]  
Alon N., 2004, The probabilistic method
[4]  
Erdo P., 1962, Magyar Tud. Akad. Mat. Kutato Int. Kozl, VA3, P459
[5]   2-COLORINGS OF COMPLETE GRAPHS WITH A SMALL NUMBER OF MONOCHROMATIC K(4) SUBGRAPHS [J].
FRANEK, F ;
RODL, V .
DISCRETE MATHEMATICS, 1993, 114 (1-3) :199-203
[6]  
Godsil C., 2001, GRADUATE TEXT MATH, V207
[7]  
Hoffman A. J., 1970, GRAPH THEORY ITS APP, P79, DOI DOI 10.1142/97898127969360041
[8]   PRIMES IN SHORT INTERVALS [J].
IWANIEC, H ;
PINTZ, J .
MONATSHEFTE FUR MATHEMATIK, 1984, 98 (02) :115-143
[9]   ON THE SHANNON CAPACITY OF A GRAPH [J].
LOVASZ, L .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1979, 25 (01) :1-7
[10]  
Mac Williams F., 1977, THEORY ERROR CORRECT