Asocijacijske sheme

master's thesis

• 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
• Created on: 2022-11-08 11:12:43