Parameters measuring the size of set families - Combinatorial Parameters

Parameters measuring the size of set families

Effective Range

Name: Effective Range

Symbol: $\mathrm{E}$

Definition:

The effective range $E(\mathcal{H})$ of a family $\mathcal{H}$ is the number of elements that can be distinguished by members of $\mathcal{H}$: $$ E(\mathcal{H}):= |{x:x\in\mathcal{X|,\, \exists h_1,h_2\in\mathcal{H},\, x\in h_1 \Delta h_2}} $$

Category: Basic

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: Yes

Values:

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Size

Name: Size

Symbol: $\mathrm{H}$

Definition:

The size of a family $\mathcal{H}$ is simply the cardinality, $$ |\mathcal{H|} $$

Category: Basic

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: Yes

Values:

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Oriented Diameter

Name: Oriented Diameter

Symbol: $\mathrm{D}^+$

Definition:

The oriented diameter $\mathrm{D}^+(\mathcal{H})$ of a family $\mathcal{H}$ is defined as $$ \mathrm{D}^+(\mathcal{H}):= \max{|S|: {\emptyset, S}\subset \mathcal{H}_{|S}} $$

Category: Basic

Symmetric: No

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values:

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Diameter

Name: Diameter

Symbol: $\mathrm{D}$

Definition:

The diameter $D(\mathcal{H})$ of a family $\mathcal{H}$ is the largest distance between two elements of the family, i.e. $$ D(\mathcal{H}):= \max_{h_1,h_2\in\mathcal{H}} |h_1\Delta h_2| $$

Comments:

The diameter is equal to the strict diameter dimension.

Category: Basic

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values:

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Hamming Radius

Name: Hamming Radius

Symbol: $\mathrm{B}$

Definition:

The Hamming Radius $B(\mathcal{H})$ of a family $\mathcal{H}$ is the smallest radius of an enclosing Hamming ball, defined as $$ B(\mathcal{H}):= \min{d: \exists T\subset \mathcal{X},\, \forall h\in \mathcal{H},\, |h\Delta T|\le d} $$

Category: Basic

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values:

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Threshold Dimension

Name: Threshold Dimension

Symbol: $\mathrm{T}$

Definition:

The Threshold dimension of a family $\mathcal{H}$, denoted by $T(\mathcal{H})$, is the largest integer $d$ such that there exists a set $S\subset \mathcal{X}$, of size $d$ such that $\mathcal{H}_{|S}$ contains thresholds, i.e. there is an ordering $x_1,\ldots,x_d$ of the elements of $S$ such that $$ \forall 0\le k\le d,\, {x_1,\ldots,x_k} \in \mathcal{H}_{|S}\,. $$

Comments:

Note that this means $\mathcal{H}_{|S}$ contains a $d+1$-chain, i.e. $d+1$ sets $S_1,\ldots,S_{d+1}$ such that $S_1\subset \ldots\subset S_{d+1}$.

Category: Basic

Symmetric: No

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values:

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Path Dimension

Name: Path Dimension

Symbol: $\mathrm{P}$

Definition:

The Path dimension of a family $\mathcal{H}$, denoted by $P(\mathcal{H})$, is the largest integer $d$ such that there exists a set $S\subset \mathcal{X}$, of size $d$ such that $\mathcal{H}_{|S}$ contains a full path, i.e. there is an ordering $x_1,\ldots,x_d$ of the elements of $S$ and a subset $T\subset S$ such that $$ \forall 0\le k\le d,\, T\Delta {x_1,\ldots,x_k} \in \mathcal{H}_{|S}\,. $$

Category: Basic

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values:

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Densest Subgraph (twice)

Name: Densest Subgraph (twice)

Symbol: $\mathrm{dens}^*$

Definition:

The densest subgraph dimension of a concept class is equal to twice the density of the densest subgraph (a.k.a. subgraph density) of its $1$-inclusion graph.

Comments:

