math1um / objects-invariants-properties

Objects, Invariants and Properties for Graph Theory (GT) automated conjecturing: in particular with the Sage program CONJECTURING: http://nvcleemp.github.io/conjecturing/
GNU General Public License v3.0
15 stars 6 forks source link

Add kashin_konyagin property #348

Open math1um opened 7 years ago

math1um commented 7 years ago

They proved: For graphs with alpha<=2, lovasz_theta <= 2^(2/3)*n^(1/3), where n = order.

It is possible some graphs with alpha > 2 also have this property.

from p.47 of Knuth paper: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v1i1a1

ghost commented 7 years ago
def kashin_konyagin_property(g):
    upper_bound = 2^(2/3)*g.order()^(1/3)
    if (independence_number(g) <= 2):
        return upper_bound
    else:
        return bool(independence_number(g) <= upper_bound)

This returns True/False for graphs with an independence number > 2 or the upper bound for the independence number if it is <= 2. Does this look okay?