Lovasz_theta problem

[math1um]

Let g=Graph("GsaCC?")

The independence number of g is 7.

but, g.lovasz_theta() = 6.9999999

That is, this function slightly under-computes theta. But this is enough to make conjectures like alpha >= theta false, and to severely cripple true statements like alpha <= floor(theta).

I've run thru a list of very small graphs and seen this problem repeatedly. What, if anything, can be done? Should we round theta if it is within epsilon of an integer?

[nvcleemp]

I don't think rounding will be the solution.

One possibility I was considering early on was to build in some fault tolerance. Say you are verifying whether a < b. Instead of checking whether a < b, you actually check whether a - epsilon < b. This should handle the problem for theta (except for the floor issue). The reason I did not do this, is because I wanted the answer to be consistent when a user looks at the conjecture, and tries it out for himself.

The floor issue could similarly be resolved by introducing a floor' function such that floor'(x) = floor(x+epsilon).

However, I'm not sure that these are the best solutions, and whether they will not break more than they fix.

[math1um]

how about this: return rounded value if the produced value is within a specified epsilon of the rounded value?

def lovasz_theta(g, epsilon = 0.00001):

initial = g.lovasz_theta()
if abs(initial - round(initial)) < epsilon:
    return round(initial) 
return initial

[math1um]

OK, add this, with docstring. This is probably the best way to proceed.

def lovasz_theta(g, epsilon = 0.00001): """ The value of lovasz theta is a real number and thus admits the potential of numerical error in its computation. This hack introduces a different potential source of error in cases where the value is very close to an integer but not actually equal to that integer. The tradeoff is that it solves the problem of a conjecture like alpha<=theta to be counted as false when alpha=theta=7 but the computed value of theta is 6.99999. Pros and cons, as is always the case in life! """ initial = g.lovasz_theta() if abs(initial - round(initial)) < epsilon: return round(initial) return initial

[jaritaes99]

added the function and changed all instances of g.lovasz_theta to loves_theta(g)

[thenealon]

added the function and changed all instances of g.lovasz_theta to loves_theta(g)

Hopefully just a typo in the commit?

On Mon, Jun 28, 2021 at 2:30 PM jaritaes99 @.***> wrote:

added the function and changed all instances of g.lovasz_theta to loves_theta(g)

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/math1um/objects-invariants-properties/issues/606#issuecomment-869919239, or unsubscribe https://github.com/notifications/unsubscribe-auth/AA55ZQ2DMFQAHKWDD43N3GDTVC5STANCNFSM4FMO3S2A .