The densest subgraph is dual to the lowest outdegree orientation.

Category: Graph-based

Symmetric: Yes

Monotonic: Yes

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Double Density or Average Degree

Name: Double Density or Average Degree

Symbol: $\mathrm{dens}$

Definition:

The double-density of a concept class is defined as twice the density of its $1$-inclusion graph, i.e twice the ratio of edges to vertices, or equivalently the average degree.

Category: Graph-based

Symmetric: Yes

Monotonic: No

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Minimum Degree

Name: Minimum Degree

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

Definition:

The minimum degree of a concept class is defined as the minimum degree of its $1$-inclusion graph.

Category: Graph-based

Symmetric: Yes

Monotonic: No

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1): None

Relationships (as Parameter 2):

Log Shattering

Name: Log Shattering

Symbol: $\log \mathrm{sh}$

Definition:

The Log Shattering of a family $\mathcal{H}$ is the (binary) log of the number of its shattered sets, $$ \log |sh{\mathcal{H|}} $$

Category: Shattering

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: Yes

Values:

Relationships (as Parameter 1):

Relationships (as Parameter 2):

VC Dimension

Name: VC Dimension

Symbol: $\mathrm{VC}$

Definition:

The VC dimension of a family $\mathcal{H}$, denoted by $\VC(\mathcal{H})$, is the largest integer $d$ such that there exists a set $S\subset \mathcal{X}$, of size $d$ such that $S$ is shattered by $\mathcal{H}$, i.e. $$ |\mathcal{H|_{|S}} = 2^{|S|}\,. $$

Description:

Vapnik-Chervonenkis Dimension [vc71].

Category: Shattering

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values:

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Effective VC Radius

Name: Effective VC Radius

Symbol: $\mathrm{VCR}$

Definition:

For a family $\mathcal{H}\subset 2^\mathcal{X}$, we define the effective VC radius as the largest integer $k$ such that all subsets of size $k$ of the effective range of $\mathcal{H}$, i.e. $\bigcup {h\Delta h': h,h'\in \mathcal{H}}$ are shattered by $\mathcal{H}$.

Category: Shattering

Symmetric: Yes

Monotonic: Yes

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values:

Relationships (as Parameter 1): None

Relationships (as Parameter 2):

Yang dimension

Name: Yang dimension

Symbol: $\mathrm{Y}$

Description:

Projective dimension of the cuboplex

Category: Algebraic

Symmetric: Yes

Monotonic: No

P-Monotonic: Yes

Doubly Monotonic: No

Strictly Monotonic: No

Values:

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Interpolation degree

Name: Interpolation degree

Symbol: $\mathrm{intdeg}$

Description:

Minimum degree of an interpolating polynomial

Category: Algebraic

Symmetric: Yes

Monotonic: Yes

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Unlabeled sample compression

Name: Unlabeled sample compression

Symbol: $\mathrm{USC}$

Description:

Minimum size of an unlabeled sample compression scheme

Category: Compression

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Star number

Name: Star number

Symbol: $\mathrm{S}$

Definition:

The Star dimension of a family $\mathcal{H}$, denoted by $S(\mathcal{H})$, is the largest integer $d$ such that there exists a set $S\subset \mathcal{X}$, of size $d$ such that $\mathcal{H}_{|S}$ contains a $d$-star, i.e. there is a subset $T\subset S$ such that $$ T\in \mathcal{H}_{|S} \,\mbox{ and }\, \forall x\in S,\, T\Delta {x} \in \mathcal{H}_{|S}\,. $$

Category: Teaching and Hitting

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values:

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Monotone Recursive Teaching Dimension

Name: Monotone Recursive Teaching Dimension

Symbol: $\mathrm{RTD}^p$

Category: Teaching and Hitting

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values:

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Teaching Dimension

Name: Teaching Dimension

Symbol: $\mathrm{TD}$

Category: Teaching and Hitting

Symmetric: Yes

