Independence number and the complexity of families of sets (Q1918552): Difference between revisions

The independence number \(m({\mathcal C})\) of a set system \(\mathcal C\) is the cardinality of its maximum qualitative independent subsystem. This notion is in close connection to the well-known Vapnik-Chervonenkis dimension. The authors dedicated several research articles to this topic. This particular paper delivers general upper bounds on \(m({\mathcal C})\) and proves inequalities between the independence number and the Vapnik-Chervonenkis dimension, in both directions. It also turns out that for special cases the two quantities are equal.