Oznaka poročila: ARRS-RPROJ-ZP-2015/181 Е!!Ј:Ш-1.!.1 feäLÄ ZAKLJUČNO POROČILO RAZISKOVALNEGA PROJEKTA A. PODATKI O RAZISKOVALNEM PROJEKTU 1.Osnovni podatki o raziskovalnem projektu Šifra projekta J1-4010 Naslov projekta Dvodelni razdaljno-regularni grafi Vodja projekta 21656 Štefko Miklavič Tip projekta J Temeljni projekt Obseg raziskovalnih ur 4818 Cenovni razred A Trajanje projekta 07.2011 - 06.2014 Nosilna raziskovalna organizacija 1669 Univerza na Primorskem, Inštitut Andrej Marušič Raziskovalne organizacije -soizvajalke 588 Univerza v Ljubljani, Pedagoška fakulteta Raziskovalno področje po šifrantu ARRS 1 NARAVOSLOVJE 1.01 Matematika 1.01.05 Teorija grafov Družbenoekonomski cilj Naravoslovne vede - RiR financiran iz drugih virov (ne iz SUF) Raziskovalno področje po šifrantu FOS 1 Naravoslovne vede 1.01 Matematika B. REZULTATI IN DOSEŽKI RAZISKOVALNEGA PROJEKTA 2.Povzetek raziskovalnega projekta1 SLO Glavni cilj predlaganega projekta je razumeti in klasificirati pomemben razred dvodelnih razdaljno-regularnih grafov. Naj bo Г dvodelen razdaljno-regularen graf premera D. Izberimo si vozlišče x grafa Г in naj bo T=T(x) pripadajoča Terwilligerjeva algebra. Centralni cilj tega projekta je klasificirati tiste grafe Г, ki do izomorfizma natančno premorejo največ dva nerazcepna T-modula s krajiščem 2, od katerih sta oba tanka. Za dosego tega cilja bomo v teku projekta poskušali rešiti vrsto problemov, ki so povezani z zgoraj omenjenim glavnim problemom. Naj omenimo dva: Problem 1: Pokaži, da sta naslednji dve trditvi ekvivalentni: (i) Graf Г ima do izomorfizma natančno največ dva nerazcepna T-modula s krajiščem 2, od katerih sta oba tanka. (ii) Za vsako naravno število i med 2 in D-2 obstajajo taka kompleksna števila a(i) in ß(i), tako da za poljubni vozlišči y in z (y je na razdalji 2 od x, z pa na razdalji i od x in y) velja, da je število sosedov vozlišča z, ki so na razdalji i-1 od vozlišč x in y, enako: a(i) + ß(i) (število skupnih sosedov vozlišč x in y, ki so na razdalji i-1 od vozlišča z). Problem 2: Pokaži, da sta naslednji dve trditvi ekvivalentni: (i) Graf Г je Q-polinomski. (ii) Za vsako naravno število i med 2 in D-1 obstajajo taka kompleksna števila a(i) in ß(i), tako da za poljubni vozlišči y in z (y je na razdalji 2 od x, z pa na razdalji i od x in y) velja, da je število sosedov vozlišča z, ki so na razdalji i-1 od vozlišč x in y, enako: a(i) + ß(i) (število skupnih sosedov vozlišč x in y, ki so na razdalji i-1 od vozlišča z). Za bolj natančno predstavitev projekta glej priloženo pdf datoteko "project_slo.pdf". ANG The main goal of the proposed project is to understand and classify a certain type of bipartite distance-regular graphs. To define this type let Г denote a bipartite distance-regular graph with diameter D. Let x denote a vertex of Г and let T=T(x) denote the associated Terwilliger algebra. In this project our central goal is to classify those Г for which up to isomorphism there exist at most two irreducible T-modules with endpoint 2, and they are both thin. To achieve this goal we will try to solve a series of related problems. Let us mention two: Problem 1: Show that the following (i), (ii) are equivalent. (i) Up to isomorphism Г has at most two irreducbile T-modules with endpoint 2, and they are both thin. (ii) For every integer i between 2 and D-2, there exist complex numbers a(i) and ß(i), such that for all vertices y and z (y being at distance 2 from x, and z being at distance i from both x and y) the following hold: the number of neighbours of z, which are at distance i-1 from both x and y is equal to: a(i) + ß(i) (the number of common neighbours of x and y, which are at distance i-1 from z). Problem 2: Show that the following (i), (ii) are equivalent. (i) Г is Q-polynomial. (ii) For every integer i between 2 and D-1, there exist complex numbers a(i) and ß(i), such that for all vertices y and z (y being at distance 2 from x, and z being at distance i from both x and y) the following hold: the number of neighbours of z, which are at distance i-1 from both x and y is equal to: a(i) + ß(i) (the number of common neighbours of x and y, which are at distance i-1 from z). For a more detailed description of the project see the attached pdf file "project_eng.pdf"._ 3.Poročilo o realizaciji predloženega programa dela na raziskovalnem projektu2 Glavna cilja našega raziskovanja sta dva. Prvi cilj je razumeti in klasificirati dvodelne razdaljno-regularne grafe, ki imajo tako imenovano Q-polinomsko lastnost. Za dosego tega cilja študiramo tako imenovano Terwilligerjevo algebro grafa G. Terwilligerjevo algebro T največkrat študiramo preko njenih nerazcepnih modulov. Poleg študija nerazcepnih modulov Terwilligerjeve algebre pa poskušamo rešiti še vrsto drugih problemov, ki pa so z zgornjim problemom tesno povezani. Drugi cilj našega raziskovanja pa je namenjen raziskovanju delovanja grup na razdaljno-regularnih grafih. Predvsem se ukvarjamo s klasifikacijo Cayleyevih razdaljno-regularnih grafov (za različne družine grup), ter razdaljno-regularnih bi- in tri-Cayleyevih grafov (ravno tako za različne družine grup). Delo na projektu na obeh dveh glavnih področjih raziskovanja, torej študiju Terwilligerjevih algeber dvodelnih razdaljno-regularnih grafov ter študiju delovanja grup na razdaljno-regularnih grafih, je potekalo skladno z zastavljenim načrtom. Seveda se pri matematičnem raziskovanju v samem procesu dokazovanja trditev in domnev odpirajo nova vprašanja, pokažejo se nove obetavne smeri razvoja, težišče raziskovanja se lahko zaradi novih dognanj hitro prevesi v drugo smer. Tudi zato je bilo delo na projektu raznoliko, včasih tudi izven strogih smernic projekta, začrtanih v prijavi. Raziskovalci projektne skupine so v letuih trajanja projekta (2011-2014) objavili 99 izvirnih znanstvenih člankov, od tega 95 v revijah, ki jih indeksira Science citation index. Šest člankov je bilo objavljenih v revijah, ki s uvrščajo v prvo četrtino na področju, 34 v revijah, ki se uvrščajo v drugo četrtino, 38 v revijah, ki se uvrščajo v tretjo četrtino, in 17 v revijah, ki se uvrščajo v četrto četrtino. Nekateri izmed teh člankov so neposredno povezani s tematiko projekta: • MIKLAVIČ, Štefko, TERWILLIGER, Paul. Bipartite Q-polynomial distance-regular graphs and uniform posets. Journal of algebraic combinatorics, ISSN 0925-9899, 2013, vol. 38, iss. 2, str. 225-242, doi: 10.1007/s10801-012-0401-1. [COBISS.SI-ID 10244667721 • MIKLAVIČ, Štefko. On bipartite distance-regular graphs with intersection numbers c_i = (q^i-1)/(q-1). Graphs and combinatorics, ISSN 0911-0119, 2013, vol. 29, iss. 1, str. 121130, doi: 10.1007/s00373-011-1094-2. [COBISS.SI-ID 10243702601 • MIKLAVIČ, Štefko, PENJIĆ, Safet. On bipartite Q-polynomial distance-regular graphs with c_2 le 2. The Electronic journal of combinatorics, ISSN 1077-8926, 2014, vol. 21, iss. 4, p4.53 (19 str.). [COBISS.SI-ID 15371209641 • MIKLAVIČ, Štefko, ŠPARL, Primož. On distance-regular Cayley graphs on abelian groups. Journal of combinatorial theory. Series B, ISSN 0095-8956, 2014, vol. 108, str. 102-122. http://dx.doi.org/10.1016/j.jctb.2014.03.002. [COBISS.SI-ID 15363826601 Večina ostalih člankov je vsaj posredno povezana z vsebino projekta preko delovanja grup na grafih, recimo • KO VACS, Istvan, MALNIČ, Aleksander, MARUŠIČ, Dragan, MIKLAVIČ, Štefko. Transitive group actions: (im)primitivity and semiregular subgroups. Journal of algebraic combinatorics, ISSN 0925-9899, 2014, vol. , is. , 19 str. doi: 10.1007/s10801-014-0556-z. [COBISS.SI-ID 15367720361 • KOVACS, Istvan. Arc-transitiv dihedrants of odd prime-power order. Graphs and combinatorics, ISSN 0911-0119, 2013, vol. 29, issue 3, str. 569-583, doi: 10.1007/s00373-012-1134-6. [COBISS.SI-ID 10244071241 ). • POTOČNIK, Primož, SPIGA, Pablo, VERRET, Gabriel. On the order of arc-stabilisers in arc-transitive graphs with prescribed local group. Transactions of the American Mathematical Society, ISSN 0002-9947, 2014, vol. 366, no. 7, str. 3729-3745, [COBISS.SI-ID 169818491 Raziskovalci projektne skupine v zadnjih 10 letih izkazujejo 1621 normiranih čistih citatov oz. 867 čistih citatov. Prav tako so raziskovalci projektne skupine preko predavanj na mednarodnih in domačih konferencah in seminarjih domačo in mednarodno javnost seznanjali z rezultati, ki so nastali v okviru projekta. Tu velja omeniti predavanje vodje projekta dr. Štefka Miklaviča na University of Wisconsin - Madison (MIKLAVIČ, Štefko. Q-polynomial distance-regular graphs with girth 6 : University of Wisconsin, Madison, Wisconsin, USA, 9. 12. 2013. 2013. http://www.math.wisc.edu/~terwilli/combsemsched.html. [COBISS.SI-ID 15361235881 ), predavanja Istvana Kovacsa na University of La Plata( KOVACS, Istvan. Arc-transitive dihedrants of two times an odd prime-power order : University of La Plata, La Plata, Argentina, 31. 10. 2013. 2013. [COBISS.SI-ID 15361358761 ) ter predavanje Martina Milaniča na Rutgers University (MILANIČ, Martin. On the identifiable subgraph problem : RUTCOR Colloquium, Rutgers University, New Brunswick, January 31, 2013. 2013. [COBISS.SI-ID 10244900681 ), ter vabljeni predavanji dr. Malniča: Algebraic, Topological and Complexity Aspects of Graph Covers - ATCAGC'11 January 23-27, 2011, Kral'ova Studna, Fatra Mountains, Slovakia, MALNIČ, Aleksander. Action graphs. Kral'ova Studna, 24. 1. 2011. [COBISS.SI-ID 158889851 in MALNIČ, Aleksander. On the split structure of lifted groups : Workshop on Symmetry in Graphs, Maps, and Polytopes, October 24-27, 2011, the Fields Institute, Toronto, Canada. 2011. http://www.fields.utoronto.ca/programs/scientific/11- 12/discretegeom/talks/october.html. [COBISS.SI-ID 10243738441. Omeniti še velja, da se University of Wisconsin Madison na "Academic Ranking of World Universities" za leto 2013 uvršča na visoko 19 mesto, na področju matematike pa celo na 11 mesto. Projektna skupina je tekom projekta gostila več podoktorandov in vrhunskih strokovnjakov iz tujine (A. A. Ivanov, G. Kiss, P. Terwilliger, T. Ito, J.H. Kwak, T. Szonyi, S. Evdokimov, P. Fowler, A. Medvedev, A. A. Pascasio, I. Ponomarenko, M. Anholcer, ...), nekaj med njimi tudi za daljše časovno obdobje. Članek, v katerem bo v celoti rešen Problem 1 (glej točko 2. Povzetek raziskovalnega projekta) je trenutno v fazi priprave. Avtorja sta vodja projekta dr. Miklavič in dr. M. MacLean iz Univerze v Seattlu. Pričakujemo, da bo članek poslan v objavo v naslednjih nekaj mesecih. 4.Ocena stopnje realizacije programa dela na raziskovalnem projektu in zastavljenih raziskovalnih ciljev3 Delo na projektu na obeh dveh glavnih področjih raziskovanja (torej študiju Terwilligerjevih algeber dvodelnih razdaljno-regularnih grafov ter študiju delovanja grup na razdaljno-regularnih grafih) je potekalo v skladu z načrtom. Kot že rečeno, se pri matematičnem raziskovanju v samem procesu dokazovanja trditev in domnev odpirajo nova vprašanja, pokažejo se nove obetavne smeri razvoja, težišče raziskovanja se zaradi novih dognanj hitro prevesi v drugo smer. Tudi zato je delo na projektu raznoliko, včasih tudi izven strogih smernic projekta, začrtanih v prijavi. Ocenjujemo, da so bili raziskovalni cilji v realizirani. V celoti je rešen Problem 1 (glej Povzetek raziskovalnega projekta), članek bo poslan v objavo naslednjih nekaj mesecih. Ob tem velja poudariti, da so rezultati, ki nastajajo tekom projekta ter so z vsebino projekta le posredno povezani, celo presegli pričakovanja vodje projektne skupine. Skupno so namreč raziskovalci projektne skupine v času trajanja projekta objavili kar 99 izvirnih znanstvenih člankov, od tega 95 v revijah, ki jih indeksira Science Citation Index. Prav tako je bila v celoti realizirana udeležba raziskovalcev na mednarodnih konferencah in seminarjih, preko katerih so raziskovalci zainteresirano javnost seznanjali z rezultati projekta. Raziskovalci so rezultate predstavili na 14. predavanjih na mednarodnih konferencah ter na šestih predavanjih na seminarjih na tujih univerzah. Omeniti tudi velja, da so raziskovalci projektne skupine sodelovali pri organizaciji številnih uspešnih mednarodnih dogodkov (http://www.famnit.upr.si/sl/konference/): • LL2012: Ljubljana-Leoben Seminar 2012, Bovec, Slovenija, 20 - 22 September 2012; • CSD6: Computers in Scientific Discovery 6 / Računalniki v znanstvenem odkrivanju 6, Portorož, Slovenija, 21 - 25 August 2012; • PhD Summer School in Discrete Mathematics / Poletna šola iz diskretne matematike za doktorske študente, Rogla, Slovenija, 2011, 2012, 2013, 2014; • CSASC 2013 - Joint Mathematical Conference, Koper, 9. - 13. junij 2013; • Joint Workshop of Mathematics Departments UP IAM and UP FAMNIT, Rogla, 17. - 19. maj, 2013; • International Conference on Graph Theory and Combinatorics. Dedicated to Prof. Dragan Marušič's 60th Birthday. UP FAMNIT, Koper, 1. - 3. maj, 2013; • ATCAGC 2013: Algebraic, Topological and Complexity Aspects of Graph Covers Bovec, 28. januar - 1. februar, 2013. • International Conference on Graph Theory and Combinatorics Rogla, Slovenija,16 - 18 Maj, 2014. Preko teh dogodkov se širi prepoznavnost in odličnost matematičnih raziskovalnih krogov na Univerzi na Primorskem. Člani raziskovalne skupine poleg tega aktivno sodelujejo pri organizaciji in vodenju raziskovalnega matematičnega seminarja na UP FAMNIT (http://www.famnit.upr.si/sl/raziskovanje/matseminar) ter ciklusa poljudnih predavanj "Izleti v matematično vesolje" (http://izleti.famnit.upr.si/sl/). 5.Utemeljitev morebitnih sprememb programa raziskovalnega projekta oziroma sprememb, povečanja ali zmanjšanja sestave projektne skupine4 V letu 2012 smo zaradi narave dela raziskovalno skupino razširili z raziskovalcem Viljemom Tisnikarjem. V letu 2012 je Viljem Tisnikar na projektu delal v obseg 510 ur. Drugih sprememb programa projekta oziroma projektne skupine ni bilo. 6.Najpomembnejši znanstveni rezultati projektne skupine5 Znanstveni dosežek 1. COBISS ID 1536382660 Vir: COBISS.SI Naslov SLO Razdaljno-regularni grafi abelskih grup ANG On distance-regular Cayley graphs on abelian groups Opis SLO Naj bo $G$ končna abelova grupa z identiteto 1 in naj bo $S$ sebi inverzna podmnožica v $G \setminus \{1\}$, ki generira $G$ in za katero obstaja tak $s \in S$, da je $\langle S \setminus \{s,s^-1}\} \rangle \ne G$. V tem članku je opisna popolna klasifikacija razdaljno-regularnih Cayleyevih grafov $\text{Cay}(G;S)$ za takšne pare $G$ in $S$. ANG Let $G$ denote a finite abelian group with identity 1 and let $S$ denote an inverse-closed subset of $G \setminus \{1\}$, which generates $G$ and for which there exists $s \in S$, such that $\langle S \setminus \{s,s^-1}\} \rangle \ne G$. In this paper we obtain the complete classification of distance-regular Cayley graphs $\text{Cay}(G;S)$ for such pairs of $G$ and $S$. Objavljeno v Academic Press; Journal of combinatorial theory. Series B; 2014; Vol. 108; str. 102-122; Impact Factor: 0.939;Srednja vrednost revije / Medium Category Impact Factor: 0.674; A': 1; WoS: PQ; Avtorji / Authors: Miklavič Štefko, Šparl Primož Tipologija 1.01 Izvirni znanstveni članek 2. COBISS ID 1024466772 Vir: COBISS.SI Naslov SLO Dvodelni Q-polinomski razdaljno-regularni grafi in uniformne delno urejene množice ANG Bipartite Q-polynomial distance-regular graphs and uniform posets Opis SLO Naj bo Г dvodelen razdaljno-regularen graf z množico vozlišč $X$ in premerom D \ge 3$. Izberimo si $x \in X$ in naj bosta $L$ in $R$ pripadajoči "lowering" in "raising" matriki. V članku pokažemo, da vsaka Q-polinomska struktura grafa Г porodi linearno odvisnost matrik $RL^$, $LRL$, $L^R$, $L$. Definirajmo delno urejenost $\le$ na $X$ takole: za $y,z \in X$ naj bo $y \le z$ natanko takrat, ko je $\partial(x,y)+\partial (y,z)=\partial(x,z)$, kjer $\partial$ označuje običajno razdaljo v grafu Г. V članku določimo, kdaj zgoranja linearna odvisnost porodi uniformno ali strogo uniformno strukturo na delno urejeni množici $X$. Pokažemo, da je - razen v enem primeru - vedno porojena uniformna struktura, razen v treh primerih pa celo strogo uniformna struktura. ANG Let Г denote a bipartite distance-regular graph with vertex set $X$ and diameter $D \ge 3$. Fix $x \in X$ and let $L$ (resp. $R$) denote the corresponding lowering (resp. raising) matrix. We show that each $Q$-polynomial structure for Г yields a certain linear dependency among $RL^ $, $LRL$, $L^R$, $L$. Define a partial order $\le$ on $X$ as follows. For $y,z \in X$ let $y \le z$ whenever $\partial(x,y)+\partial(y,z)=\partial(x,z) $, where $\partial$ denotes path-length distance. We determine whether the above linear dependency gives this poset a uniform or strongly uniform structure. We show that except for one special case a uniform structure is attained, and except for three special cases a strongly uniform structure is attained. Objavljeno v Kluwer Academic; Journal of algebraic combinatorics; 2013; Vol. 38, iss. 2; str. 225-242; Impact Factor: 0.721;Srednja vrednost revije / Medium Category Impact Factor: 0.674; WoS: PQ; Avtorji / Authors: Miklavič Štefko, Terwilliger Paul Tipologija 1.01 Izvirni znanstveni članek 3. COBISS ID 1536772036 Vir: COBISS.SI Naslov SLO Tranzitivna delovanja grup: (ne)primitivnost in semiregularne podgrupe ANG Transitive group actions: (im)primitivity and semiregular subgroups Opis SLO V članku obravnavamo naslednji problem: če je H semiregularna abelska podgrupa trazitvne grupe $G$, ki deluje na množici $X$, potem poišči pogoje za (ne)eksistenco $G$-invariantnih particij množice $X$. Pogoji, dobljeni v tem članku, so dobljeni s študijem spektralnih lastnosti pripadajočega $G$-invariantnega digrafa. Nerazcepni kompleksni karakterji podgrupe G so ključno orodje za dosego rezultatov. Vprašanja te vrste se naravno pojavijo ko poskušamo klasificirati kombinatorične objekte, ki premorejo določeno stopnjo simetrije. Kot ilustracija dobljenih rezultatov je v članku podan nov in kratek dokaz starega rezultata Frucht-a, Graver-ja in Watkins-a, v katerem so klasificirani povezavno tranzitivni posplošeni petersenovi grafi. ANG The following problem is considered: if $H$ is a semiregular abelian subgroup of a transitive permutation group $G$ acting on a finite set $X$, find conditions for (non) existence of $G$-invariant partitions of $X$. Conditions presented in this paper are derived by studying spectral properties of associated $G$-invariant digraphs. As an essential tool, irreducible complex characters of $H$ are used. Questions of this kind arise naturally when classifying combinatorial objects which enjoy a certain degree of symmetry. As an illustration, a new and short proof of an old result of Frucht, Graver and Watkins classifying edge-transitive generalized Petersen graphs, is given. Objavljeno v Kluwer Academic; Journal of algebraic combinatorics; 2014; Vol. , is.; 19 str.; Impact Factor: 0.721;Srednja vrednost revije / Medium Category Impact Factor: 0.674; WoS: PQ; Avtorji / Authors: Kovacs Istvan, Malnič Aleksander, Marušič Dragan, Miklavič Štefko Tipologija 1.01 Izvirni znanstveni članek 4. COBISS ID 16981849 Vir: COBISS.SI Naslov SLO Red ločnega stabilizatorja v ločno tranzitivnem grafu s predpisano lokalno grupo ANG On the order of arc-stabilisers in arc-transitive graphs with prescribed local group Opis SLO Naj bo Г povezan $G$-ločno tranzitiven graf, $uv$ lok grafa Г in $L$ permutacijska grupa, ki jo inducira stabilizator $G_v$ na soseščini $r(v)$. V članku raziskujemo zgornjo mejo za red stabilizatorja $G_{uv}$ v odvisnosti od grupe $L$ in reda grafa Г. ANG Let Г be a connected $G$-arc-transitive graph, let $uv$ be an arc of Г and let $L$ be the permutation group induced by the action of the vertex-stabiliser $G_v$ on the neighbourhood $r(v)$. We study the problem of bounding $|G_{uv}|$ in terms of $L$ and the order of Г. Objavljeno v American Mathematical Society.; Transactions of the American Mathematical Society; 2014; Vol. 366, no. 7; str. 3729-3745; Impact Factor: 1.095;Srednja vrednost revije / Medium Category Impact Factor: 0.674; A': 1; WoS: PQ; Avtorji / Authors: Potočnik Primož, Spiga Pablo, Verret Gabriel Tipologija 1.01 Izvirni znanstveni članek 5. COBISS ID 1024473940 Vir: COBISS.SI Naslov SLO G-ločno-tranzitivni dihedranti in regularni dihedrantski zemljevidi ANG On G-arc-regular dihedrants and regular dihedral maps Opis SLO Graf Г je G-ločno tranzitiven, če podgrupa G 3. Naj bo MatX (C) C-algebra matrik z elementi v C, z vrsticami in stolpci indeksiranimi z X. Naj bo A G MatX(C) matrika sosednosti grafa Г. Bose-Mesnerjeva algebra M grafa Г je podalgebra v MatX(C), ki je generirana z A. Znano je, da ima algebra M bazo, ki jo sestavlja D + 1 medsebojno pravokotnih primitivnih idempotentov Ei (0 < i < D). Algebra M je zaprta tudi za Schurovo množenje matrik, ki ga oznacimo s o. Torej za 0 < i, j < D obstajajo taksni skalarji qj G C (0 < h < D), da velja Ei o Ej = ^h=o qjEh. Graf Г je Q-polinomski (glede na dan vrstni red E0, Ei,..., ED primitivnih idempotentov), ce za 0 < h, i, j < D velja naslednje: qh = 0 (oz. qh = 0) vedno, ko je eden izmed h, i, j vecji (oz. enak) kot vsota preostalih dveh. Glavni cilj nasega raziskovanja je razumeti in klasificirati dvodelne Q-polinomske razdaljno-regularne grafe. Za dosego tega cilja uporabljamo naslednjo algebro. Izberimo si x G X. Za 0 < i < D naj bo E* = E*(x) diagonalna matrika v MatX (C) z (y, y)-koordinato enako 1 ce je d(x,y) = i, in 0 sicer (y G X). Terwilligerjeva algebra grafa Г glede na vozlišče x je podalgebra v Matx(C), ki je generirana z A, E*,E*,..., ED. Terwilligerjevo algebro oznacimo s T = T(x). Algebro T(x) najveckrat studiramo preko njenih modulov. Naj bo CX vektorski prostor nad C, ki ga sestavljajo stolpcni vektorji z elementi v C, in ki imajo vrstice indeksirane z X. Za z G X naj bo ž G CX vektor, ki ima z-to koordinato enako 1, ostale koordinate pa enake 0. T-modul je vektorski podprostor W v CX, za katerega velja BW C W za vsak B G T. Naj bosta W in W' T-modula. Izomorfizem iz W v W' je izomorfizem vektorskih prostorov a : W ^ W', za katerega velja (aB — Ba)W = 0 za vsak B G T. T-modul W je nerazcepen, ce je nenicelen in ne vsebuje nobenih T-modulov razen nicelnega T-modula in samega sebe. Naj bo W nerazcepen T-modul. Krajišče r modula W je r = min{i | 0 < i < D, E*W = 0}. T-modul W je tanek, ce je dimE*(W) < 1 za 0 < i < D. Od sedaj naprej privzemimo naslednjo notacijo. Notacija 1 Naj bo Г = (X, R) dvodelen razdaljno-regularen graf s premerom D > 3 in z matriko sosednosti A. Naj bo M Bose-Mesnerjeva algebra grafa Г. Izberimo si x G X in naj bo T = T(x) Terwilligerjeva algebra grafa Г glede na x. Za y G ^(x) in cela stevila 0 < i, j < D definirajmo vektorje wij = wij(y) na naslednji način: wij = ^2,2ег-(ж)пг-(y) ž. Naj bo q > 2 naravno stevilo. V tem projektu bo nas glavni cilj resiti naslednji problem. Problem 1 Klasificiraj tiste grafe Г; ki imajo do izomorfizma natančno največ dva nerazcepna T-modula s krajiscem 2, od katerih sta oba tanka. Nastejmo nekaj problemov, ki so tesno povezani s problemom 1, in jih bomo poskusili resiti: Problem 2 Pokazi, da sta trditvi (i),(ii) ekvivalentni. (i) Graf Г ima do izomorfizma natančno največ dva nerazcepna T-modula s krajiscem 2, od katerih sta oba tanka. (ii) Za 2 < i < D — 2 obstajajo kompleksna stevila ai,ßi z naslednjo lastnostjo: za y,z G X z d(x,y) = 2, d(x,z) = i, d(y,z) = i, je |ri_i(x) П ri_i(y) П r(z)| = ai + ßi|r(x) П r(y) П ri_i(z)|. Problem 3 Pokazi, da sta trditvi (i),(ii) ekvivalentni. (i) Za 2 < i < D — 1 obstajajo kompleksna stevila ai,ßi z naslednjo lastnostjo: za y,z G X z d(x,y) = 2, d(x,z) = i, d(y,z) = i, je |ri_i(x) П ri_i(y) П r(z)| = ai + ßi|r(x) П r(y) П ri_i(z)|. (ii) Graf Г je Q-polinomski. Problem 4 Stevila a^ ßi iz problemov 2 in 3 izrazi s presečnimi stevili grafa Г. Problem 5 Privzemimo, da ima Г presečna stevila p\ i_i = (qi — 1)/(q — 1) (1 < i < D). Poisči atraktivno ortogonalno bazo za MW = {mw | m G M, w G span{wij | 0 < i, j < D}}. Problem 6 Naj bo Г is Q-polinomski. Za vozlisča z,w G X definirajmo z < w natanko takrat ko je d(x, z) + d(z,w) = d(x,w). Pokazi, da je delno urejena mnozica (X, <) uniformna. Problem 7 Naj bo Г Q-polinomski. Pokazi, da Г ne obstaja če je D > 4 in C2 = 1. Priloga 3 BIPARTITE DISTANCE-REGULAR GRAPHS Project proposal Our research concerns a combinatorial object known as a graph. A graph is a finite set of vertices, together with a set of undirected arcs or edges, each of which connects a pair of distinct vertices. Let Г denote a graph with vertex set X, shortest-path distance function д, and diameter D. For x G X and an integer i let Гј(х) := {y G X | d(x,y) = i}. We say Г is distance-regular whenever for all integers h,i,j (0 < h,i,j < D), and all x,y G X with d(x,y) = h, the number ph := |ГДх) П Гј (y)| is independent of x, y. The constants ph (0 < h, i, j < D) are known as the intersection numbers of Г. From now on we assume Г is distance-regular with diameter D > 3. Let Matx (C) denote the C-algebra of matrices with entries in C and with rows and columns indexed by X. Let A G Matx(C) denote the adjacency matrix of Г. Let M denote the subalgebra of Matx(C) generated by A. It is known that M has a basis consisting of D + 1 mutually orthogonal primitive idempotents Ei (0 < i < D). The algebra M is closed under entry-wise multiplication o. Thus for 0 < i,j < D there exist qh G C (0 < h < D) such that Ei o Ej = J2h=o qhjEh. The scalars qh are real numbers. The graph Г is said to be Q-polynomial (with respect to the given ordering E0, Ei,..., ED) whenever for 0 < h,i,j < D the following holds: qh is zero (resp. nonzero) whenever one of h, i,j is greater than (resp. equal to) the sum of the other two. The general goal of our research is to understand and classify the bipartite Q-polynomial distance-regular graphs. To reach this goal we will use a certain algebra defined as follows. Fix x G X. For 0 < i < D let E* = E*(x) denote the diagonal matrix in Matx (C) with (y,y)-entry equal to 1 if d(x,y) = i, and 0 otherwise (y G X). Let T = T(x) denote the subalgebra of Matx(C) generated by matrices A,E*,E*,..., ED. We refer to T as the Terwilliger algebra of Г with respect to x. In many instances the algebra T can best be studied via its modules. In order to define them we let Cx denote the vector space over C consisting of column vectors with entries in C and rows indexed by X. For z G X, let z denote the vector in Cx with a 1 in the z-coordinate, and 0 in all other coordinates. By a T-module we mean a subspace W of Cx such that BW C W for all B G T. Let W and W' denote T-modules. By a isomorphism from W to Wwe mean a vector space isomorphism a : W ^ W' such that (aB-Ba)W = 0 for all B G T .A T-module W is irreducible whenever it is nonzero and contains no T-modules other than zero and W. Let W denote an irreducible T-module. We define the endpoint r of W by r = min{i | 0 < i < D, E*W = 0}. A T-module W is thin whenever dimE*(W) < 1 for 0 < i < D. From now on we adopt the following notation. Notation 1 Let Г = (X, R) denote a bipartite distance-regular graph with diameter D > 3 and with adjacency matrix A. Let M denote the Bose-Mesner algebra of Г. Fix x G X and let T = T(x) denote the Terwilliger algebra of Г with respect to x. For y G ^(x) and integers 0 < i,j < D define vectors wij = wij(y) by wij = ^2, where the sum is over all z G ri(x) П Гј (y). Let q > 2 be an integer. In this project our central goal is to solve the following problem. Problem 1 With reference to Notation 1, classify those Г for which up to isomorphism there exist at most two irreducible T-modules with endpoint 2, and they are both thin. Below are some problems which are related to Problem 1, and which we will try to solve for the project. Problem 2 With reference to Notation 1, show that the following (i),(ii) are equivalent. (i) Up to isomorphism Г has at most two irreducbile T-modules with endpoint 2, and they are both thin; (ii) For 2 < i < D — 2 there exist complex scalars ai,ßi with the following property: for all y,z G X such that d(x,y) = 2, d(x,z) = i, d(y,z) = i we have |ri_i(x) П ri_i(y) П r(z)| = a4 + ßi|r(x) П r(y) П ri_i(z)|. Problem 3 With reference to Notation 1, show that the following (i),(ii) are equivalent. (i) For 2 < i < D — 1 there exist complex scalars ai,ßi with the following property: for all y,z G X such that d(x,y) = 2, d(x,z) = i, d(y,z) = i we have |r_i(x) П r_i(y) П r(z)| = a4 + ßi|r(x) П r(y) П ri_i(z)|; (ii) Г is Q-polynomial. Problem 4 With reference to Problems 2,3, determine ai,ßi in terms of the intersection numbers of Г. Problem 5 With reference to Notation 1, assume that Г has intersection numbers р1ц_i = (qi — 1)/(q — 1) (1 < i < D). Find an attractive basis for MW = {mw | m G M,w G span{wij | 0 < i, j < D}}. Problem 6 With reference to Notation 1, assume that Г is Q-polynomial. For all vertices z,w G X define z < w if and only if д(x, z) + d(z, w) = д(x, w). Show that partially ordered set (X, <) is uniform. Problem 7 With reference to Notation 1, assume that Г is Q-polynomial. Show that Г does not exist if D > 4 and C2 = 1.