Monotonic: Yes

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values:

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Hitting Size

Name: Hitting Size

Symbol: $\mathrm{HT}$

Category: Teaching and Hitting

Symmetric: No

Monotonic: Yes

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1): None

Relationships (as Parameter 2):

Relative Hitting Size

Name: Relative Hitting Size

Symbol: $\mathrm{RHT}$

Category: Teaching and Hitting

Symmetric: Yes

Monotonic: Yes

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Majority Complexity

Name: Majority Complexity

Symbol: $\mathrm{Maj}$

Category: Queries

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Worst Mistakes

Name: Worst Mistakes

Symbol: $\mathrm{M}_{\mathrm{worst}}$

Category: Queries

Symmetric: Yes

Monotonic: Yes

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Best Mistakes

Name: Best Mistakes

Symbol: $\mathrm{M}_{\mathrm{best}}$

Category: Queries

Symmetric: Yes

Monotonic: Yes

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Partial Equivalence Queries Complexity

Name: Partial Equivalence Queries Complexity

Symbol: $\mathrm{Q}_{\mathrm{par}}$

Category: Queries

Symmetric: Yes

Monotonic: Yes

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values:

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Self-Directed Queries Complexity

Name: Self-Directed Queries Complexity

Symbol: $\mathrm{M}_{\mathrm{sd}}$

Category: Queries

Symmetric: Yes

Monotonic: Yes

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Occasional One-Sided Getback

Name: Occasional One-Sided Getback

Symbol: $\mathrm{M}_{\mathrm{o1g}}$

Category: Queries

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Order Sample Compression

Name: Order Sample Compression

Symbol: $\mathrm{OSC}$

Category: Compression

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values:

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Stable Unlabeled Complexity

Name: Stable Unlabeled Complexity

Symbol: $\mathrm{sUSC}$

Category: Compression

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Proper Stable Sample Compression

Name: Proper Stable Sample Compression

Symbol: $\mathrm{psUSC}$

Category: Compression

Symmetric: Yes

Monotonic: No

P-Monotonic: Yes

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Proper Unlabeled Sample Compression

Name: Proper Unlabeled Sample Compression

Symbol: $\mathrm{pUSC}$

Category: Compression

Symmetric: Yes

Monotonic: No

P-Monotonic: Yes

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Labeled Sample Compression

Name: Labeled Sample Compression

Symbol: $\mathrm{LSC}$

Category: Compression

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Stable Labeled Sample Compression

Name: Stable Labeled Sample Compression

Symbol: $\mathrm{sLSC}$

Category: Compression

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Proper Labeled Sample Compression

Name: Proper Labeled Sample Compression

Symbol: $\mathrm{pLSC}$

Category: Compression

Symmetric: Yes

Monotonic: No

P-Monotonic: Yes

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Proper Stable Labeled Sample Compression

Name: Proper Stable Labeled Sample Compression

Symbol: $\mathrm{psLSC}$

Category: Compression

Symmetric: Yes

Monotonic: No

P-Monotonic: Yes

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

co-VC dimension

Name: co-VC dimension

Symbol: $\mathrm{coVC}$

Definition:

The coVC number of a family $\mathcal{H}$, denoted by $\covcmod(\mathcal{H})$, is the largest integer $d$ such that there exists a set $S\subset \mathcal{X}$, of size $d$ such that $\mathcal{H}_{|S}$ contains a hollow $d$-star, i.e. there is a subset $T\subset S$ such that $$ T\notin \mathcal{H}_{|S} \,\mbox{ and }\, \forall x\in S,\, T\Delta {x} \in \mathcal{H}_{|S}\,. $$

Category: Holes and Homology

Symmetric: Yes

Monotonic: No

P-Monotonic: Yes

Doubly Monotonic: No

Strictly Monotonic: No

Values:

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Sign Rank

Name: Sign Rank

Symbol: $\mathrm{SR}$

Definition:

