Quantum measurements are inherently probabilistic. Further defying our classical intuition, quantum theory often forbids us to precisely determine the outcomes of simultaneous measurements. This phenomenon is captured and quantified through uncertainty relations. Although studied since the inception of quantum theory, this problem of determining the possible expectation values of a collection of quantum measurements remains, in general, unsolved.
In this talk, we will go over some basic notions of graph theory that will allow us to derive uncertainty relations valid for any set of dichotomic quantum observables. We will then specify the many cases for which these relations are tight, depending on properties of some graphs, and discuss a conjecture for the untight cases. Finally, we will show some direct applications to several problems in quantum information, namely, in constructing entropic uncertainty relations, separability criteria and entanglement witnesses.