Before revision:  This new perspective allows us to close the gap for directed acyclic graphs and obtain a tight bound of \Theta(k^2) . Central to our approach is the concept of skew-symmetry from extremal combinatorics, and we derive a similar theory for the representation of skew-symmetric families that may have future applications).
After revision:  This new perspective allows us to close the gap for directed acyclic graphs and obtain a tight bound of \Theta(k^2) vertices for the case that G is a DAG. We also show how to compute H in time near-linear in the size of G, improving on the previous O(n^{\omega+1).