Colloquium: Charles Colbourn

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