Block designs, semidefinite matrices and association schemes
Coding and Information Transmission Group
Association schemes are an important tool in algebraic design and coding theory. A block design is a collection of subsets of size k of a set of size v (called blocks), with the property that every two distinct points are contained in a constant number l of blocks. In this research problem, we first translate the defining design properties to properties of the incidence matrix of the design, and use this to build a 3-dimensional matrix algebra. Then we use decomposition techniques to find a nonnegative semidefinite matrix in this algebra. Finally, we use the properties of such matrices, namely that principal minors are nonnegative, to derive inequalities for the design-parameters. The inequalities that are obtained from minors of size 1 and 2 are known. In these cases, it is possible to bring these inequalities in a special, nice form. The problem is to investigate the inequalities obtained from higher-order minors, and to see if they can be given similar nice forms. The techniques that are used generalize to so-called (Q-polynomial) association schemes, algebraic constructions invented specially to study certain regular combinatorial structures. Some background study into semidefinite matrices and association schemes is possible, and extensions to association schemes and possible other applications can be considered, if there is enough time.
Lõputöö kaitsmise aasta
Henk D.L. Hollmann, Vitaly Skachek
Some background in combinatorics and/or coding theory would help but is not required. For a master-level thesis some knowledge of linear algebra and algebraic structures (groups, rings) is probably needed.
Henk D.L. Hollmann