Separating systems and oriented graphs of diameter two

We prove results on the size of weakly and strongly separating set systems and matrices, and on cross-intersecting systems. As a consequence, we improve on a result of Katona and Szemerédi [G. Katona, E. Szemerédi, On a problem of graph theory, Studia Sci. Math. Hungar. 2 (1967) 23–28], who proved that the minimal number of edges in an oriented graph of order n with diameter 2 is at least ( n / 2 ) log 2 ( n / 2 ) . We show that the minimum is ( 1 + o ( 1 ) ) n log 2 n .