A note on the stability number of an orthogonality graph

E. de Klerk; D. V. Pasechnik

doi:10.1016/j.ejc.2006.08.011

A note on the stability number of an orthogonality graph

E. de Klerk^*, D. V. Pasechnik

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

12 Scopus citations

Abstract

We consider the orthogonality graph Ω (n) with 2ⁿ vertices corresponding to the vectors {0, 1}ⁿ, two vertices adjacent if and only if the Hamming distance between them is n / 2. We show that, for n = 16, the stability number of Ω (n) is α (Ω (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/SimulationOf Entanglement.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-2866]. 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 Ω (n) the latter two bounds are equal to 2ⁿ / n.

Original language	English (US)
Pages (from-to)	1971-1979
Number of pages	9
Journal	European Journal of Combinatorics
Volume	28
Issue number	7 SPEC. ISS.
DOIs	https://doi.org/10.1016/j.ejc.2006.08.011
State	Published - Oct 2007
Externally published	Yes

Funding

The first author is supported by the Netherlands Organisation for Scientific Research grant NWO 613.000.214 as well as the NSERC grant 283331 - 04. Part of this research was performed while on leave from the Department of Combinatorics and Optimization, University of Waterloo.

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.ejc.2006.08.011

Cite this

@article{4f969d0722e84cf181c857197b4468ee,

title = "A note on the stability number of an orthogonality graph",

abstract = "We consider the orthogonality graph Ω (n) with 2n vertices corresponding to the vectors {0, 1}n, two vertices adjacent if and only if the Hamming distance between them is n / 2. We show that, for n = 16, the stability number of Ω (n) is α (Ω (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/SimulationOf Entanglement.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-2866]. 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 Ω (n) the latter two bounds are equal to 2n / n.",

author = "{de Klerk}, E. and Pasechnik, {D. V.}",

year = "2007",

month = oct,

doi = "10.1016/j.ejc.2006.08.011",

language = "English (US)",

volume = "28",

pages = "1971--1979",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

number = "7 SPEC. ISS.",

}

TY - JOUR

T1 - A note on the stability number of an orthogonality graph

AU - de Klerk, E.

AU - Pasechnik, D. V.

PY - 2007/10

Y1 - 2007/10

N2 - We consider the orthogonality graph Ω (n) with 2n vertices corresponding to the vectors {0, 1}n, two vertices adjacent if and only if the Hamming distance between them is n / 2. We show that, for n = 16, the stability number of Ω (n) is α (Ω (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/SimulationOf Entanglement.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-2866]. 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 Ω (n) the latter two bounds are equal to 2n / n.

AB - We consider the orthogonality graph Ω (n) with 2n vertices corresponding to the vectors {0, 1}n, two vertices adjacent if and only if the Hamming distance between them is n / 2. We show that, for n = 16, the stability number of Ω (n) is α (Ω (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/SimulationOf Entanglement.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-2866]. 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 Ω (n) the latter two bounds are equal to 2n / n.

UR - http://www.scopus.com/inward/record.url?scp=34447282009&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34447282009&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2006.08.011

DO - 10.1016/j.ejc.2006.08.011

M3 - Article

AN - SCOPUS:34447282009

SN - 0195-6698

VL - 28

SP - 1971

EP - 1979

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

IS - 7 SPEC. ISS.

ER -

A note on the stability number of an orthogonality graph

Abstract

Funding

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this