Add Theory section in gt.sage

[math1um]

Define all known upper and lower bound theorems, and add a list "alpha_upper_bounds", and "alpha_lower_bounds"

For each bound, we need a precise reference and should test the theorem at least for the available graphs.

[rbarden]

I'll add these sections.

[rbarden]

These need to be checked. They are the upper bounds from Willis's thesis.

# R. Pepper. Binding independence. Ph. D. Dissertation. University of Houston. Houston, TX, 2004.
annihilation_thm = lambda g: annihilation_number(g)

fractional_thm = lambda g: fractional_alpha(g)

# R. Pepper. Binding independence. Ph. D. Dissertation. University of Houston. Houston, TX, 2004.
kwok_thm = lambda g: order(g) - (size(g)/max_degree(g))

# D. M. Cvetkovic, M. Doob, and H. Sachs. Spectra of graphs. Academic Press, New York, 1980.
cvetkovic_thm = lambda g: cvetkovic(g)

# Trivial
trivial_thm = lambda g: order(g)

min_degree_thm = lambda g: order(g) - min_degree(g)

# P. Hansen and M. Zheng. Sharp Bounds on the order, size, and stability number of graphs. NETWORKS 23 (1993), no. 2, 99-102.
hansen_thm = lambda g: floor(1/2 + sqrt(1/4 + order(g)**2 - order(g) - 2*size(g)))

borg_thm = lambda g: order(g) - ceil((order(g) - 1) / max_degree(g))

matching_number_thm = lambda g: order(g) - matching_number(g)

Need references for Fractional Alpha, Minimum Degree, Borg, and Matching Number.

[math1um]

the matching number theorem is "folklore". but the reason is simple: let M be a maximum matching., and mu = |M|. at most one vertex from each of the mu edges is in any maximum independent set. so at least mu vertices are not in the maximum independent set. so the maximum independent set has at most n-mu vertices.

[math1um]

for fractional independence, this was first explored by Nemhauser and Trotter in the 70s. see:

1. Nemhauser, George L., and Leslie Earl Trotter. "Vertex packings: structural properties and algorithms." Mathematical Programming 8.1 (1975): 232-248.

2. Nemhauser, George L., and Leslie E. Trotter. "Properties of vertex packing and independence system polyhedra." Mathematical Programming 6.1 (1974): 48-61.

[math1um]

The Hansen bound is correct. The same paper (attached) gives a lower bound: alpha >= ceil((2n - (2m/ceil(2m/n))/(ceil(2m/n))+1)), where n=order and m=size

hansen-zheng-stability-number-bounds-1993.pdf

[math1um]

Here's a Borg Bound reference: https://arxiv.org/abs/1007.5426

Is it of practical use? (Does it beat all other bounds for any graph?)

[nvcleemp]

Just a short note about adding lambdas as invariants. They don't play well with the precomputed values database. The key that is used to identify the invariant is the name of the invariant. For lambdas this is always <lambda>. If you want to use a lambda, it might be better to also give it a name:

kwok_thm = lambda g: order(g) - (size(g)/max_degree(g))
kwok_thm.__name__ = 'kwok'

In other cases there actually is no need to use a lambda. For instance, the following:

cvetkovic_thm = lambda g: cvetkovic(g)
trivial_thm = lambda g: order(g)

could also be written as

cvetkovic_thm = cvetkovic
trivial_thm = Graph.order

[thenealon]

RE: Borg Bound

The Borg bound simplifies to n-ceil((n-1)/Delta) for 2-graphs; for a connected graph, this will never beat the Kwok bound of n-size/delta, since size>=n-1 (sage assures me the ceiling doesn't matter).

[rbarden]

@nvcleemp Which would you prefer, methods or lambdas for the ones that need it?

[rbarden]

Exists in the reorganization.