The Stein-Lovdsz Theorem and Its Applications to Some Combinatorial Arrays

Abstract

The Stein-Lovasz Theorem can be used to get existence results for some combinatorial problems using constructive methods rather than probabilistic methods. In this paper, we discuss applications of the Stein-Lovasz Theorem to some combinatorial set systems and arrays, including perfect hash families, separating hash families, splitting systems, covering designs, lotto designs and $A$-free systems. We also compare some of the bounds obtained from the Stein-Lovasz Theorem to those using the basic probabilistic method.