  A fundamental problem in quantum computation and quantum information is
finding the minimum quantum dimension needed for a task. For tasks involving
state preparation and measurements, this problem can be addressed using only
the input-output correlations. This has been applied to Bell,
prepare-and-measure, and Kochen-Specker contextuality scenarios. Here, we
introduce a novel approach to quantum dimension witnessing for scenarios with
one preparation and several measurements, which uses the graphs of mutual
exclusivity between sets of measurement events. We present the concepts and
tools needed for graph-theoretic quantum dimension witnessing and illustrate
their use by identifying novel quantum dimension witnesses, including a family
that can certify arbitrarily high quantum dimensions with few events.
