A note on the stability number of an orthogonality graph (Q2643845): Difference between revisions

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\).