Orthogonal Arrays; Enumeration and Applications

Demirkale, Fatih (2013). Orthogonal Arrays; Enumeration and Applications PhD Thesis, School of Mathematics and Physics, The University of Queensland.

       
Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
s42201049_phd_finalthesis.pdf Thesis full text application/pdf 854.47KB 8
Author Demirkale, Fatih
Thesis Title Orthogonal Arrays; Enumeration and Applications
School, Centre or Institute School of Mathematics and Physics
Institution The University of Queensland
Publication date 2013
Thesis type PhD Thesis
Supervisor Diane Donovan
Benjamin A. Burton
Deborah J. Street
Total pages 157
Total black and white pages 157
Language eng
Subjects 010104 Combinatorics and Discrete Mathematics (excl. Physical Combinatorics)
010499 Statistics not elsewhere classified
080201 Analysis of Algorithms and Complexity
Formatted abstract
An orthogonal array OA(N, k, s, t) of strength t is anX k array with elements from an ordered set of s symbols such that any N X t subarray has each t-tuple appearing as a row λ times.

    Orthogonal arrays are used in the design of experiments in statistics and in many elds of combinatorics including coding theory and cryptography. They are also important in software testing and have applications in computer science. Orthogonal arrays are also closely related to some combinatorial structures such as mutually orthogonal Latin squares, nite projective planes and Hadamard matrices.

    In this thesis, we apply orthogonal arrays to construct D-optimal discrete choice experiments. We give new constructions for discrete choice experiments in which all attributes have the same number of levels. These constructions use several combinatorial structures, such as orthogonal arrays, balanced incomplete block designs and Hadamard matrices. If we assume that only the main eects of the attributes are to be used to explain the results and that all attribute level combinations are equally attractive, we show that the constructed discrete choice experiments are D-optimal.

    Later we describe new algorithms to enumerate all orthogonal arrays with given parameters. Key techniques include eliminating signicant space requirements, using previously-computed information on substructures in an efficient way, and using efficient vertex- invariants for nauty. Computational results show these algorithms to be signicantly faster than the prior state-of-the-art, and we use them to give some new enumeration results.

    In this thesis, we also study the enumeration of non-isomorphic three column orthogonal arrays on three symbols, and we study an asymptotic formula for the number of OA(N, 3, 3, 2). Later we identify a set of s(s - 1)2 Latin squares and represent these as vectors. We show these vectors can be used to form intercalates which form a basis for a linear space which contains all Latin trades. We also show that (s - 1)3 + 1 of these vectors are linearly independent. We use this theory to study an asymptotic formula for the number of OA(N, 3, s, 2) for s ≥ 3, and we show that for a given s, the number of OA(N, 3, s, 2) is λ(s-1)3(1-o(1)) as λ →∞.

    Lastly we study intersection numbers for two simple 2-fold (3s, s, 3) group divisible designs or equivalently two simple OA(2 • s2, 3, s, 2)s for s ≥ 2. More precisely, we develop constructions which show that there exists two simple 2-fold (3s, s, 3) group divisible designs which intersect in precisely K 2 {0, 1, 2,..., 2s2}\ {2s2 -1, 2s2 -2, 2s2 -3, 2s2 -5}
triples for s ≥ 5. There are some exceptions for s = 3, 4.

    This thesis contributes to the general body of knowledge on existence, enumeration and applications of orthogonal arrays.
Keyword Orthogonal arrays
Discrete choice experiments
Stated preference experiments
D-optimal designs
Block designs
Latin squares
Combinatorial enumeration
nauty
Intersection problem
Group divisible designs
Quasigroups

 
Citation counts: Google Scholar Search Google Scholar
Created: Mon, 23 Sep 2013, 13:26:03 EST by Fatih Demirkale on behalf of Scholarly Communication and Digitisation Service