Values assigned to parameters for specific classes - Combinatorial Parameters

Name: Effective Range of Trivial concepts

Class: Trivial concepts

Parameter: Effective Range

Value: $n$

Order: $\Omega(n)$

Name: Log Shattering of Trivial concepts

Class: Trivial concepts

Parameter: Log Shattering

Value: $\log n$

Order: $\Omega(\log n)$

Name: Membership and Proper Equivalence Queries Complexity of Trivial concepts

Class: Trivial concepts

Parameter: Membership and Proper Equivalence Queries Complexity

Value: $1$

Order: $\Omega(1)$

Name: Membership Query Complexity of Trivial concepts

Class: Trivial concepts

Parameter: Membership Query Complexity

Value: $1$

Order: $\Omega(1)$

Name: Projected Membership Queries Complexity of Trivial concepts

Class: Trivial concepts

Parameter: Projected Membership Queries Complexity

Value: $1$

Order: $\Omega(1)$

Name: Recursive Teaching Dimension of Addressing

Class: Addressing

Parameter: Recursive Teaching Dimension

Value: $1$

Order: $\Omega(1)$

Name: Recursive Teaching Dimension of Tagged Singletons

Class: Tagged Singletons

Parameter: Recursive Teaching Dimension

Value: $2$

Order: $\Omega(1)$

Name: Recursive Teaching Dimension of Half-intervals

Class: Half-intervals

Parameter: Recursive Teaching Dimension

Value: $1$

Order: $\Omega(1)$

Name: Recursive Teaching Dimension of Full Cube

Class: Full Cube

Parameter: Recursive Teaching Dimension

Value: $n$

Order: $\Omega(n)$

Name: Recursive Teaching Dimension of Singletons plus empty set

Class: Singletons plus empty set

Parameter: Recursive Teaching Dimension

Value: $1$

Order: $\Omega(1)$

Name: Recursive Teaching Dimension of Singletons

Class: Singletons

Parameter: Recursive Teaching Dimension

Value: $1$

Order: $\Omega(1)$

Name: Recursive Teaching Dimension of Trivial concepts

Class: Trivial concepts

Parameter: Recursive Teaching Dimension

Value: $1$

Order: $\Omega(1)$

Name: Star number of Majority

Class: Majority

Parameter: Star number

Value: $n$

Order: $\Omega(n)$

Name: Star number of Addressing

Class: Addressing

Parameter: Star number

Value: $n-1$

Order: $\Omega(n)$

Name: Teaching Dimension of Trivial concepts

Class: Trivial concepts

Parameter: Teaching Dimension

Value: $1$

Order: $\Omega(1)$

Name: Star number of Tagged Singletons

Class: Tagged Singletons

Parameter: Star number

Value: $n-1$

Order: $\Omega(n)$

Name: Star number of Full Cube

Class: Full Cube

Parameter: Star number

Value: $n$

Order: $\Omega(n)$

Name: Star number of Singletons plus empty set

Class: Singletons plus empty set

Parameter: Star number

Value: $n$

Order: $\Omega(n)$

Name: Star number of Singletons

Class: Singletons

Parameter: Star number

Value: $n-1$

Order: $\Omega(n)$

Name: Star number of Trivial concepts

Class: Trivial concepts

Parameter: Star number

Value: $1$

Order: $\Omega(1)$

Name: co-VC dimension of Addressing

Class: Addressing

Parameter: co-VC dimension

Value: $n$

Order: $\Omega(n)$

Name: co-VC dimension of Tagged Singletons

Class: Tagged Singletons

Parameter: co-VC dimension

Value: $2$

Order: $\Omega(1)$

Name: co-VC dimension of Half-intervals

Class: Half-intervals

Parameter: co-VC dimension

Value: $2$

Order: $\Omega(1)$

Name: co-VC dimension of Full Cube

Class: Full Cube

Parameter: co-VC dimension

Value: $n$

Order: $\Omega(n)$

Name: co-VC dimension of Singletons plus empty set

Class: Singletons plus empty set

Parameter: co-VC dimension

Value: $2$

Order: $\Omega(1)$

Name: co-VC dimension of Singletons

Class: Singletons

Parameter: co-VC dimension

Value: $n$

Order: $\Omega(n)$

