A note on the stability number of an orthogonality graph
From MaRDI portal
Publication:2643845
DOI10.1016/J.EJC.2006.08.011zbMATH Open1125.05053DBLPjournals/ejc/KlerkP07arXivmath/0505038OpenAlexW1968116383WikidataQ56859927 ScholiaQ56859927MaRDI QIDQ2643845FDOQ2643845
Authors: E. de Klerk, Dmitrii V. Pasechnik 
Publication date: 27 August 2007
Published in: European Journal of Combinatorics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/math/0505038
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
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- Global optimization with polynomials and the problem of moments
- Title not available (Why is that?)
- Forbidden Intersections
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- Title not available (Why is that?)
- Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
- New Code Upper Bounds From the Terwilliger Algebra and Semidefinite Programming
- A comparison of the Delsarte and Lovász bounds
- Title not available (Why is that?)
Cited In (12)
- Problems from CGCS Luminy, May 2007
- A characterization of Delsarte's linear programming bound as a ratio bound
- On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs
- The automorphism group and fixing number of orthogonality graph over a vector space
- Strengthened semidefinite programming bounds for codes
- The density of sets avoiding distance 1 in Euclidean space
- High dimensional Hoffman bound and applications in extremal combinatorics
- Block-diagonal semidefinite programming hierarchies for 0/1 programming
- Invitation to intersection problems for finite sets
- Commutative association schemes
- Invariant Semidefinite Programs
- Deterministic quantum non-locality and graph colorings
Uses Software
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)
