Stein-Lovasz定理的推廣及其應用

Abstract

Stein-Lov?asz定理提供一個演算法的方式來找出好的覆 蓋(covering)，並且可以用來處理一些組合問題，找出它們的上 界。為了可以用來處理更多的組合問題，在這篇論文裡，我 們將原先的Stein-Lov?asz定理作推廣。此外，我們將利用推廣後 的Stein-Lov?asz定理來處理一些模型，這些模型包括：分離矩 陣(disjunct matrices)、選擇器(selectors)以及系統集(set systems) ，在固定行(column)數的前提之下，分別去找出這些矩陣的最 小列(row)數的上界。其中分離矩陣和選擇器可以應用在匯集設 計(pooling design)上。

The Stein-Lov?asz theorem provides an algorithmic way to deal with the existence of good coverings and then to derive some upper bounds related to some combinatorial structures. In order to deal with more combinatorial problems, an extension of the classical Stein-Lov?asz theorem, called the extended Stein-Lov?asz theorem, will be given in this thesis. Moreover, we will also discuss applications of the extended Stein-Lov?asz theorem to various models stated as follows: 1. Several disjunct matrices (for group testing purpose) ? d-disjunct matrices, (d; z]-disjunct matrices; ? (d; r]-disjunct matrices, (d; r; z]-disjunct matrices; ? (d; r)-disjunct matrices, (d; r; z)-disjunct matrices; ? (d; s out of r]-disjunct matrices, (d; s out of r; z]-disjunct matrices. 2. Several selectors (for group testing purpose) ? (k; m; n)-selectors, (k; m; n; z)-selectors; ? (k; m; c; n)-selectors, (k; m; c; n; z)-selectors. 3. Some set systems (for others) ? uniform (m; t)-splitting systems, uniform (m; t; z)-splitting systems; ? uniform (m; t1; t2)-separating systems, uniform (m; t1; t2; z)-separating systems; ? (v; k; t)-covering designs, (v; k; t; z)-covering designs; ? (v; k; t; p)-lotto designs, (v; k; t; p; z)-lotto designs.