Erdös-Ko-Rado izrek je eden osrednjih rezultatov ekstremalne kombinatorike. Podaja mejo za velikost družine presečnih k-podmnožic množice inklasificira družine, ki to mejo dosežejo. Ta izrek je bil posplošen na številne načine, na primer na presečne podprostore vektorskega prostora nadkončnim poljem in na presečne bloke v načrtu. Fokus predlaganega projekta je razširitev Erdos-Ko-Rado izreka na tranzitivne permutacijske grupe intočkovno tranzitivne grafe.

Za dano permutacijsko grupo, je podmnožica I množice G presečna, če za poljubni dve permutaciji g in h iz množice I obstaja tak element v izmnožice V, da je g(v)=h(v). Pravimo, da ima permutacijska grupa G Erdos-Ko-Rado lastnost (na kratko EKR-lastnost), če je velikost maksimalnepresečne množice enaka redu največjega točkovnega stabilizatorja. Presečna gostota r(G) je mera, ki nam pove, kako daleč je tranzitivnapermutacijska grupa G od tega, da bi imela EKR-lastnost, in je definirana kot kvocient r(G)=|I|/G_v, kjer je I presečna množica v grupi G maksimalnevelikosti, G_v pa točkovni stabilizator v grupi G.

Raziskovalni projekt ima tri glavne cilje:

- pričeti program, s katerim bomo pridobili globlje razumevanje tranzitivnih permutacijskih grup, ki nimajo EKR-lastnosti, s posebnim poudarkom nagrupah, katerih točkovni stabilizatorji imajo predpisano strukturo, kot na primer ciklične grupe;

- razviti računalniške programe za določevanje presečne gostote dane tranzitivne permutacijske grupe,

- oblikovati inovativne pristope za reševanje že dolgo odprtih problemov o točkovno tranzitivnih grafih – kot je na primer dobro poznan problemhamiltonskosti – in sicer s prepletom koncepta nizov presečnih gostot z drugimi že poznanimi informacijami o strukturi teh grafov (dolžinekonsistentnih ciklov, obstoj lihih avtomorfizmov, ipd).

The Erdös-Ko-Rado theorem is one of the central results in extremal combinatorics. It gives a bound on the size of a family of intersecting k-subsetsof a set and classifies the families satisfying the bound. This theorem has been extended in various directions, for example, to intersectingsubspaces of a vector space over a finite field and to intersecting blocks in a design. The focus of this project proposal is an extension of the Erdos-Ko-Rado theorem to transitive permutation groups and vertex-transitive graphs.

Given a permutation group , a subset I of G is called intersecting if, for any two permutations g and h in I, there exists v in V such that g(v)=h(v). Apermutation group G is said to have the Erdos-Ko-Rado property (in short EKR-property), if the size of a maximum intersecting set is equal to theorder of the largest point stabilizer. The measure of how far a transitive permutation group G is from having the EKR-property is the so-calledintersection density r(G) defined as the quotient r(G)=|I|/G_v, where I is an intersecting set in G of a maximum size, and G_v is a point stabilizer of G.

This research project has three main goals:

- to initiate a program aimed at obtaining a deeper understanding of transitive permutation groups, not having the EKR-property, with a specialemphasis given to groups whose point stabilizers have a prescribed structure, such as for example cyclic groups;

- to develop computer programs for determining intersection density of a given transitive permutation group;

- designing innovative approaches to certain long standing open problems about vertex-transitive graphs – such as for example the well-knownhamiltonicity problem – by combining the concept of intersection density of transitive groups of automorphisms with already existing information onthe structure of these graphs (lenghts of consistent cycles, existence of odd automorphisms, etc).