Details:
Speaker: Charles Colbourn, Arizona State
Title: Disjoint Spread Systems and Fault Location
Abstract: A \(v\)-spread on an \(n\)-set \(X\) is a partition of \(X\) into \(v\) subsets.Two spreads are disjoint if they have no subset in common. A \((n;k,v)\)-disjoint spread system is a set of \(k\) mutually disjoint \(v\)-spreads of an \(n\)-set. We explore two questions in this talk.
(1) Given \(k\) and \(v\), what is the smallest set size \(n\) for which an \((n;k,v)\)-disjoint spread system exists?
(2) Other than mathematical curiosity, why should one care about the first question?
To partially answer the second question, we outline a surprising connection with the location of faulty components in a large component-based system. Indeed we find that disjoint spread systems correspond to the first nontrivial case for test suites known as locating arrays.
We then give a complete and exact answer to the first question by addressing the equivalent one: Given \(n\) and \(v\), what is the largest value of \(k\) for which an \((n;k,v)\)-disjoint spread system exists? The key is to form \(k\) integer partitions of \(n\) each having \(v\) parts, so that the total number of occurrences of the part \(i\) is at most \(n \choose i\) whenever \(0 \leq i \leq n\). Using a generalization of Baranyai's theorem (established using a beautiful method by Brouwer and Schrijver) we establish that such integer partitions always yield an \((n;k,v)\)-disjoint spread system. To complete the determination, we present an explicit set of integer partitions; using binomial inequalities, we establish that the set is feasible and that it is maximum.
This is joint work with Bingli Fan (Beijing Jiaotong) and Daniel Horsley (Monash).
Host: Jessica McDonald
|
