For graph ‘HCRbdq{‘ we knew alpha=3, and there was an efficiently computable lower bound equal to 3. Of the efficiently computable upper bounds we had programmed the best one was equal to 4. So there was a gap in the predictive power of the theory – as it had been programmed.

So it was time to program the Lovasz theta function. This number was defined by Lovasz in order to bound the Shannon capacity of a graph. It is an upper bound for the independence number. Fortunately, I didn’t have to do the programming work: the code is here. This number is the solution of a semi-definite programming problem and hence efficiently computable.

For graph ‘HCRbdq{‘ theta=3. Which in turn gives us alpha=3 directly from theory. Solved!

Advertisements