Independence number and the complexity of families of sets (Q1918552)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Independence number and the complexity of families of sets |
scientific article; zbMATH DE number 906902
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Independence number and the complexity of families of sets |
scientific article; zbMATH DE number 906902 |
Statements
Independence number and the complexity of families of sets (English)
0 references
25 November 1996
0 references
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.
0 references
complexity
0 references
qualitative independence
0 references
inclusion-exclusion
0 references
independence number
0 references
set system
0 references
Vapnik-Chervonenkis dimension
0 references
0 references
0 references
0.91050446
0 references
0.89542156
0 references
0.8888865
0 references
0.8876847
0 references
0.8865677
0 references
0.88534176
0 references
0.88308185
0 references
0.8819004
0 references