The sign rank of a sign matrix $S$ is the maximum number $k$ such for all real matrix $M$ whose signs are $S$, $M$ has rank at least $k$.

Category: Algebraic

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Equivalence Queries Complexity

Name: Equivalence Queries Complexity

Symbol: $\mathrm{Q}_{\mathrm{eq}}$

Category: Queries

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: Yes

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Positive Teaching Dimension

Name: Positive Teaching Dimension

Symbol: $\mathrm{TD}^+$

Category: Teaching and Hitting

Symmetric: No

Monotonic: Yes

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2): None

Preference-Based Teaching Dimension

Name: Preference-Based Teaching Dimension

Symbol: $\mathrm{PBTD}$

Category: Teaching and Hitting

Symmetric: Yes

Monotonic: Yes

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2): None

No-Clashing Teaching Dimension

Name: No-Clashing Teaching Dimension

Symbol: $\mathrm{NCTD}$

Category: Teaching and Hitting

Symmetric: Yes

Monotonic: Yes

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values:

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Log Size

Name: Log Size

Symbol: $\log \mathrm{H}$

Definition:

The Log Size of a family $\mathcal{H}$ is simply the (binary) log of its cardinality, $$ \log |\mathcal{H|} $$

Category: Basic

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: Yes

Values:

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Log Size Ratio

Name: Log Size Ratio

Symbol: $\frac{\log (\mathrm{H}-1)}{\log (n+1)}$

Definition:

The Log Size Ratio of a family $\mathcal{H}$ is the ratio of the log of its cardinality to the log of the effective range, $$ \log \frac{|\mathcal{H|}-1}{\log (n+1)} $$

Category: Basic

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values:

Relationships (as Parameter 1): None

Relationships (as Parameter 2):

Random Proper Equivalence Queries Complexity

Name: Random Proper Equivalence Queries Complexity

Symbol: $\mathrm{Q}_{\mathrm{rpeq}}$

Category: Queries

Symmetric: Yes

Monotonic: No

P-Monotonic: Yes

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Random Equivalence Queries Complexity

Name: Random Equivalence Queries Complexity

Symbol: $\mathrm{Q}_{\mathrm{req}}$

Category: Queries

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Projected Membership Queries Complexity

Name: Projected Membership Queries Complexity

Symbol: $\mathrm{Q}_{\mathrm{m}}^p$

Category: Queries

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values:

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Minimum Teaching Set Size

Name: Minimum Teaching Set Size

Symbol: $\mathrm{TS}_{\min}$

Category: Teaching and Hitting

Symmetric: Yes

Monotonic: No

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values:

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Maximum Teaching Set Size

Name: Maximum Teaching Set Size

Symbol: $\mathrm{TS}_{\max}$

Category: Teaching and Hitting

Symmetric: Yes

Monotonic: Yes

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Minimum Projected Teaching Set Size

Name: Minimum Projected Teaching Set Size

Symbol: $\mathrm{TS}_{\min}^p$

Category: Teaching and Hitting

Symmetric: Yes

Monotonic: No

P-Monotonic: Yes

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Maximum Projected Teaching Set Size

Name: Maximum Projected Teaching Set Size

Symbol: $\mathrm{TS}_{\max}^p$

Category: Teaching and Hitting

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Monotonic Minimum Teaching Set Size

Name: Monotonic Minimum Teaching Set Size

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

Category: Teaching and Hitting

Symmetric: Yes

Monotonic: Yes

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Monotonic Projected Minimum Teaching Set Size

Name: Monotonic Projected Minimum Teaching Set Size

Symbol: $\mathrm{TS}_{\min}^{*p}$

Category: Teaching and Hitting

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Information Complexity

Name: Information Complexity

Symbol: $\mathrm{IC}$

Category: Basic

Symmetric: Yes

Monotonic: Yes

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1): None

Relationships (as Parameter 2): None

Proper Ordered Sample Compression

Name: Proper Ordered Sample Compression

