Poopćenje i profinjenje nekih algoritama za konstrukciju blokovnih dizajna i istraživanje njihovih podstruktura

doctoral thesis

• Title (english): Generalization and refinement of some algorithms for construction and substructures investigation of block designs
• Author: Doris Dumičić Danilović
• Mentor: Dean Crnković (mentor)
• Mentor: Sanja Rukavina (komentor)
• Committee member: Mario-Osvin Pavčević (predsjednik povjerenstva)
• Committee member: Dean Crnković (član povjerenstva)
• Committee member: Sanja Rukavina (član povjerenstva)
• Committee member: Vedran Krčadinac (član povjerenstva)
• Committee member: Vedrana Mikulić Crnković (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2014-11-20, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics
• Universal decimal classification (UDC): 51 - Mathematics

Abstract

U ovoj disertaciji opisani su algoritmi za konstrukciju blokovnih dizajna pomoću orbitnih matrica, uz pretpostavku djelovanja određene grupe na dizajn. Radi se o algoritmu za konstrukciju neizomorfnih točkovnih orbitnih matrica blokovnih dizajna s proizvoljnim dopustivim parametrima na koje djeluje proizvoljna grupa. Taj je algoritam generalizacija algoritma za konstrukciju neizomorfnih blokovnih orbitnih matrica simetričnih dizajna, opisanog u članku [21]. U sklopu ove disertacije, razvili smo i algoritam za profinjenje (dekompoziciju) orbitnih matrica koji se temelji na primjeni kompozicijskog niza rješive grupe automorfizama blokovnih dizajna. Opisani algoritmi implementirani su u programsku podršku napisanu u programu GAP ([25]). Pomoću razvijenih programa napravljena je klasifikacija 2-(45, 5, 1) dizajna na koje djeluje automorfizam reda šest, te klasifikacija 2-(45, 12, 3) dizajna na koje djeluje involutorni automorfizam. Isto tako, konstruirani su svi, do na izomorfizam, 2-(45, 5, 1) dizajni na koje djeluje grupa \(G\cong Z_{3}\times Z_{3}\) u slučajevima kada postoje dvije podgrupe reda tri u grupi G koje djeluju na dizajn tako da nemaju zajedničkih orbita točaka i blokova duljine tri. Konstruirani su također i 2-(45, 5, 1) dizajni na koje djeluje grupa \(S_{3}\). Osim toga, napravljena je klasifikacija 2-(78, 22, 6) dizajna na koje djeluje grupa \(F rob_{39} \times Z_{2}\), pri čemu se u ovom slučaju algoritam za profinjenje orbitnih matrica temelji na primjeni glavnog niza konkretne grupe koja djeluje na taj dizajn. Jedan od bitnih rezultata ove disertacije je dokaz da ne postoji (78, 22, 6) diferencijski skup u grupi \(F rob_{39} \times Z_{2}\), a dobiven je primjenom spomenutih programa. U sklopu ovog rada razvili smo modificirane genetske algoritme za traženje unitala i drugih poddizajna, pretraživanjem matrica incidencije (simetričnih) blokovnih dizajna. Ti su algoritmi implementirani u programsku podršku napisanu u Matlab-u. Pronađeni su unitali u simetričnim 2-(66, 26, 10) i 2-(36, 15, 6) dizajnima i 2-(11, 5, 2) poddizajni u simetričnim 2-(66, 26, 10) dizajnima.

Abstract (english)

In this thesis we describe the algorithms for construction of block designs admitting an action of an automorphism group using orbit matrices. We develop and describe a program which constructs mutually nonisomorphic orbit matrices for arbitrary block design and automorphism group, which is a generalisation of the program for obtaining orbit matrices for some symmetric design and automorphism group described in the paper [21]. The second step in the construction is often called an indexing of orbit matrices, respectively construction of block designs from orbit matrices. Indexing often lasts too long, therefore we develop an algorithm for the refinement of orbit matrices, based on the application of the composition series of the solvable automorphism group which acts on design. Mentioned algorithms are used as a base for computer programs written in program GAP. Classification of all 2-(45, 5, 1) designs admitting an action of an automorphism of order 6 and classification of all 2-(45, 12, 3) designs admitting an action of an involution is presented. Moreover, we have constructed all, up to isomorphism, 2-(45, 5, 1) designs admitting an action of group \(Z_{3}\times Z_{3}\) in the cases when there exist two subgroups of order 3 in the group \(Z_{3}\times Z_{3}\) that act on the design having no common point and block orbits of length 3. Besides this, we have constructed 2-(45, 5, 1) designs admitting an action of group \(S_{3}\). The classification of all 2-(78, 22, 6) admitting an action of group \(G \cong F rob_{39} \times Z_{2}\) is presented. In this case, the algorithm for the refinement of orbit matrices is based on the application of the principal series of the group G. An important result of the thesis is the proof that there does not exists (78,22,6) difference set in the group G. Besides that, the subject of the thesis is to examine the existence of certain subdesignes in a block designs using an incomplete search with a modified genetic algorithm, in case when complete methods (exhaustive search) do not give enough or any results in a reasonable period of time. Therefore modified genetic algorithms for finding subdesigns probing incidence matrices for some block designs we develop and describe. Modified genetic algorithm for finding unitals in symmetric designs is applied on search for unitals in symmetric designs with parameters 2-(66,26,10) and 2-(36,15,6). Moreover, modified genetic algorithm for finding subdesigns with given parameters in arbitrary block design is applied on search for 2-(11, 5, 2) subdesigns in 2-(66, 26, 10) designs.

• Keywords: konstrukcija blokovnih dizajna; orbitne matrice; neizomorfne točkovne orbitne matrice blokovnih dizajna
• Keywords (english): construction of block designs; orbit matrices; mutually nonisomorphic orbit matrices for arbitrary block design
• Language: croatian
• URN:NBN: urn:nbn:hr:217:134492
• Study programme: Title: Mathematics; Study programme type: university; Study level: postgraduate; Academic / professional title: doktor/doktorica znanosti, područje prirodnih znanosti, polje matematika (doktor/doktorica znanosti, područje prirodnih znanosti, polje matematika)
• Type of resource: Text
• Extent: ii, 128 str.
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-03-08 10:27:58