  Quantum measurements are inherently probabilistic and quantum theory often
forbids to precisely predict the outcomes of simultaneous measurements. This
phenomenon is captured and quantified through uncertainty relations. Although
studied since the inception of quantum theory, the problem of determining the
possible expectation values of a collection of quantum measurements remains, in
general, unsolved. By constructing a close connection between observables and
graph theory, we derive uncertainty relations valid for any set of dichotomic
observables. These relations are, in many cases, tight, and related to the size
of the maximum clique of the associated graph. As applications, our results can
be straightforwardly used to formulate entropic uncertainty relations,
separability criteria and entanglement witnesses.
