[go: up one dir, main page]
TOPICS
Search

Sandwich Theorem

There are several theorems known as the "sandwich theorem."

In calculus, the squeeze theorem is also sometimes known as the sandwich theorem.

In graph theory, the sandwich theorem states that the Lovász number theta(G) of a graph G satisfies

omega(G)<=theta(G^_)<=chi(G),
(1)

where omega(G) is the clique number, chi(G) is the chromatic number of G, and G^_ is the graph complement of G. This can be rewritten by changing the role of graph complements, giving

omega(G^_)<=theta(G)<=chi(G^_),
(2)

which can be written using omega(G^_)=alpha(G) with alpha the independence number and theta(G)=chi(G^_) the clique covering number as

alpha(G)<=theta(G)<=theta(G).
(3)

Furthermore, theta(G) can be computed efficiently despite the fact that the computation of the two numbers it lies between is an NP-hard problem.

See also

Fermat's Sandwich Theorem, Ham Sandwich Theorem, Lovász number, Shannon Capacity, Squeeze Theorem

Explore with Wolfram|Alpha

References

Grötschel, M.; Lovász, L.; and Schrijver, A. "The Ellipsoid Method and Its Consequences in Combinatorial Optimization." Combinatorica 1, 169-197, 1981.Knuth, D. E. "The Sandwich Theorem." Electronic J. Combinatorics 1, No. 1, A1, 1-48, 1994. http://www.combinatorics.org/Volume_1/Abstracts/v1i1a1.html.

Referenced on Wolfram|Alpha

Sandwich Theorem

Cite this as:

Weisstein, Eric W. "Sandwich Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SandwichTheorem.html

Subject classifications