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.