VC-dimensions Between Partially Ordered Sets and Totally Ordered Sets

Abstract

We say that two partial orders on $[n]$ are compatible if there exists a partial order that refines both of them. This compatibility relation induces a natural set system structure between the collection $\mathcal{F}$ of all partial orders and the collection $\mathcal{G}$ of all total orders on $[n]$, where each order is associated with the set of orders compatible with it. In this note, we determine the VC-dimension of $\mathcal{F}$ with respect to $\mathcal{G}$, proving that ${\mathrm{VC}}_{\mathcal{G}}(\mathcal{F})=\lfloor \frac{n^2}{4}\rfloor$ for $n\ge 4$. We also establish bounds on the dual VC-dimension, showing that $2(n-3)\le {\mathrm{VC}}_{\mathcal{F}}(\mathcal{G})\le n{\log }_{2}n$ for all $n\ge 1$.

5 pages, 2 figures