Journal article
A lower bound for families of Natarajan dimension d
A system F of functions {1, 2, …, n}→{1, 2, …, k} has Natarajan dimension at most d if no (d+1)-element subset A⊂X is 2-shattered. A is 2-shattered if for each x∈A there is a 2-element set Vx⊆{1, 2, …, k} such that for any choice of elements cx∈Vx, a function f∈F exists with f(x)=cx for all x∈A. We improve a lower bound of cdkdnd (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 k for d=1).
The problem of obtaining a tight bound is related to interesting questions in extremal graph theory.
Language: | English |
---|---|
Year: | 2001 |
Pages: | 189-195 |
ISSN: | 10960899 and 00973165 |
Types: | Journal article |
DOI: | 10.1006/jcta.2000.3160 |
ORCIDs: | Fischer, Paul |