Combinatorial properties of dependence graphs