A Note on the Stability Number of an Orthogonality Graph

E. de Klerk, D.V. Pasechnik

Research output: Working paperDiscussion paperOther research output

217 Downloads (Pure)

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 [7].The main tool we employ is a recent semidefinite programming relaxation for minimal distance binary codes due to Schrijver [16].Moreover, 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 (n) the latter two bounds are equal to 2n/n.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages11
Volume2005-66
Publication statusPublished - 2005

Publication series

NameCentER Discussion Paper
Volume2005-66

Fingerprint

Stability number
Orthogonality
Graph in graph theory
Semidefinite Programming Relaxation
Association Scheme
Hamming Distance
Binary Code
Clique
Adjacent
If and only if

Keywords

  • C0
  • C61

Cite this

de Klerk, E., & Pasechnik, D. V. (2005). A Note on the Stability Number of an Orthogonality Graph. (CentER Discussion Paper; Vol. 2005-66). Tilburg: Operations research.
de Klerk, E. ; Pasechnik, D.V. / A Note on the Stability Number of an Orthogonality Graph. Tilburg : Operations research, 2005. (CentER Discussion Paper).
@techreport{8fc31de593ae4966836af2598a425033,
title = "A Note on the Stability Number of an Orthogonality Graph",
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 [7].The main tool we employ is a recent semidefinite programming relaxation for minimal distance binary codes due to Schrijver [16].Moreover, 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 (n) the latter two bounds are equal to 2n/n.",
keywords = "C0, C61",
author = "{de Klerk}, E. and D.V. Pasechnik",
note = "Subsequently published in the European Journal of Combinatorics, 2007 Pagination: 11",
year = "2005",
language = "English",
volume = "2005-66",
series = "CentER Discussion Paper",
publisher = "Operations research",
type = "WorkingPaper",
institution = "Operations research",

}

de Klerk, E & Pasechnik, DV 2005 'A Note on the Stability Number of an Orthogonality Graph' CentER Discussion Paper, vol. 2005-66, Operations research, Tilburg.

A Note on the Stability Number of an Orthogonality Graph. / de Klerk, E.; Pasechnik, D.V.

Tilburg : Operations research, 2005. (CentER Discussion Paper; Vol. 2005-66).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

T1 - A Note on the Stability Number of an Orthogonality Graph

AU - de Klerk, E.

AU - Pasechnik, D.V.

N1 - Subsequently published in the European Journal of Combinatorics, 2007 Pagination: 11

PY - 2005

Y1 - 2005

N2 - 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 [7].The main tool we employ is a recent semidefinite programming relaxation for minimal distance binary codes due to Schrijver [16].Moreover, 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 (n) the latter two bounds are equal to 2n/n.

AB - 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 [7].The main tool we employ is a recent semidefinite programming relaxation for minimal distance binary codes due to Schrijver [16].Moreover, 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 (n) the latter two bounds are equal to 2n/n.

KW - C0

KW - C61

M3 - Discussion paper

VL - 2005-66

T3 - CentER Discussion Paper

BT - A Note on the Stability Number of an Orthogonality Graph

PB - Operations research

CY - Tilburg

ER -

de Klerk E, Pasechnik DV. A Note on the Stability Number of an Orthogonality Graph. Tilburg: Operations research. 2005. (CentER Discussion Paper).