arvutiteaduse instituudi lõputööde teemade register

Block designs, semidefinite matrices and association schemes
Organisatsiooni nimiCoding and Information Transmission Group
KokkuvõteAssociation 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 aasta2022-2023
JuhendajaHenk D.L. Hollmann, Vitaly Skachek
Suhtlemiskeel(ed)inglise keel
Nõuded kandideerijaleSome 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.
Tase Bakalaureus, Magister
Märksõnad #coding, #combinatorics, #designs, #algebra, #association_scheme
Kandideerimise kontakt
Nimi Henk D.L. Hollmann
Tel +31 619489142