TOPICS

# 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 of a graph satisfies

 (1)

where is the clique number, is the chromatic number of , and is the graph complement of . This can be rewritten by changing the role of graph complements, giving

 (2)

which can be written using with the independence number and the clique covering number as

 (3)

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

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

## Explore 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.

Sandwich Theorem

## Cite this as:

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