Title Asocijacijske sheme
Title (english) Association schemes
Author Lucija Relić
Mentor Vedran Krčadinac (mentor)
Committee member Vedran Krčadinac (predsjednik povjerenstva)
Committee member Miljenko Huzak (član povjerenstva)
Committee member Dijana Ilišević (član povjerenstva)
Committee member Tomislav Pejković (član povjerenstva)
Granter University of Zagreb Faculty of Science (Department of Mathematics) Zagreb
Defense date and country 2022-09-29, Croatia
Scientific / art field, discipline and subdiscipline NATURAL SCIENCES Mathematics
Abstract Glavni promatrani objekti u ovom radu su asocijacijske sheme. Asocijacijska shema s d klasa je skup razapinjućih podgrafova G0,G1, . . . ,Gd koji particioniraju bridove potpunog grafa Kn, a imaju svojstvo da za svaka dva vrha x i y koji su susjedni u Gk broj vrhova z susjednih sa x u Gi i susjednih sa y u Gj ovisi samo o indeksima i, j, k. Taj broj označavamo sa pk i,j i nazivamo presječnim brojem sheme. Asocijacijske sheme možemo konstruirati pomoću distancijsko regularnih grafova, a najvažniji takvi primjeri su Johnsonova i Hammingova shema. Osim toga, vrlo su važne i konstrukcije pomoću konačnih grupa. Matrice susjedstva grafova asocijacijske sheme razapinju komutativnu algebru koju nazivamo Bose-Mesnerovom algebrom. Pripadnu Bose-Mesnerovu algebru razapinju i idempotentne matrice određene svojstvenim potprostorima matrica sheme. Osim presječnih brojeva postoji još nekoliko bitnih parametara asocijacijske sheme kao što su svojstvene vrijednosti, dualne svojstvene vrijednosti i Kreinovi parametri, a imaju zanimljiva dualna svojstva. Asocijacijske sheme dobivene pomoću distancijsko regularnih grafova ekvivalentne su P-polinomijalnim shemama, a poznate su i karakterizacije pomoću presječnih brojeva, svojstvenih vrijednosti sheme i dijametara grafova. Postoje i Q-polinomijalne sheme s karakterizacijama preko dualnih pojmova, ali ne i kombinatorna interpretacija poput distancijsko regularnih grafova. Konkretni primjeri u diplomskom radu izračunati su pomoću GAP paketa AssociationSchemes.
Abstract (english) The main objects studied in this thesis are association schemes. An association scheme with d classes is a set of spanning subgraphs G0,G1, . . . ,Gd which partition the edges of the complete graph Kn and have the property that for every two vertices x and y which are adjacent in Gk the number of vertices z adjacent to x in Gi and adjacent to y in Gj depends only on the indices i, j, k. This number is denoted by pk i,j and called an intersection number of the scheme. We can construct association schemes using distanceregular graphs and the most important examples are Johnson and Hamming schemes. Constructions using Ąnite groups are very important as well. AThe adjacency matrices of association scheme graphs span a commutative algebra called the Bose-Mesner algebra. The Bose-Mesner algebra of the association scheme is also spanned by idempotent matrices which are determined by eigenspaces of the adjacency matrices. Apart from the intersection numbers, there are other important parameters of the association scheme such as eigenvalues, dual eigenvalues and Krein parameters. These parameters have interesting dual properties. Association schemes obtained from distance-regular graphs are equivalent to P-polynomial schemes, and can also be characterized via intersection numbers, eigenvalues of the scheme and diameters of its graphs. There are also Q-polynomial schemes with characterizations via dual terms, but no combinatorial interpretation such as distance-regular graphs is known. Examples in the thesis were calculated using the GAP package AssociationSchemes.
Keywords
skup razapinjućih podgrafova
presječni broj sheme
distancijsko regularni grafovi
Johnsonova shema
Hammingova shema
konačne grupe
Bose-Mesnerova algebra
svojstvene vrijednosti
dualne svojstvene vrijednosti
Kreinovi parametri
P-polinomijalne sheme
Q-polinomijalne sheme
Keywords (english)
set of spanning subgraphs
intersection number of the scheme
distanceregular graphs
Johnson schemes
Hamming schemes
Bose-Mesner algebra
eigenvalues
dual eigenvalues
Krein's parameters
P-polynomial schemes
Q-polynomial schemes
GAP package AssociationSchemes
Language croatian
URN:NBN urn:nbn:hr:217:373687
Study programme Title: Mathematical Statistics Study programme type: university Study level: graduate Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
Type of resource Text
File origin Born digital
Access conditions Open access
Terms of use
Created on 2022-11-08 11:12:43