A generalization of Sauer's lemma (Q1899068): Difference between revisions

The authors generalize \textit{N. Sauer's} lemma [ibid. 13, 145-147 (1972; Zbl 0248.05005)] to multivalued functions, proving tight bounds on the cardinality of subsets of \(\prod^m_{i= 1} \{0,\dots, N_i\}\) which avoid certain patterns. In addition, the authors give an application of this result, bounding the uniform rate of convergence of empirical estimates of the expectations of a set of random variables to their true expectations.