Free resolutions of function classes via order complexes
  Function classes are collections of Boolean functions on a finite set, which
are fundamental objects of study in theoretical computer science. We study
algebraic properties of ideals associated to function classes previously
defined by the third author. We consider the broad family of
intersection-closed function classes, and describe cellular free resolutions of
their ideals by order complexes of the associated posets. For function classes
arising from matroids, polyhedral cell complexes, and more generally interval
Cohen-Macaulay posets, we show that the multigraded Betti numbers are pure, and
are given combinatorially by the M\"obius functions. We then apply our methods
to derive bounds on the VC dimension of some important families of function
classes in learning theory.
