SMALL TRANSVERSALS IN HYPERGRAPHS

For each positive integer k, we consider the set A(k) of all ordered pairs [a, b] such that in every k-graph with n vertices and m edges some set of at most am + bn vertices meets all the edges. We show that each A(k) with k greater-than-or-equal-to 2 has infinitely many extreme points and conjecture that, for every positive-epsilon, it has only finitely many extreme points [a, b] with a greater-than-or-equal-to epsilon. With the extreme points ordered by the first coordinate, we identify the last two extreme points of every A(k), identify the last three extreme points of A3, and describe A2 completely. A by-product of our arguments is a new algorithmic proof of Turan's theorem.