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.