most recent 30 from http://mathoverflow.net 2013-05-25T02:53:16Z http://mathoverflow.net/feeds/question/57336 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/57336/lovasz-theta-function-integrality Yaroslav Bulatov 2011-03-04T10:28:44Z 2011-03-05T11:29:19Z

<p>Is anything known about Lovasz Theta Function taking integral value in non-perfect graphs? In particular, does integral value of Lovasz theta always coincide with the size of largest independent set?</p> <p>For instance, graph below is non-perfect, and its Lovasz theta function gives the independence number.</p> <p><img src="http://yaroslavvb.com/upload/save/non-perfect.png"></p> <p>Its true for a few other non-perfect graphs I tried, here's a <a href="http://mathematica-bits.blogspot.com/2011/03/computing-lovasz-theta-function.html" rel="nofollow">Mathematica package </a> I used to compute it</p>

http://mathoverflow.net/questions/57336/lovasz-theta-function-integrality/57448#57448 Chris Godsil 2011-03-05T11:29:19Z 2011-03-05T11:29:19Z

<p>No. For some examples see <a href="http://mathoverflow.net/questions/46534/when-the-lovasz-theta-function-saturates-its-upper-bound" rel="nofollow">http://mathoverflow.net/questions/46534/when-the-lovasz-theta-function-saturates-its-upper-bound</a></p>