Name: co-VC dimension of Trivial concepts

Class: Trivial concepts

Parameter: co-VC dimension

Value: $2$

Order: $\Omega(1)$

Name: Largest Strongly Shattered Set of Addressing

Class: Addressing

Parameter: Largest Strongly Shattered Set

Value: $0$

Order: $\Omega(1)$

Name: Largest Strongly Shattered Set of Half-intervals

Class: Half-intervals

Parameter: Largest Strongly Shattered Set

Value: $1$

Order: $\Omega(1)$

Name: Star number of Half-intervals

Class: Half-intervals

Parameter: Star number

Value: $2$

Order: $\Omega(1)$

Name: Monotone Recursive Teaching Dimension of Trivial concepts

Class: Trivial concepts

Parameter: Monotone Recursive Teaching Dimension

Value: $1$

Order: $\Omega(1)$

Name: Minimum Teaching Set Size of Trivial concepts

Class: Trivial concepts

Parameter: Minimum Teaching Set Size

Value: $1$

Order: $\Omega(1)$

Name: Membership and Equivalence Queries Complexity of Trivial concepts

Class: Trivial concepts

Parameter: Membership and Equivalence Queries Complexity

Value: $1$

Order: $\Omega(1)$

Name: Oriented Diameter of Singletons plus empty set

Class: Singletons plus empty set

Parameter: Oriented Diameter

Value: $1$

Order: $\Omega(1)$

Name: Oriented Diameter of Singletons

Class: Singletons

Parameter: Oriented Diameter

Value: $1$

Order: $\Omega(1)$

Name: Maximum Degree of Tagged Singletons

Class: Tagged Singletons

Parameter: Maximum Degree

Value: $\left\lceil\frac{n}{2}\right\rceil$

Order: $\Omega(n)$

Name: Maximum Degree of Addressing

Class: Addressing

Parameter: Maximum Degree

Value: $0$

Order: $\Omega(1)$

Name: Maximum Degree of Majority

Class: Majority

Parameter: Maximum Degree

Value: $n$

Order: $\Omega(n)$

Name: Maximum Degree of Half-intervals

Class: Half-intervals

Parameter: Maximum Degree

Value: $2$

Order: $\Omega(1)$

Name: Maximum Degree of Singletons plus empty set

Class: Singletons plus empty set

Parameter: Maximum Degree

Value: $n$

Order: $\Omega(n)$

Name: Maximum Degree of Full Cube

Class: Full Cube

Parameter: Maximum Degree

Value: $n$

Order: $\Omega(n)$

Name: Maximum Degree of Singletons

Class: Singletons

Parameter: Maximum Degree

Value: $0$

Order: $\Omega(1)$

Name: Maximum Degree of Trivial concepts

Class: Trivial concepts

Parameter: Maximum Degree

Value: $0$

Order: $\Omega(1)$

Name: Log Shattering of Singletons

Class: Singletons

Parameter: Log Shattering

Value: $\log n$

Order: $\Omega(\log n)$

Name: Order Sample Compression of Singletons

Class: Singletons

Parameter: Order Sample Compression

Value: $1$

Order: $\Omega(1)$

Name: Proper Ordered Sample Compression of Singletons

Class: Singletons

Parameter: Proper Ordered Sample Compression

Value: $n-1$

Order: $\Omega(n)$

Name: Effective VC Radius of Singletons

Class: Singletons

Parameter: Effective VC Radius

Value: $1$

Order: $\Omega(1)$

Name: Yang dimension of Singletons

Class: Singletons

Parameter: Yang dimension

Value: $n-1$

Order: $\Omega(n)$

Name: Partial Equivalence Queries Complexity of Singletons

Class: Singletons

Parameter: Partial Equivalence Queries Complexity

Value: $1$

Order: $\Omega(1)$

Name: Membership and Equivalence Queries Complexity of Singletons

Class: Singletons

Parameter: Membership and Equivalence Queries Complexity

Value: $1$

Order: $\Omega(1)$

Name: Minimum Teaching Set Size of Singletons

Class: Singletons

Parameter: Minimum Teaching Set Size

Value: $1$

Order: $\Omega(1)$

Name: Monotone Recursive Teaching Dimension of Singletons

Class: Singletons

Parameter: Monotone Recursive Teaching Dimension

