A Lecture on Submodular Functions

I will try to motivate submodular functions with a few examples and then attempt
to cast them as the discrete analogues of convex functions. The main results I
hope to prove are

- Characterize submodular functions in terms of their Lovasz extension.
- Submodular intersection theorem.
- Frank's discrete separation theorem.

The talk is intended for a general audience; the only thing anyone will need to
understand the proofs is LP duality.