Name
Abstract | ||
|---|---|---|
What is the maximum possible number, f3(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, g3(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 f3(n) = Θ(2n) whereas g3(n)=Θ(n). |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/s00493-007-0042-5 | Combinatorica |
Keywords | Field | DocType |
special case,hamming distance,maximum possible number,clique number,new parameter,length n,xor graph products,independence number,parameters denote limit,xor power,graph g. | Discrete mathematics,Graph,Clique number,Combinatorics,Normalization (statistics),Clique,Infinity,Hamming distance,Mathematics,Hamming graph,Special case | Journal |
Volume | Issue | ISSN |
27 | 1 | 0209-9683 |
Citations | PageRank | References |
1 | 0.38 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Noga Alon | 1 | 10468 | 1688.16 |
| Eyal Lubetzky | 2 | 355 | 28.87 |