Independence number and the complexity of families of sets (Q1918552): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q200913 |
||
Property / reviewed by | |||
Property / reviewed by: Péter L. Erdős / rank | |||
Revision as of 21:45, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Independence number and the complexity of families of sets |
scientific article |
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