A note on the stability number of an orthogonality graph

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 by Galliard [Classical p...

Full description

Saved in:
Bibliographic Details
Main Authors: Klerk, Etienne de., Pasechnik, Dmitrii V.
Other Authors: School of Physical and Mathematical Sciences
Format: Article
Language:English
Published: 2011
Subjects:
Online Access:https://hdl.handle.net/10356/92189
http://hdl.handle.net/10220/6870
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-92189
record_format dspace
spelling sg-ntu-dr.10356-921892023-02-28T19:32:28Z A note on the stability number of an orthogonality graph Klerk, Etienne de. Pasechnik, Dmitrii V. School of Physical and Mathematical Sciences DRNTU::Science::Mathematics::Geometry 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 by 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 Schrijver [New code upper bounds from the Terwilliger algebra, IEEE Trans. Inform. Theory 51 (8) (2005) 2859–2866]. As well, we give a general condition for Delsarte bound on the (co)cli¬ques 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. Accepted version 2011-07-06T03:35:01Z 2019-12-06T18:18:56Z 2011-07-06T03:35:01Z 2019-12-06T18:18:56Z 2006 2006 Journal Article Klerk, E. D., & Pasechnik, D. V. (2006). A note on the stability number of an orthogonality graph. European Journal of Combinatorics, 28, 1971-1979. https://hdl.handle.net/10356/92189 http://hdl.handle.net/10220/6870 10.1016/j.ejc.2006.08.011 en European journal of combinatorics © 2006 Elsevier. This is the author created version of a work that has been peer reviewed and accepted for publication by European Journal of Combinatorics, Elsevier. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at the following DOI: http://dx.doi.org/10.1016/j.ejc.2006.08.011. 10 p. application/pdf
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic DRNTU::Science::Mathematics::Geometry
spellingShingle DRNTU::Science::Mathematics::Geometry
Klerk, Etienne de.
Pasechnik, Dmitrii V.
A note on the stability number of an orthogonality graph
description 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 by 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 Schrijver [New code upper bounds from the Terwilliger algebra, IEEE Trans. Inform. Theory 51 (8) (2005) 2859–2866]. As well, we give a general condition for Delsarte bound on the (co)cli¬ques 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.
author2 School of Physical and Mathematical Sciences
author_facet School of Physical and Mathematical Sciences
Klerk, Etienne de.
Pasechnik, Dmitrii V.
format Article
author Klerk, Etienne de.
Pasechnik, Dmitrii V.
author_sort Klerk, Etienne de.
title A note on the stability number of an orthogonality graph
title_short A note on the stability number of an orthogonality graph
title_full A note on the stability number of an orthogonality graph
title_fullStr A note on the stability number of an orthogonality graph
title_full_unstemmed A note on the stability number of an orthogonality graph
title_sort note on the stability number of an orthogonality graph
publishDate 2011
url https://hdl.handle.net/10356/92189
http://hdl.handle.net/10220/6870
_version_ 1759852922550616064