A note on the stability number of an orthogonality graph

DOI10.1016/J.EJC.2006.08.011MaRDI QIDQ2643845zbMATH OpenOpenAlexDBLPWikidataFDO

Authors E. de Klerk, Dmitrii V. Pasechnik

Publication date 27 August 2007

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0505038, https://research.tilburguniversity.edu/en/publications/fb61fc0a-a843-4a66-8a69-36663e1032f5

zbMATH Keywords

Delsarte boundorthogonality graphstability number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Semidefinite programming (90C22)

Abstract: 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.

Review text

Let \(\Omega(n)\) be the graph on \(2^n\) vertices corresponding to the vectors \(\{0,1\}^n\), such that two vertices are adjacent if and only if the Hamming distance between them is \(n/2\). Then \(\Omega(n)\) is regular of degree \({n\choose n/2}\). Let \(\alpha(\Gamma)\) be the stability number of a graph \(\Gamma\). This note studies upper bounds on the stability number \(\alpha(\Omega(n))\) for \(n\leq 32\). It is known that \(\alpha(\Omega(n))\leq 2^n/n\) (the ratio bound). Schrijver (Laurent) obtained new upper bounds \(\overline \alpha(n)\) (\(l^+(n)\)) such that \(\alpha(\Omega(n))\leq l^+(n)\leq \overline\alpha(n)\leq 2^n/n\). For \(n=16\) the lower and Schrijver bound coincide, so \(\alpha(\Omega(16))=2304\) (previously known was \(\alpha(\Omega(16))\leq 3912\)). For \(n=20\) the Schrijver and the Laurent bound coincide, so \(20144\leq \alpha(\Omega(20))\leq 20164\). For \(n=24\) the Schrijver bound is 183373 and the Laurent bound is 184194, so \(178208\leq \alpha(\Omega(24))\leq 183173\).

Recommendations

• Lower bounds on the stability number of graphs computed in terms of degrees
• Sharp bounds on the order, size, and stability number of graphs
• Improving an upper bound on the stability number of a graph
• LP-oriented upper bounds for the weighted stability number of a graph
• A characterization of Delsarte's linear programming bound as a ratio bound

Cites work

• A comparison of the Delsarte and Lovász bounds
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• Forbidden Intersections
• Global optimization with polynomials and the problem of moments
• scientific article; zbMATH DE number 3884178 (Why is no real title available?)
• scientific article; zbMATH DE number 3543912 (Why is no real title available?)
• scientific article; zbMATH DE number 2232233 (Why is no real title available?)
• New Code Upper Bounds From the Terwilliger Algebra and Semidefinite Programming
• Reduction of symmetric semidefinite programs using the regular -representation
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones

Cited in

(12)

• Block-diagonal semidefinite programming hierarchies for 0/1 programming
• Commutative association schemes
• The density of sets avoiding distance 1 in Euclidean space
• High dimensional Hoffman bound and applications in extremal combinatorics
• Invariant Semidefinite Programs
• Deterministic quantum non-locality and graph colorings
• The automorphism group and fixing number of orthogonality graph over a vector space
• On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs
• Invitation to intersection problems for finite sets
• Strengthened semidefinite programming bounds for codes
• A characterization of Delsarte's linear programming bound as a ratio bound
• Problems from CGCS Luminy, May 2007

Describes a project that uses

Uses Software

• SeDuMi

This page was built for publication: A note on the stability number of an orthogonality graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2643845)