Fréchet optimal bounds on the probability of a union with supplementary information

We show that bounds for the probability of a union involving either lower order binomial moments or lower order probabilities of events may be considerably improved in the presence of supplementary information such as a bound on the number of events that can occur simultaneously or bounds on their probabilities. An example shows how such additional information often may be provided naturally. We also prove the Fréchet optimality of these bounds using linear programming.