Lehrstuhl Mathematik & InformatikOne-inclusion Hypergraph Density Revisited
In this paper, we show that the density of the one-inclusion hypergraph induced by a family of multi-valued functions is bounded by the pseudo-dimension of this family. (The original proof for this fact, that has been published quite recently, makes use of a wrong claim.) We show furthermore that the well-known graph-dimension is another upper bound on the density (which solves an open problem from a recent paper by Rubinstein, Bartlett, and Rubinstein.