Value: $1$

Order: $\Omega(1)$

Name: Teaching Dimension of Singletons

Class: Singletons

Parameter: Teaching Dimension

Value: $1$

Order: $\Omega(\log n)$

Name: Membership and Proper Equivalence Queries Complexity of Singletons

Class: Singletons

Parameter: Membership and Proper Equivalence Queries Complexity

Value: $n$

Order: $\Omega(n)$

Name: Projected Membership Queries Complexity of Singletons

Class: Singletons

Parameter: Projected Membership Queries Complexity

Value: $n$

Order: $\Omega(n)$

Name: Membership Query Complexity of Singletons

Class: Singletons

Parameter: Membership Query Complexity

Value: $n$

Order: $\Omega(n)$

Name: Order Sample Compression of Trivial concepts

Class: Trivial concepts

Parameter: Order Sample Compression

Value: $1$

Order: $\Omega(1)$

Name: Proper Ordered Sample Compression of Trivial concepts

Class: Trivial concepts

Parameter: Proper Ordered Sample Compression

Value: $1$

Order: $\Omega(1)$

Name: Projected VC Radius of Trivial concepts

Class: Trivial concepts

Parameter: Projected VC Radius

Value: $1$

Order: $\Omega(1)$

Name: Effective VC Radius of Trivial concepts

Class: Trivial concepts

Parameter: Effective VC Radius

Value: $1$

Order: $\Omega(1)$

Name: Yang dimension of Trivial concepts

Class: Trivial concepts

Parameter: Yang dimension

Value: $1$

Order: $\Omega(1)$

Name: Partial Equivalence Queries Complexity of Trivial concepts

Class: Trivial concepts

Parameter: Partial Equivalence Queries Complexity

Value: $1$

Order: $\Omega(1)$

Name: Largest Strongly Shattered Set of Full Cube

Class: Full Cube

Parameter: Largest Strongly Shattered Set

Value: $n$

Order: $\Omega(n)$

Name: Largest Strongly Shattered Set of Singletons plus empty set

Class: Singletons plus empty set

Parameter: Largest Strongly Shattered Set

Value: $1$

Order: $\Omega(1)$

Name: Largest Strongly Shattered Set of Singletons

Class: Singletons

Parameter: Largest Strongly Shattered Set

Value: $0$

Order: $\Omega(1)$

Name: Largest Strongly Shattered Set of Trivial concepts

Class: Trivial concepts

Parameter: Largest Strongly Shattered Set

Value: $0$

Order: $\Omega(1)$

Name: Threshold Dimension of Singletons

Class: Singletons

Parameter: Threshold Dimension

Value: $1$

Order: $\Omega(1)$

Name: Size of Addressing

Class: Addressing

Parameter: Size

Value: $n$

Order: $\Omega(n)$

Name: Size of Majority

Class: Majority

Parameter: Size

Value: $2^n$

Order: $\Omega(2^n)$

Name: Size of Tagged Singletons

Class: Tagged Singletons

Parameter: Size

Value: $n+\lceil\log n\rceil +1$

Order: $\Omega(n)$

Name: Size of Half-intervals

Class: Half-intervals

Parameter: Size

Value: $n$

Order: $\Omega(n)$

Name: Size of Singletons plus empty set

Class: Singletons plus empty set

Parameter: Size

Value: $n+1$

Order: $\Omega(n)$

Name: Size of Full Cube

Class: Full Cube

Parameter: Size

Value: $2^n$

Order: $\Omega(2^n)$

Name: Size of Singletons

Class: Singletons

Parameter: Size

Value: $n$

Order: $\Omega(n)$

Name: Path Dimension of Trivial concepts

Class: Trivial concepts

Parameter: Path Dimension

Value: $1$

Order: $\Omega(1)$

Name: Threshold Dimension of Trivial concepts

Class: Trivial concepts

Parameter: Threshold Dimension

Value: $1$

Order: $\Omega(1)$

Name: Hamming Radius of Trivial concepts

Class: Trivial concepts

Parameter: Hamming Radius

Value: $\left\lceil \frac{n}{2}\right\rceil$

Order: $\Omega(n)$

Name: Diameter of Trivial concepts

Class: Trivial concepts

Parameter: Diameter

Value: $\left\lceil \frac{n}{2}\right\rceil$