Symbol: $\mathrm{pOSC}$

Category: Compression

Symmetric: Yes

Monotonic: No

P-Monotonic: Yes

Doubly Monotonic: No

Strictly Monotonic: No

Values:

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Largest Shattered Set

Name: Largest Shattered Set

Symbol: $\mathrm{SH}$

Category: Shattering

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2): None

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):

Relationships (as Parameter 2):

Projected Maximal Degree

Name: Projected Maximal Degree

Symbol: $\mathrm{d}^p_{\max}$

Category: Graph-based

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2): None

No Name

Category:

Symmetric: No

Monotonic: No

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1): None

Relationships (as Parameter 2): None

Projected Double Density or Projected Average Degree

Name: Projected Double Density or Projected Average Degree

Symbol: $\mathrm{dens}^p$

Definition:

The projected double density of a concept class is defined as the maximum over all projections of the averaged degree of the $1$-inclusion graph.

Category: Graph-based

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Projected Minimum Degree

Name: Projected Minimum Degree

Symbol: $\mathrm{d}^p_{\min}$

Category: Graph-based

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

No Name

Category:

Symmetric: No

Monotonic: No

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1): None

Relationships (as Parameter 2): None

Dual Sign Rank

Name: Dual Sign Rank

Symbol: $\mathrm{DSR}$

Definition:

The dual sign rank of a sign matrix $S$ is the maximum number $k$ such that there exist $k$ columns of $S$ such that any real matrix $M$ with signs $S$ has those column linearly independent.

Category: Algebraic

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Projected VC Radius

Name: Projected VC Radius

Symbol: $\mathrm{VCR}^p$

Category: Shattering

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values:

Relationships (as Parameter 1):

Relationships (as Parameter 2): None

Projected Strongly Shattered Dimension

Name: Projected Strongly Shattered Dimension

Symbol: $\mathrm{ST}^p$

Category: Shattering

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2): None

Maximum Largest Order Shattered Set

Name: Maximum Largest Order Shattered Set

Symbol: $\mathrm{OSH}_{\max}$

Category: Shattering

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2): None

Maximum Positive Degree

Name: Maximum Positive Degree

Symbol: $\mathrm{d}^+_{\max}$

Definition:

The Maximum Positive Degree of a concept class is the maximum dominance of its $1$-inclusion graph (where dominance is the number of neighbors that are smaller with respect to inclusion).

Category: Graph-based

Symmetric: No

Monotonic: Yes

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Positive No-Clashing Teaching Dimension

Name: Positive No-Clashing Teaching Dimension

Symbol: $\mathrm{NCTD}^+$

Category: Teaching and Hitting

Symmetric: No

Monotonic: Yes

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Distinguishing Range

Name: Distinguishing Range

Symbol: $\mathrm{R}$

Definition:

Minimum number of coordinates over which all concepts in the class can be distinguished.

Category: Basic

Symmetric: Yes

Monotonic: Yes

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

Positive Recursive Teaching Dimension

Name: Positive Recursive Teaching Dimension

Symbol: $\mathrm{RTD}^+$

Category: Teaching and Hitting

Symmetric: No

Monotonic: Yes

P-Monotonic: No

Doubly Monotonic: No

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

2-Littlestone Dimension

Name: 2-Littlestone Dimension

Symbol: $\mathrm{L}_2$

Category: Queries

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

3-Littlestone Dimension

Name: 3-Littlestone Dimension

Symbol: $\mathrm{L}_3$

Category: Queries

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):

$k$-Littlestone Dimension ($k\ge3$)

Name: $k$-Littlestone Dimension ($k\ge3$)

Symbol: $\mathrm{L}_k$

Category: Queries

Symmetric: Yes

Monotonic: Yes

P-Monotonic: Yes

Doubly Monotonic: Yes

Strictly Monotonic: No

Values: None

Relationships (as Parameter 1):

Relationships (as Parameter 2):