Our methods are in a sense purely ``linear algebraic''. Our starting point is the formulation of the problem by means of r dimensional arrays of reals and a simple approximation of these arrays by the sum of ``rank 1'' arrays. A central result we prove and use is an upper bound on a certain norm of a random sub-array of an r dimensional array in terms of the same norm of the whole array. The norm is chosen to model these combinatorial problems.
Joint work with N. Alon, F.W. dela Vega and M. Karpinski