Haemers Bound

I just read a couple of papers of Haemers from 1979, who introduced a minimum rank upper bound for the Shannon capacity of a graph and, hence, the independence number. Importantly, it can be better than Lovasz’s theta function.

Let G be a graph and B be an nxn matrix with Bi,j=0 iff there is an edge from vertex i to vertex j in G. Then alpha is no more than the rank of B. And, thus, alpha is no more than the minimum rank of all matrices of this form. He gives examples of computations of this bound in special cases. As far as I know it can’t be computed efficiently in the general case – although I’d love to know an algorithm.

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