Covering arrays and qualitative independence graphs

电路、软件和网络的彻底测试是至关重要的，但它经常被忽视，因为它可能很复杂和耗时。许多研究人员试图找到测试方案，以减少测试系统所需的工作量，同时仍有一套严格的测试。其中一种方案是由一种称为覆盖阵列的设计确定的。覆盖数组描述了完全测试系统中的每一对参数，而不是完全测试系统中所有可能的参数集的方案。这导致了既有效又高效的测试。对这种测试方案的进一步改进是仅测试已知相互作用的参数对。由于相互作用的对集可以被记录在图结构中，这导致了一种被称为图上的覆盖数组的求精。该研究程序包括寻找覆盖数组的结构，确定覆盖数组的大小的界，以及确定给定图上的覆盖数组是否存在。在我的研究中的一个新的方法是，我定义了一族图，它的性质是给定图上的覆盖数组存在当且仅当给定图到族中的图有图同态。这类图具有特殊的性质，使得它特别适合于代数图论中的方法。这种新的方法允许应用图论的结果和使用代数方法来研究覆盖数组。这个研究程序借鉴了数学中许多不同领域的理论。例如，覆盖阵列子族的关键结果是极值有限集合论中众所周知的定理的直接结果。该研究计划包括将这些结果自然扩展到一般覆盖阵列。

Thorough testing of circuits, software and networks is critical but it is often neglected since it can be complicated and time consuming.  Researchers have tried to find testing schemes that would reduce the amount of work required to test a system, while still having a rigorous set of tests. One such scheme is determined by a design called a covering array. A covering array describes a scheme that completely tests every pair of parameters in the system, rather than completely testing all possible sets of parameters in a system. This leads to testing that is both effective and efficient. A further improvement on such a testing scheme is to test only pairs of parameters that are known to interact. Since the set of pairs which interact can be recorded in a graph structure, this leads to a refinement, called a covering array on a graph.This research program includes finding constructions for covering arrays, determining bounds on the size of a covering array, and deciding if a covering array on a given graph exists. A novel approach in my research is that I have defined a family of graphs which have the property that a covering array on a given graph exists if and only if there is a graph homomorphism of the given graph to a graph in the family. This family of graphs has special properties that make it particularly well-suited to methods from algebraic graph theory. This new approach allows for the application of results from graph theory and the use of algebraic methods to study covering arrays.This research program draws on theory in a number of disparate fields in mathematics. For example, key results for a sub-family of covering arrays are a direct consequence of well-known theorems in extremal finite set theory. This research program includes developing the natural extension of these results to general covering arrays.