首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Codes And Xor Graph Products
Authors:Noga?Alon  Eyal?Lubetzky?
Institution:(1) Schools of Mathematics and Computer Science, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, 69978, Israel;(2) Department of Computer Science, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, 69978, Israel
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). * Research supported in part by a USA-Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. † Research partially supported by a Charles Clore Foundation Fellowship.
Keywords:05C69  94A15
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号