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 TheoremExplore with Wolfram|Alpha
More things to try:
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 TheoremCite this as:
Weisstein, Eric W. "Sandwich Theorem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SandwichTheorem.html