Order: $\Omega(n)$

Name: Oriented Diameter of Trivial concepts

Class: Trivial concepts

Parameter: Oriented Diameter

Value: $n$

Order: $\Omega(n)$

Name: Size of Trivial concepts

Class: Trivial concepts

Parameter: Size

Value: $2$

Order: $\Omega(1)$

Name: VC Dimension of Tagged Singletons

Class: Tagged Singletons

Parameter: VC Dimension

Value: $1$

Order: $\Omega(1)$

Name: Hamming Radius of Tagged Singletons

Class: Tagged Singletons

Parameter: Hamming Radius

Value: $2$

Order: $\Omega(1)$

Name: Diameter of Tagged Singletons

Class: Tagged Singletons

Parameter: Diameter

Value: $4$

Order: $\Omega(1)$

Name: Oriented Diameter of Tagged Singletons

Class: Tagged Singletons

Parameter: Oriented Diameter

Value: $2$

Order: $\Omega(1)$

Name: Effective Range of Tagged Singletons

Class: Tagged Singletons

Parameter: Effective Range

Value: $n+\lceil \log n \rceil$

Order: $\Omega(n)$

Name: Effective Range of Addressing

Class: Addressing

Parameter: Effective Range

Value: $n+\lceil \log n\rceil$

Order: $\Omega(n)$

Name: Effective Range of Majority

Class: Majority

Parameter: Effective Range

Value: $n+1$

Order: $\Omega(n)$

Name: Effective Range of Half-intervals

Class: Half-intervals

Parameter: Effective Range

Value: $n$

Order: $\Omega(n)$

Name: Effective Range of Singletons plus empty set

Class: Singletons plus empty set

Parameter: Effective Range

Value: $n$

Order: $\Omega(n)$

Name: Effective Range of Full Cube

Class: Full Cube

Parameter: Effective Range

Value: $n$

Order: $\Omega(n)$

Name: VC Dimension of Singletons plus empty set

Class: Singletons plus empty set

Parameter: VC Dimension

Value: $1$

Order: $\Omega(1)$

Name: VC Dimension of Full Cube

Class: Full Cube

Parameter: VC Dimension

Value: $n$

Order: $\Omega(n)$

Name: VC Dimension of Singletons

Class: Singletons

Parameter: VC Dimension

Value: $1$

Order: $\Omega(1)$

Name: VC Dimension of Trivial concepts

Class: Trivial concepts

Parameter: VC Dimension

Value: $1$

Order: $\Omega(1)$

Name: Effective Range of Singletons

Class: Singletons

Parameter: Effective Range

Value: $n$

Order: $\Omega(n)$

Name: Threshold Dimension of Full Cube

Class: Full Cube

Parameter: Threshold Dimension

Value: $n$

Order: $\Omega(n)$

Name: Oriented Diameter of Full Cube

Class: Full Cube

Parameter: Oriented Diameter

Value: $n$

Order: $\Omega(n)$

Name: Threshold Dimension of Singletons plus empty set

Class: Singletons plus empty set

Parameter: Threshold Dimension

Value: $1$

Order: $\Omega(1)$

Name: Threshold Dimension of Tagged Singletons

Class: Tagged Singletons

Parameter: Threshold Dimension

Value: $2$

Order: $\Omega(1)$

Name: VC Dimension of Addressing

Class: Addressing

Parameter: VC Dimension

Value: $\log n$

Order: $\Omega(\log n)$

Name: Littlestone Dimension of Addressing

Class: Addressing

Parameter: Littlestone Dimension

Value: $\log n$

Order: $\Omega(\log n)$

Name: Littlestone Dimension of Tagged Singletons

Class: Tagged Singletons

Parameter: Littlestone Dimension

Value: $2$

Order: $\Omega(1)$

Name: Littlestone Dimension of Half-intervals

Class: Half-intervals

Parameter: Littlestone Dimension

Value: $\log n$

Order: $\Omega(\log n)$

Name: Littlestone Dimension of Full Cube

Class: Full Cube

Parameter: Littlestone Dimension

Value: $n$

Order: $\Omega(n)$

Name: Littlestone Dimension of Singletons plus empty set

Class: Singletons plus empty set

Parameter: Littlestone Dimension

