Better Know A Theorem: Sandwich Theorems

13Jul07

Rather than a complete explanation, today is an excerpt from “Combinatorial Optimization” by Lex Schrijver; if for no other reason, because of the name (tied for best with the “hairy ball theorem”).

A. Frank in 1982 showed the following ‘discrete sandwich theorem’ (analogous to the ‘continuous sandwich theorem’, stating the existence of a linear function between a convex and a concave function):

Corollary 46.2b (Frank’s discrete sandwich theorem). Let f be a submodular and g be a supermodular set function on S, with g f. Then there exists a modular set function h with g h f. If f and g are integer, h can be taken integer.

A Sandwich

Advertisements


No Responses Yet to “Better Know A Theorem: Sandwich Theorems”

  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: