It turns out that any such map is necessarily bijective if n≥3. The results represents a generalization of the fundamental theorem of geometry of symmetric matrices (over a finite field). In the language of graph theory, the result says that the graph Gn with vertex set V (Gn) = Sn(Fq) and with edge set

E(Gn) = {{A;B}: rk(A - B) = 1} is a core, i.e., any its endomorphism is an automorphism, if n ≥ 3. This is not true if n = 2. In fact, it turns out that the chromatic number of G₂ equals q and there exists a proper

endomorphism onto a clique of order q.

22.11.2010. ob 10:00 Seminarska soba v Galebu

Predavatelj: dr. Ferdinando Cicalese, sa Univerze v Salernu (Università degli Studi di Salerno).

Naslov: Superselectors: Efficient Constructions and Applications

Povzetek: Superimposed codes represent the main tool for the efficient solution of several problems arising in compressed sensing, cryptography and data security, computational biology, multi-access communication, database theory, pattern matching, distributed colouring, and circuit complexity, among the others.

It has also become apparent that combinatorial structures strictly related to superimposed codes lie at the heart of an even vaster series of problems. E.g., selectors were instrumental to obtain fast broadcasting algorithms in radio networks, (p,k,n)-selectors were the basic tool for the first two-stage group testing algorithm with an information theoretic optimal number of tests, (d,\ell)- disjunct matrices were a crucial building block for the efficiently decodable non-adaptive group testing procedures.

We shall focus on a new combinatorial structure, superselectors, which encompasses and unifies all of the combinatorial structures mentioned above (and more). When appropriately instantiated, superselectors asymptotically match the best known constructions of (p,k,n)-selectors, (d, l)-list-disjunct matrices, monotone encodings and (k, alpha)-FUT families, MUT_k(r)-families for multi-access channel.

We shall show some implementations of superselectors which provide optimal approximate group testing schemes and quasi-optimal additive group testing schemes.

8.11.2010. ob 10:00 Seminarska soba v Galebu

Predavatelj: dr.Istvan Kovacs

Naslov: Covering systems of finite abelian groups

Povzetek: A covering system of a finite group G is a set S of ordered pairs of its subgroups,

S = { (M₁,L₁), ..., (M_n,L_n) }, which satisfies the following axioms:
1. M_ii for all i.
2. (L₁\M₁) U … U (L_n\M_n) = G\{1}.
3. |L₁ : M₁| ∙…∙ |L_n: M_n| = |G|.
The covering system S is said to be regular if some L_i=G.
In the talk we study the regularity of covering systems of finite abelian groups.

18.10.2010. ob 10:00 Seminarska soba v Galebu

Predavatelj: dr.Martin Milanič.

Naslov: Graphs of separability at most two: structural characterizations and their consequences

Povzetek: We introduce graphs of separability at most k as graphs in which every two non-adjacent vertices can be separated by a set of at most k other vertices. Graphs of separability at most k arise in connection with the parsimony haplotyping problem from computational biology. For k = 0 or k = 1, the only connected graphs of separability at most k are complete graphs and block graphs, respectively. For values of k greater than 2, graphs of separability at most k form a rich class of graphs containing all graphs of maximum degree k.

We prove several characterizations of graphs of separability at most 2, which generalize complete graphs, cycles and trees. The main result is that every connected graph of separability at most 2 can be constructed from complete graphs and cycles by pasting along vertices or edges, and vice-versa, every graph constructed this way is of separability at most 2. The structure theorem has nice algorithmic implications – some of which cannot be extended to graphs of higher separability – however certain optimization problems remain intractable on graphs of separability 2. Finally, we characterize graphs of separability at most 2 in terms of minimal forbidden induced subgraphs and minimal forbidden induced minors.

You can download slides from the lecture here. DOWNLOAD

11.10.2010. ob 10:00 Seminarska soba v Galebu
Predavatelj: Alexandru Tomescu (University of Udine, Italy)
Naslov: Mapping Hypersets into Numbers

Povzetek: We introduce and prove the basic properties of an encoding that generalizes to non-well-founded hereditarily finite sets the bijection defined by Ackermann between hereditarily finite sets and natural numbers. The new encoding maps its domain onto dyadic rational numbers.

You can download slides from the lecture here: DOWNLOAD

4.10.2010. ob 10:00 Seminarska soba v Galebu
Predavatelj: dr. Barbara Boldin
Naslov: Biološke invazije v strukturiranih populacijah

Povzetek :Kdaj je invazija nove populacije uspešna? Če dinamiko populacij opišemo kot determinističen proces in privzamemo, da so obstoječe populacije v ravnovesnem stanju, potem na to vprašanje lahko odgovorimo takole: če je osnovno reprodukcijsko razmerje nove populacije R₀večje kot 1, je invazija uspešna, medtem ko je invazija obsojena na neuspeh kadar je R₀0 = 1 pride do transkritične bifurkacije.

Z matematičnega vidika obstaja samo en tip transkritične bifurkacije. Kadar pa dinamični sistem opisuje nek biološki proces, moramo razlikovati dva primera: superkritično bifurkacijo, pri kateri netrivialna veja ravnovesnih stanj obstaja za R₀> 1 in podkritično bifurkacijo, kjer netrivialne ravnovesne točke najdemo le ko je R₀

Na predavanju bomo predstavili način izračuna osnovnega repodukcijskega razmerja za strukturirane populacije, izpeljali formulo za določanje smeri bifurkacije in opisali posledice tipa transkritične bifurkacije za biološki proces. Rezultati so uporabni za študij različnih invazij, tako v ekologiji, epidemiologiji kot tudi evoluciji, kar bomo prikazali na primerih.

Predavanje bo povzeto po članku:
“B. Boldin: Introducing a population into a steady community: the critical case, the centre manifold and the direction of bifurcation. SIAM Journal on Applied Mathematics, Volume 66 (2006), Issue 4, pp. 1424-1453”

Tukaj lahko prevzamete prosojnice s predavanja:DOWNLOAD

	+386 (5) 611 75 70 (administration office)
	+386 (5) 611 75 75 (student services)
	+386 (5) 611 75 71