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...
Saved in:
| Main Authors: | , |
|---|---|
| Other Authors: | |
| 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 |
| Summary: | 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. |
|---|