COSAM » Events » 2016 » January » Colloquium: Charles Colbourn

 Colloquium: Charles Colbourn Time: Jan 29, 2016 (04:00 PM) Location: SCC 115 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

Last updated: 01/22/2016