Lovasz Number to the rescue

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s