Abstract: For a finite set , we say that a set crosses a partition of if intersects partition classes. If , this means that meets all classes , whilst for the elements of the crossing set belong to mutually distinct classes. A set system crosses , if so does some . The minimum number of -element subsets, such that every -partition of an -element set is crossed by at least one of them, is denoted by . The problem of determining these minimum values for was raised and studied by several authors, first by Sterboul in 1973 [Proc. Colloq. Math. Soc. J. Bolyai, Vol. 10, Keszthely 1973, North-Holland/American Elsevier, 1975, pp. 1387--1404]. The present authors determined asymptotically tight estimates on for every fixed as [Graphs Combin., 25 (2009), 807--816]. Here we consider the more general problem for two parameters and , and establish lower and upper bounds for . For various combinations of the three values we obtain asymptotically tight estimates, and also point out close connections of the function to Tur'an-type extremal problems on graphs and hypergraphs, or to balanced incomplete block designs.
