Departmental PhD Thesis Exam – Nevena Francetic

Everyone welcome.  Refreshments will be served in the Math Lounge before the exam.

Tuesday, May 29, 2012, 10:10 a.m., in BA 6183, 40 St. George Street

PhD Candidate: Nevena Francetic

Thesis Title: Covering Arrays with Row Limit
(http://www.math.toronto.edu/nfrancet/mojaTeza.pdf)

Thesis Abstract:

Covering arrays with row limit, CARLs for short, are a generalization of group divisible designs and covering arrays. Similarly to their predecessor, CARLs have a natural application as combinatorial models for interaction test suites. A CARL(N;t,k,v: w), is an N×k array with some empty cells. A component, which is represented by a column, takes values from a v-set called the alphabet. In each row, there are exactly w non-empty cells, that is the corresponding components have an assigned value from the alphabet. The parameter w is called the row limit. Moreover, any N×t subarray contains every of v^t distinct t-tuples of alphabet symbols at least once.

This thesis is concerned with the bounds on the size and constructions of CARLs when the row limit w(k) is a positive integer valued function of the number of columns, k. Here we give a lower bound, and probabilistic and algorithmic upper bounds for any CARL. Further, we find improvements on the upper bounds when w(k)lnw(k) = o(k) and when w(k) is a constant function. We also determine the asymptotic size of CARLs when w(k) = Θ(k) and when w(k) is constant.

Next, we study constructions of CARLs. We provide two combinatorial constructions of CARLs, which we apply to construct families of CARLs with w(k) = ck, where c < 1.  Also, we construct optimal CARLs when t = 2 and w = 4, and prove that there exists a constant δ, such that for any v and k ≥ 4, an optimal CARL(2,k,v: 4) differs from the lower bound by at most δ rows, with some possible exceptions.

Finally, we define a packing array with row limit, PARL(N;t,k,v: w), the same as a CARL(N;t,k,v: w) with the difference that any t-tuple is contained at most once in any N × t subarray. We find that when w(k) is a constant function, the results on the asymptotic size of CARLs imply the results on the asymptotic size of PARLs. Also, when t = 2, we consider a transformation of optimal CARLs with row limit w = 3 to optimal PARLs with w = 3.