Value: $1$

Order: $\Omega(1)$

Name: Littlestone Dimension of Singletons

Class: Singletons

Parameter: Littlestone Dimension

Value: $1$

Order: $\Omega(1)$

Name: Littlestone Dimension of Trivial concepts

Class: Trivial concepts

Parameter: Littlestone Dimension

Value: $1$

Order: $\Omega(n)$

Name: Proper Equivalence Queries Complexity of Full Cube

Class: Full Cube

Parameter: Proper Equivalence Queries Complexity

Value: $n$

Order: $\Omega(n)$

Name: Proper Equivalence Queries Complexity of Addressing

Class: Addressing

Parameter: Proper Equivalence Queries Complexity

Value: $n$

Order: $\Omega(n)$

Name: Proper Equivalence Queries Complexity of Tagged Singletons

Class: Tagged Singletons

Parameter: Proper Equivalence Queries Complexity

Value: $2$

Order: $\Omega(1)$

Name: Proper Equivalence Queries Complexity of Half-intervals

Class: Half-intervals

Parameter: Proper Equivalence Queries Complexity

Value: $\log n$

Order: $\Omega(\log n)$

Name: Proper Equivalence Queries Complexity of Singletons plus empty set

Class: Singletons plus empty set

Parameter: Proper Equivalence Queries Complexity

Value: $1$

Order: $\Omega(1)$

Name: Proper Equivalence Queries Complexity of Singletons

Class: Singletons

Parameter: Proper Equivalence Queries Complexity

Value: $n$

Order: $\Omega(n)$

Name: Proper Equivalence Queries Complexity of Trivial concepts

Class: Trivial concepts

Parameter: Proper Equivalence Queries Complexity

Value: $1$

Order: $\Omega(1)$

Name: No-Clashing Teaching Dimension of Full Cube

Class: Full Cube

Parameter: No-Clashing Teaching Dimension

Value: $\lceil n/2\rceil$

Order: $\Omega(n)$

Name: Log Size Ratio of Full Cube

Class: Full Cube

Parameter: Log Size Ratio

Value: $n/\log n$

Order: $\Omega(\log n)$

Name: Log Size Ratio of Singletons

Class: Singletons

Parameter: Log Size Ratio

Value: $1$

Order: $\Omega(1)$

Name: Log Size Ratio of Trivial concepts

Class: Trivial concepts

Parameter: Log Size Ratio

Value: $0$

Order: $\Omega(1)$

Name: Log Size of Addressing

Class: Addressing

Parameter: Log Size

Value: $\Omega(\log n)$

Order: $\Omega(\log n)$

Name: Log Size of Majority

Class: Majority

Parameter: Log Size

Value: $n$

Order: $\Omega(n)$

Name: Log Size of Tagged Singletons

Class: Tagged Singletons

Parameter: Log Size

Value: $\Omega(\log n)$

Order: $\Omega(\log n)$

Name: Log Size of Half-intervals

Class: Half-intervals

Parameter: Log Size

Value: $\log n$

Order: $\Omega(\log n)$

Name: Log Size of Singletons plus empty set

Class: Singletons plus empty set

Parameter: Log Size

Value: $\log(n+1)$

Order: $\Omega(\log n)$

Name: Log Size of Full Cube

Class: Full Cube

Parameter: Log Size

Value: $n$

Order: $\Omega(n)$

Name: Log Size of Singletons

Class: Singletons

Parameter: Log Size

Value: $\log n$

Order: $\Omega(\log n)$

Name: Log Size of Trivial concepts

Class: Trivial concepts

Parameter: Log Size

Value: $1$

Order: $\Omega(1)$

Name: Threshold Dimension of Addressing

Class: Addressing

Parameter: Threshold Dimension

Value: $\lceil \log n\rceil$

Order: $\Omega(\log n)$

Name: Threshold Dimension of Majority

Class: Majority

Parameter: Threshold Dimension

Value: $n$

Order: $\Omega(n)$

Name: Threshold Dimension of Half-intervals

Class: Half-intervals

Parameter: Threshold Dimension

Value: $n-1$

Order: $\Omega(n)$

Name: Oriented Diameter of Half-intervals

Class: Half-intervals

Parameter: Oriented Diameter

Value: $n$

Order: $\Omega(n)$