A note on the stability number of an orthogonality graph

作者：de Klerk E^*; Pasechnik D V

来源：European Journal of Combinatorics, 2007, 28(7): 1971-1979.

DOI：10.1016/j.ejc.2006.08.011

We consider the orthogonality graph Omega(n) with 2 '' vertices corresponding to the vectors {10, 1}'', two vertices adjacent if and only if the Hamming distance between them is 11/2. We show that, for n = 16, the stability number of S?(n) is a(S?(16)) = 2304, thus proving a conjecture of V. Galliard [Classical pseudo telepathy and coloring graphs, Diploma Thesis, ETH Zurich, 2001. Available at http://math.galliard.ch/Cryptography/Papers/PseudoTelepathy/SimulationOfEntanglement.pdf]. The main tool we employ is a recent semidefinite programming relaxation for minimal distance binary codes due to A. Schrijver [New code upper bounds from the Terwilliger algebra, IEEE Trans. Inform. Theory 51 (8) (2005) 2859-28661. Also, we give a general condition for a Delsarte bound on the (co)cliques in graphs of relations of association schemes to coincide with the ratio bound, and use it to show that for S?(n) the latter two bounds are equal to 2 ''/n.

• 出版日期2007-10
• 单位南阳理工学院