A system F of functions {1, 2,..., n} --> {1, 2,..., k} has Natarajan dimension at most d if no (d + 1)-element subset A subset of X is 2-shattered. A is 2-shattered if for each x is an element of A there is a 2-element set V-x subset of or equal to {1, 2,..., k} such that for any choice of elements c(x) is an element of V-x, a function f is an element of F exists with f(x) = c(x) for all x is an element of A. We improve a lower bound of c(d)k(d)n(d) (due to Haussler and Long) for the maximum size of F of Natarajan dimension at most d by a factor somewhat smaller than k (e.g., by rootk for d = 1). The problem of obtaining a tight bound is related to interesting questions in extremal graph theory. (C) 2001 Academic Press. [References: 12]
展开▼
