We have made conjectures for the following objects, among others.

- Upper and lower bounds for the independence number of a graph.
- Upper and lower bounds for the determinant of a matrix.
- Necessary and sufficient conditions for whether a graph contains a hamilton cycle.
- Upper and lower bounds for various invariants associated with the game Chomp.
- Lower bounds for Goldbach(x), the number of ways to represent x as a sum of primes.

Advertisements

someone knows a non-efficient characterization of graphs where the independence number \alpha equals the Lovász \vartheta function?

No. This would also be of interest. An efficient characterization, though, would give a new and possible large class of graphs where \alpha can be computed efficiently. Expanding this class is the immediate goal of this project.

Thanks. A non-efficient characterization is interesting for “my” problem :) but an efficient characterization is more interesting