Notes:
In this paper we use Talagrand's inequality to prove a concentration inequality for Lipschitz,
monotone submodular functions.
We were unaware of prior work proving concentration for subadditive functions by
Schechtman in 2003, using Talagrand's inequality,
and by Hajiaghayi et al. in 2005, using selfbounding functions.
In 2009, Chekuri and Vondrak also proved a concentration inequality for Lipschitz,
monotone submodular functions, using the FKG inequality.
Their inequality achieves Chernofftype concentration, which is somewhat better than the
Talagrandlike concentration that we achieve.
An earlier version of our paper only proved concentration for matroid rank functions.
After learning of the work of Chekuri and Vondrak, we improved our inequality
to its current form, in which it applies to arbitrary Lipschitz, monotone, submodular functions.
Perhaps the nicest way to prove such inequalities is using selfbounding functions.
In particular, this approach yields concentration for nonmonotone functions;
it is not clear whether the FKG or Talagrand approaches do too.
See the note by Vondrak from 2010.
