The Stern-Lovász Theorem And Its Applications To Some Combinatorial Arrays

The probabilistic method is a powerful tool for solving many problems in Combinatorics and Graph Theory. Roughly speaking, the method works as follows: to prove that a structure with certain desired properties exists, define an appropriate probability space of structures and then show that the desired properties hold in this space with positive probability. The advantage of the probabilistic method is: to prove that a structure with certain desired properties exists, we do not need to construct the specific structure but only an appropriate probability space.Although the probabilistic method is powerful, we can only get a conclusion on whether a structure with certain desired properties exists. However, in many applications, we need not only this conclusion, but also such a structure to perform calculation on.The Stern-Lovász theorem can be used to do existence analysis for some combinational problems, which shows more constructive features compared with the probabilistic methods.In this thesis, we first give a brief proof of the Stern-Lovász theorem, then discuss about applications of the Stern-Lovász theorem to some combinational set systems and arrays, including perfect hash families, separating hash families, splitting systems and covering designs. We also compare some of the boundaries obtained from the Stern-Lovász theorem with those from the basic probabilistic method.We conclude that the results from the Stern-Lovász theorem and the basic probabilistic method are approximately the same, but the results of the Stern-Lovász theorem shows stronger constructive features. Therefore, the Stern-Lovász theorem, in some sense, can be regarded as the de-ramdomized algorithm for the basic probabilistic methods for the discussed problems.