Lovasz theta is *really* good

Patrick’s INP “survey” function currently tests graphs with minimum degree at least 3 and maximum degree no more than n-2 (graphs with \delta<3 or \Delta=n-1 are reducible). These are the graphs reported on below.

sage: INPGraph.survey(INPGraph.lovasz_theta, 9)
Counting graphs of order 9… 76783
Testing…
69941 out of 76783 graphs of order 9 were predicted by lovasz_theta.

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