The epsilon-net story
by Professor Janos Pach
Abstract: In 1986, Haussler and Welzl introduced the notion of epsilon-nets and adapted a theorem of Vapnik-Chervonenkis to establish the existence of small epsilon-nets in hypergraphs (range spaces) of small "dimension." Since then epsilon-net theory has been successfully applied in machine learning, in discrete and computational geometry and elsewhere. It has been an outstanding open problem to determine the size of the smallest epsilon-net that can be found in every hypergraph. We summarize the last chapter of the story, and describe some recent geometric constructions found by the speaker and by Gabor Tardos.