Free resolutions of function classes via order complexes (Q2197912): Difference between revisions

Suppose that \(C\) is a collection of Boolean functions on \([n]=\{0,\ldots, n-1\}\) and \(U \subseteq [n]\). It is said that \(U\) is shattered by \(C\), if every possible Boolean function on \(U\) is a restriction of a function in \(C\). In learning theory the VC dimension of \(C\) is defined as \(\dim_{VC} C=\max\{|U|\big| U \text{ is shattered by }C\}\). This quantity tries to measure how much data is required to learn an unknown function, given that the function is in \(C\). Now consider the simplicial complex \(\diamond_C\) on the vertex set \([n]\times [2]\), whose facets are \(\{(i,f(i))|i\in [n]\}\) for all \(f\in C\). This is called the suboplex associated to \(C\). The Stanley-Reisner ideal of \(\diamond_C\) is called the suboplex ideal of \(C\) and is denoted by \(I_C\) and its Alexander dual is denoted by \(I^*_C\). The homological dimension of \(C\) is defined as the projective dimension of \(I^*_C\) and is denoted by \(\dim_h(C)\). In the paper [``A homological theory of functions'', Preprint, \url{arXiv:1701.02302}], \textit{G. Yang} showed that \(\dim_{VC}(C)\leq \dim_h(C)\). Now in the current paper, the authors present a free resolution for \(I^*_C\) when \(C\) is ``intersection-closed'', and use this to derive upper bounds on the VC dimension of some families of function classes. More concretely, the authors first note that under the correspondence \(f \leftrightarrow f^{-1}(1)\), the function class \(C\) corresponds to a poset of subsets of \([n]\). For a poset \(P\), the corresponding function class is denoted by \(C(P)\). They call a poset \(P\) intersection-closed, when from \(A,B\in P\) it follows that \(A\cap B\in P\). When \(P\) is intersection-closed, they construct a cellular free resolution of \(I^*_{C(P)}\) on the order complex of \(P\) and show that \(\dim_h C(P)\leq \mathrm{rank}(P)\), where \(\mathrm{rank}(P)\) denotes the length of a longest chain in \(P\). Then they consider interval Cohen-Macaulay posets, that is, posets \(P\) with the property that for every open interval \(I\) of \(P\), the order complex of \(I\) is Cohen-Macaulay. The authors present a formula for the Betti numbers of \(I^*_{C(P)}\), in terms of the Möbius function on \(P\), when \(P\) is intersection-closed and interval Cohen-Macaulay. They show that lattices of flats of matroids and face posets of polyhedral cell complexes have these two properties and use this to find the VC dimension of the former ones and give bounds on the VC dimension of the latter ones. Finally, they utilize these results to find the VC dimension or give bounds on the VC dimension of some families of function classes which are important in learning theory.