Small transversals in hypergraphs

For each positive integerk, we consider the setA _k of all ordered pairs a, b] such that in everyk-graph withn vertices andm edges some set of at mostam+bn vertices meets all the edges. We show that eachA _k withk2 has infinitely many extreme points and conjecture that, for every positive , it has only finitely many extreme points a, b] witha. With the extreme points ordered by the first coordinate, we identify the last two extreme points of everyA _k , identify the last three extreme points ofA ₃, and describeA ₂ completely. A by-product of our arguments is a new algorithmic proof of Turán's theorem.