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.