×

zbMATH — the first resource for mathematics

A note on the stability number of an orthogonality graph. (English) Zbl 1125.05053
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\).

MSC:
05C35 Extremal problems in graph theory
90C22 Semidefinite programming
Software:
SeDuMi
PDF BibTeX XML Cite
Full Text: DOI arXiv Link
References:
[1] Bannai, E.; Ito, T., Algebraic combinatorics I, (1984), Benjamin/Cummings Publishing Company London · Zbl 0555.05019
[2] Brassard, G.; Cleve, R.; Tapp, A., The cost of exactly simulating quantum entanglement with classical communication, Phys. rev. lett., 83, 9, 1874-1878, (1999)
[3] Delsarte, P., Bounds for unrestricted codes, by linear programming, Philips res. rep., 27, 272-289, (1972) · Zbl 0348.94016
[4] Delsarte, P., An algebraic approach to the association schemes of coding theory, Philips res. rep., Suppl. 10, 1-97, (1973) · Zbl 1075.05606
[5] E. de Klerk, D.V. Pasechnik, A. Schrijver, Reduction of symmetric semidefinite programs using the regular *-representation, Math. Program. B (2005) (preprint) (in press). Available at http://www.optimization-online.org · Zbl 1200.90136
[6] Frankl, P.; Rödl, V., Forbidden intersections, Trans. AMS, 300, 259-286, (1987) · Zbl 0611.05002
[7] V. Galliard, Classical pseudo telepathy and coloring graphs, Diploma Thesis, ETH Zurich, 2001. Available at http://math.galliard.ch/Cryptography/Papers/PseudoTelepathy/SimulationOfEntanglement.pdf
[8] V. Galliard, A. Tapp, S. Wolf, The impossibility of pseudo-telepathy without quantum entanglement, in: Proc. 2003 IEEE International Symposium on Information Theory, ISIT, Yokohama, 2003
[9] C.D. Godsil, Interesting Graphs and their Colourings, in: Lecture Notes, University of Waterloo, ON, Canada, N2L 3G1. Available at http://quoll.uwaterloo.ca
[10] C.D. Godsil, M.W. Newman, Colouring an orthogonality graph, preprint, 2005. Available at http://www.arxiv.org/abs/math.CO/0509151
[11] Lassere, J., Global optimization with polynomials and the problem of moments, SIAM J. optim., 11, 3, 796-817, (2001) · Zbl 1010.90061
[12] Laurent, M., A comparison of the sherali – adams, lovász – schrijver and Lasserre relaxations for 0-1 programming, Math. oper. res., 28, 3, 470-496, (2003) · Zbl 1082.90084
[13] M. Laurent, Strengthened semidefinite programming bounds for codes, Math. Program. B (2005) (preprint) (in press). Available at http://homepages.cwi.nl/ monique/
[14] M.W. Newman, Independent sets and eigenspaces, Ph.D. Thesis, University of Waterloo, Waterloo, Canada, 2004. Available at: http://www.math.uwaterloo.ca/ mwnewman/thesis.pdf
[15] Supplementary files in http://www.arxiv.org/abs/math.CO/0505038
[16] Schrijver, A., A comparison of the delsarte and lovász bounds, IEEE trans. inform. theory, 25, 4, 425-429, (1979) · Zbl 0444.94009
[17] Schrijver, A., New code upper bounds from the Terwilliger algebra, IEEE trans. inform. theory, 51, 8, 2859-2866, (2005) · Zbl 1298.94152
[18] Sturm, J.F., Using sedumi 1.02, a Matlab toolbox for optimization over symmetric cones, Optim. methods softw., 11-12, 625-653, (1999) · Zbl 0973.90526
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.