A note on the stability number of an orthogonality graph.

DSpace/Manakin Repository


Search DR-NTU

Advanced Search Subject Search


My Account

A note on the stability number of an orthogonality graph.

Show simple item record

dc.contributor.author Klerk, Etienne de.
dc.contributor.author Pasechnik, Dmitrii V.
dc.date.accessioned 2011-07-06T03:35:01Z
dc.date.available 2011-07-06T03:35:01Z
dc.date.copyright 2006
dc.date.issued 2011-07-06T03:35:01Z
dc.identifier.citation Klerk, E. D., & Pasechnik, D. V. (2006). A note on the stability number of an orthogonality graph. European Journal of Combinatorics, 28, 1971-1979.
dc.identifier.uri http://hdl.handle.net/10220/6870
dc.description.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.
dc.format.extent 10 p.
dc.language.iso en
dc.relation.ispartofseries European journal of combinatorics
dc.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.
dc.subject DRNTU::Science::Mathematics::Geometry.
dc.title A note on the stability number of an orthogonality graph.
dc.type Journal Article
dc.contributor.school School of Physical and Mathematical Sciences
dc.identifier.doi http://dx.doi.org/10.1016/j.ejc.2006.08.011
dc.description.version Accepted version

Files in this item

Files Size Format View
6. A note on t ... an orthogonality graph.pdf 190.6Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record


Total views

All Items Views
A note on the stability number of an orthogonality graph. 491

Total downloads

All Bitstreams Views
6. A note on the stability number of an orthogonality graph.pdf 167

Top country downloads

Country Code Views
United States of America 92
China 13
Singapore 11
Saudi Arabia 7
France 5

Top city downloads

city Views
Mountain View 60
Singapore 11
Redmond 5
Southampton 4
Tehran 4