Tight Bound on Vertex Cut Sparsifiers in Directed Acyclic Graphs

For an unweighted graph on $k$ terminals, Kratsch and Wahlstr\"om constructed a vertex sparsifier with $O(k^3)$ vertices via the theory of representative families on matroids. Since their breakthrough result in 2012, no improvement upon the $O(k^3)$ bound has been found. In this paper, we interpret Kratsch and Wahlstr\"om's result through the lens of Bollob\'as's Two-Families Theorem from extremal combinatorics. 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.