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.