Parameters measuring the size of set families

Degeneracy

Name: Degeneracy

Symbol: $\mathrm{d}^*_{\min}$

Definition:

The degeneracy of a concept class is defined as the degeneracy of its $1$-inclusion graph, i.e. the maximum over induced subgraphs of the minimum degree.

Category: Graph-based

Symmetric: Yes

Monotonic: Yes

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Degeneracy / Minimum Degree
Degeneracy / Largest Strongly Shattered Set

Relationships (as Parameter 2):

Densest Subgraph (twice) / Degeneracy
Maximum Degree / Degeneracy