Krepko regularni grafi so kot stična točka kombinatorike, geometrije in algebre predmet številnih raziskav že več desetletij. S stališča algebraičnekombinatorike jih lahko smatramo kot kombinatorično aproksimacijo ranga 3 grafov, to je, orbitalnih grafov tranzitivnih permutacijskih grup ranga 3(t.j. grup, katerih točkovni stabilizator ima poleg fiksne točke dve dodatni orbiti). Medtem ko so slednji seveda popolnoma klasificirani kot posledica Klasifikacije končnih enostavnih grup (CFSG), je klasifikacija celotnega razreda krepko regularnih grafov trenutno še izven našega dosega.

Pri obravnavi posebnih razredov krepko regularnih grafov lahko uberemo različne smeri. Eden od pristopov je koncept t-točkovnega pogoja, kjer sezahteva, da so števila določenih podgrafov, ki vsebujejo dani par točk, invariantna grafa. Druga pomembna lastnost krepko regularnih grafih jekoncept k-izoregularnosti, kjer se zahteva, da imata poljubni dve podmnožici kardinalnosti največ k, ki inducirata izomorfna podgrafa, enako številososedov. Oba koncepta pa se srečata pri (m,n)-regularnosti. Grafi, ki zadoščajo t-točkovnemu pogoju soupadajo z (2,t)-regularnimi grafi in k-izoregularni grafi soupadajo s (k,k+1)-regularnimi grafi.

Dodatna motivacija za predlagani projekt izhaja iz povezave krepko regularnih grafov s tranzitivnimi permutacijskimi grupami ranga 3, ki sozahvaljujoč CFSG znane, kot je omenjeno zgoraj. Toda mnogi, ki se ukvarjajo s permutacijskimi grupami (in posledično algebrajično teorijo grafov),so mnenja, da je treba CFSG uporabljati nekoliko bolj previdno in konzervativno in da je treba, kadar koli je to mogoče, poiskati neposreden dokaz, kine vsebuje CFSG.

V ta namen bosta skupaj z različnimi drugimi teoretičnimi in kombinatoričnimi orodji v predlaganem projektu bistveno vlogo igrala zgoraj omenjenakoncepta - t-točkovni pogoj in k-izoregularnost - in sicer z namenom, da se doseže naslednje tri glavne cilje: (1) Pridobiti strukturne rezultate okrepko regularnih grafih (in bolj splošno, o asociativnih shemah), zlasti o tistih, ki so (2,4)-regularni oziroma (3,4)-regularni. (2) Dokazati (brezuporabe CFSG), da za sodo število n>8 ne obstaja netrivialni 3-izoregularni (krepko regularen) n-bicirkulant. (3) Dokazati (brez uporabe CFSG), da zaliho število n netrivialen krepko regularen n-bicirkulant X ne izpolnjuje 4-točkovnega pogoja, razen, če je n=5 in je X Petersenov graf ali njegovkomplement.

EN

As a meeting point of combinatorics, geometry and algebra, strongly regular graphs have been in the interest of mathematical community for quite along time, with first papers dating several decades ago. From the algebraic combinatorics viewpoint they can be seen as a combinatorialaproximation of rank 3 graphs, that is, orbital graphs of transitive permutation groups of rank 3 - groups with point stabilizers having two additionalorbits beside the fixed point. Of course, while the latter have been completely classified as a consequence of the Classification of Finite SimpleGroups (CFSG, hereafter), a classification of the whole class of strongly regular graphs is presently beyond our reach.

Different directions can be taken when looking for restricted classes of strongly regular graphs. One approach is the concept of t-vertex conditionwhere the numbers of certain subgraphs containing a given pair of vertices are required to be invariant of the graph. Another important restrictionimposed on strongly regular graphs is via the concept of k-isoregularity, where it is required that any two subsets of cardinality at most k andinducing isomorphic subgraphs have the same number of neighbors. Both of these directions meet through the concept of (m,n)-regularity, where inparticular graphs satisfying the t-vertex condition coincide with (2,t)-regular graphs and k-isoregular graphs coincide with (k,k+1)-regular graphs.

An additional important motivation for this project stems from the connection of strongly regular graphs to transitive permutation groups of rank 3,which are all known thanks to CFSG, as mentioned above. But many working in permutation groups (and by extension in algebraic graph theory) areof the opinion that CFSG should be used somewhat more cautiously and conservatively and that whenever possible, one should look for a directproof, one that is CFSG-free.

To this end, together with various other group-theoretic and combinatorial tools, the two concepts mentioned above - t-vertex condition and k-isoregularity - will play an essential role. The following are three main goals of this project: (1) To obtain structural results about strongly regulargraphs (and more generally about association schemes), in particular about their respective subclasses of (2,4)-regular and (3,4)-regular graphs. (2)To prove (without the use of CFSG) that for n>8 even no non-trivial 3-isoregular (strongly regular) n-bicirculant exists. (3) To prove (without the useof CFSG) that for n odd a non-trivial strongly regular n-bicirculant X does not satisfy the 4-vertex condition unless n=5 and X is either the Petersengraph or its complement.