Please use this identifier to cite or link to this item:
https://hdl.handle.net/10356/92189
Title: | A note on the stability number of an orthogonality graph | Authors: | Klerk, Etienne de. Pasechnik, Dmitrii V. |
Keywords: | DRNTU::Science::Mathematics::Geometry | Issue Date: | 2006 | Source: | Klerk, E. D., & Pasechnik, D. V. (2006). A note on the stability number of an orthogonality graph. European Journal of Combinatorics, 28, 1971-1979. | Series/Report no.: | European journal of combinatorics | 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 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. | URI: | https://hdl.handle.net/10356/92189 http://hdl.handle.net/10220/6870 |
DOI: | 10.1016/j.ejc.2006.08.011 | Schools: | School of Physical and Mathematical Sciences | Rights: | © 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. | Fulltext Permission: | open | Fulltext Availability: | With Fulltext |
Appears in Collections: | SPMS Journal Articles |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
6. A note on the stability number of an orthogonality graph.pdf | 186.22 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
20
12
Updated on Mar 18, 2024
Web of ScienceTM
Citations
20
10
Updated on Oct 27, 2023
Page view(s) 5
989
Updated on Mar 18, 2024
Download(s) 10
355
Updated on Mar 18, 2024
Google ScholarTM
Check
Altmetric
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.