A note on the stability number of an orthogonality graph

Details A note on the stability number of an orthogonality graph A note on the stability number of an orthogonality graph

2005-05-02

arxiv.org/abs/math/0505038v3

European Journal of Combinatorics 28(2007) 1971-1979

Mathematics

Combinatorics

10 pages, LaTeX, 1 figure, companion Matlab code. Misc. misprints fixed and references updated

Scientific paper

10.1016/j.ejc.2006.08.011

We consider the orthogonality graph Omega(n) with 2^n vertices corresponding to the 0-1 n-vectors, two vertices adjacent if and only if the Hamming distance between them is n/2. We show that the stability number of Omega(16) is alpha(Omega(16))= 2304, thus proving a conjecture by Galliard. The main tool we employ is a recent semidefinite programming relaxation for minimal distance binary codes due to Schrijver. As well, we give a general condition for 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 Omega(n) the latter two bounds are equal to 2^n/n.

Affiliated with

Also associated with

No associations

Rating

A note on the stability number of an orthogonality graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A note on the stability number of an orthogonality graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A note on the stability number of an orthogonality graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-460430