# Raziskovalni matematični seminar - Arhiv

2019 | 2018 | 2017 | 2016 | 2015 | 2014 | 2013 | 2012 | 2011 | 2010 |

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |

**Datum in ura**/ Date and time: 20.12.12

**Predavalnica**/ Location: Famnit-Semin (Seminar room)

**Predavatelj**/ Lecturer: Prof. Andreas Brandstädt (University of Rostock, Germany)

**Naslov**/ Title: On the complexity of some packing and covering problems in certain graph classes

**Vsebina**/ Abstract:

Packing and covering problems in graphs and hypergraphs and their relationships belong to the most fundamental topics in combinatorics and graph algorithms and have a wide spectrum of applications in computer science, operations research and many other fields. Vertex Cover is a typical example of a covering problem, and Maximum Independent Set is a typical example of a packing problem, and the complexity of these two problems was investigated in thousands of papers.

Recently, there has been an increasing interest in problems combining packing and covering properties. For a hypergraph H = (V, E), Exact Cover is a classical problem asking for the existence of a subcollection E′ ⊆ E such that every vertex of V is contained in exactly one hyperedge from E′. It is well known that this problem is NP- complete even when the hyperedges contain only three vertices called Exact Cover by 3-Sets.

Among the problems combining packing and covering properties, there are the follo- wing variants of domination problems: Let G = (V, E) be a finite undirected and simple graph, and let N(G) denote the closed neighborhood hypergraph of G. A vertex set U ⊆ V is an efficient dominating set in G if the closed neighborhoods of vertices in U form an exact cover in N (G). An edge set M ⊆ E is an efficient edge dominating set in G if M is an efficient dominating set in the line graph L(G). Note that not every graph has an efficient dominating set (an efficient edge dominating set, respectively). The problem Efficient Domination (Efficient Edge Domination, respective- ly) asks for the existence of such a vertex set (edge set, respectively). It is well known that both problems are NP-complete, even for bipartite graphs. We give some new ca- ses where the problems are efficiently solvable by using structural properties of graph classes and using closure properties under the square operation, and we also generalize the problems to hypergraphs.

### **Slides from the talk are available here: DOWNLOAD!**

**Datum in ura**/ Date and time: 11.12.12

**Predavalnica**/ Location: FAMNIT-SEMIN

**Predavatelj**/ Lecturer: prof. Pablo Spiga (University of Milano-Bicocca)

**Naslov**/ Title: Is the theory of finite primitive groups finished?

**Vsebina**/ Abstract:

From time to time you hear people saying that the theory of finite primitive groups is dead (after theO'Nan-Scott theorem and the Classification of the Finite Simple Groups). In this talk, we present a result on cycle lengths that could have been discovered by Schur, or Wielandt or Manning. However, they didn't because such powerful results are not the end of the theory, but the beginning.

**Datum in ura**/ Date and time: 3.12.12

**Predavalnica**/ Location: FAMNIT-MP

**Predavatelj**/ Lecturer: Dragan Marušič

**Naslov**/ Title: Primitive groups of degree twice a prime number (part II)

**Vsebina**/ Abstract:

We will give a short overview and discuss possible future directions with regards to the classification of strongly regular bicirculants, in relation to the problem of obtaining a CFSG-free proof of nonexistence of simply primitive groups of degree $2p$.

**Datum in ura**/ Date and time: 26.11.12

**Predavalnica**/ Location: FAMNIT-MP

**Predavatelj**/ Lecturer: Dragan Marušič

**Naslov**/ Title: Primitive groups of degree twice a prime number

**Vsebina**/ Abstract:

We will give a short overview and discuss possible future directions with regards to the classification of strongly regular bicirculants, in relation to the problem of obtaining a CFSG-free proof of nonexistence of simply primitive groups of degree $2p$.

**Datum in ura**/ Date and time: 1.1.70

**Predavalnica**/ Location: Location: FAMNIT-MP

**Predavatelj**/ Lecturer: Lecturer: Dragan Marušič

**Naslov**/ Title: Title: Primitive groups of degree twice a prime number

**Vsebina**/ Abstract:

Abstract: We will give a short overview and discuss possible future directions with regards to the classification of strongly regular bicirculants, in relation to the problem of obtaining a CFSG-free proof of nonexistence of simply primitive groups of degree $2p$.

**Datum in ura**/ Date and time: 19.11.12

**Predavalnica**/ Location: Seminar room at Galeb (Kettejeva 1, Koper)

**Predavatelj**/ Lecturer: Prof. Endre Boros (RUTCOR, Rutgers University, USA)

**Naslov**/ Title: Quadratization of Pseudo-Boolean Functions

**Vsebina**/ Abstract:

Set functions, i.e., real mappings form the family of subsets of a finite set to the reals are known and widely used in discrete mathematics for almost a century, and in particular in the last 50 years. If we replace a finite set with its characteristic vector, then the same set function can be interpreted as a mapping from the set of binary vectors to the reals. Such mappings are called pseudo-Boolean functions and were introduced in the works of Peter L. Hammer in the 1960s (Hammer and Rudeanu, 1968). Pseudo-Boolean functions are different from set functions, only in the sense that their algebraic representation, a multilinear polynomial expression, is usually assumed to be available as an input representation.

The problem of minimizing a pseudo-Boolean function (over the set of binary vectors) appears to be the common form of numerous optimization problems, including the well-known MAX-SAT and MAX-CUT problems, and have applications in areas ranging from physics through chip design to computer vision, etc.

Some of these applications lead to the minimization of a quadratic pseudo-Boolean function, and hence such quadratic binary optimization problems received ample attention in the past decades. One of the most frequently used technique is based on roof-duality (Hamer, Hansen, Simeone, 1984), and aims at finding in polynomial time a simpler form of the given quadratic minimization problem, by fixing some of the variables at their provably optimum value (persistency) and decomposing the residual problem into variable disjoint smaller subproblems (Boros and Hammer, 1989). The method in fact was found very effective in computer vision problems, where frequently it can fix up to 80-90% of the variables at their provably optimum value (Boros, Hammer, Sun and Tavares, 2008). This algorithm was used by computer vision experts and a very efficient implementation, called QPBO, is freely downloadable (Rother, Kolmogorov, Lempitsky and Szummer, 2007).

In many applications of pseudo-Boolean optimization, in particular in vision problems, the objective function is a higher degree multilinear polynomial. For such problems there are substantially fewer effective techniques available. In particular, there is no analogue to the persistencies (fixing variables at their provably optimum value) provided by roof-duality for the quadratic case. On the other hand, more and more applications would demand efficient methods for the minimization of such higher degree pseudo-Boolean functions. This increased interest, in particular in the computer vision community, lead to a systematic study of methods to reduce a higher degree minimization problem to a quadratic one. We report on the most recent techniques and the computational success of those.

Joint research with Alex Fix (Cornell University), Aritanan Gruber (Rutgers University), Gabriel Tavares (FICO, Xpress-MP), and Ramin Zabih (Cornell University).

SLIDES FROM THE TALK ARE AVAILABLE HERE: **DOWNLOAD!**

**Datum in ura**/ Date and time: 12.11.12

**Predavalnica**/ Location: Seminar room at Galeb (Kettejeva 1, Koper)

**Predavatelj**/ Lecturer: dr. Bojan Kuzma

**Naslov**/ Title: On maps which do not increase the spectum of difference of matrices

**Vsebina**/ Abstract:

We will show that maps, which do not increase the spectra of complex matrices (in a sense that $Sp(Phi(A)-Phi(B)) subseteq Sp(A-B)$) are automatically linear and bijective. Although the problem is elementary, its proof relies on deep results from the theory of analitic functions.

**Datum in ura**/ Date and time: 22.10.12

**Predavalnica**/ Location: Seminar room at Galeb (Kettejeva 1, Koper).

**Predavatelj**/ Lecturer: Riste Škrekovski (FMF and IMFM, Ljubljana, Slovenia)

**Naslov**/ Title: Some results on network centralitiy indicies

**Vsebina**/ Abstract:

Centrality is used to quantify an intuitive feeling that in most networks some vertices are more central than others. In the talk we consider some graph theoretical results on closeness, betweenness centrality, and eccentricity.

**Datum in ura**/ Date and time: 5.11.12

**Predavalnica**/ Location: Seminar room at Galeb (Kettejeva 1, Koper)

**Predavatelj**/ Lecturer: dr. Dragan Stevanović

**Naslov**/ Title: Spectral approach to network partitioning problems

**Vsebina**/ Abstract:

An important part of the network analysis are network partitioning problems, which come in the forms of partitioning, finding maximum cut and detecting communities. There are well known, simple spectral heuristics for all three problems, which assign nodes to an appropriate part based on the sign of the eigenvector corresponding to an extremal eigenvalue of a particular network matrix. We will discuss a general framework in which these heuristics work and suggests a way for their further improvement.

**All welcome!**

**Datum in ura**/ Date and time: 29.10.12

**Predavalnica**/ Location: Seminar room at Galeb (Kettejeva 1, Koper)

**Predavatelj**/ Lecturer: dr. Gabriel Verret

**Naslov**/ Title: Growth of automorphism groups in arc-transitive graphs

**Vsebina**/ Abstract:

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 Gv on the neighbourhood Γ(v).

I will talk about the problem of bounding |Guv| in terms of L and the order of Γ.

**All welcome!**

On** Monday, October 22, 2012**, at the Faculty of Mathematics, Natural Sciences and Information Technologies in Koper, there will be a research mathematical seminar. **Seminar starts at 10:00**, and it will be organized in the "Seminar room" at Galeb (Kettejeva 1, Koper).

This Monday, we will have two lectures, both will last for approximately 25 minutes.

**(10:00-10:25) Vesna Andova (Institute of Mathematics and Physics, Skopje, Macedonia)**

**Title: Diameter on fullerene graphs**

**Abstract**: Fullerene graphs are 3-connected planar cubic graphs with all

faces of size 5 or 6.

In the talk I will present a results regarding the diameter of

icosahedral fullerenes and fullerene graphs in general.

**(10:30-10:55) Riste Škrekovski (FMF and IMFM, Ljubljana, Slovenia)**

**Title: Some results on network centralitiy indicies**

**Abstract**: Centrality is used to quantify an intuitive feeling that in

most networks some vertices are more central than others.

In the talk we consider some graph theoretical results on closeness,

betweenness centrality, and eccentricity.

**All welcome!**

**Datum in ura**/ Date and time: 8.10.12

**Predavalnica**/ Location: Seminar room at Galeb (Kettejeva 1, Koper)

**Predavatelj**/ Lecturer: Martin Milanič

**Naslov**/ Title: On graphs whose complement and square are isomorphic

**Vsebina**/ Abstract:

We study square-complementary graphs, that is, graphs whose complement and square are isomorphic.

We prove several necessary conditions for a graph to be square-complementary, describe ways of building new square-complementary graphs from existing ones, construct infinite families of square-complementary graphs, give a characterization of natural numbers n for which there exists a square-complementary graph of order n, and characterize square-complementary graphs within various graph classes. The bipartite case turns out to be of particular interest.

Joint work with Anders Sune Pedersen, Daniel Pellicer and Gabriel Verret.

Next week (September 24- September 28, 2012), at the Faculty of Mathematics, Natural Sciences and Information Technologies in Koper, **dr. Ferdinando Cicalese** from the University of Salerno, Italy will be giving three lectures. The lectures will take place in the "Seminar room" at Galeb (Kettejeva 1, Koper).

The lectures will be held on:**- Monday (September 24, 2012) 10:00-11:00****- Wednesday (September 26, 2012) 10:00-11:00
- Friday (September 28, 2012) 10:00-11:00**

**All welcome!**

Title: Models and Methodologies in Combinatorial Search

Title: Models and Methodologies in Combinatorial Search

**Abstract:**

In a typical combinatorial search problem one is required to develop a testing procedure to determine which one of a finite number of possible objects or properties is present in a given sample.

The structure of a typical search problem appears more often than one would expect, in surprisingly diverse scenarios. A search problem can be the task of: (i) identifying objects within a set via a series of tests (identification); (ii) learning the structure of a given function via sampling (learning); (iii) determining the most concise way of representing a given piece of information so that recovery is uniquely achievable (encoding); (iv) distinguishing patterns on the basis of exact or approximate examples (classification).

Typical applications are found in medical diagnosis, database theory, networking, laboratory analysis, computer decision making, bioinformatics data analysis and inference, just to mention a few.

We shall analyze three different scenarios where instances of the above models are found and give a glimpse of the tools and techniques used in the field.

**In the first talk**, we shall discuss a model of approximate string matching. Given a pattern p, and a string s, we are interested in finding any or all jumbled occurrences of the pattern p in the given string. By a jumbled occurrence of p in s we mean the existence of a substring of s which has exactly the same multiplicity of characters of the pattern p, i.e., it coincides with p or with any permutation of p.

**In the second talk**, we shall focus on non-adaptive group testing procedures: in a finite set U we want to identify an initially unknown subset P. We can test any subset Q of U for the presence of elements of P, we also assume some knowledge on the cardinality of the target set P.

We shall look at non-adaptive procedures for group testing, we shall show the connections between this problem and error correcting codes. We shall also survey recent results in this area and discuss known and novel applications.

**In the third talk**, we shall look at a very general model of identification problem, where the reservoir of tests available is restricted. We are given: (i) a finite set of objects, O1,..., On, from which an initially unknown object has to be identified; (ii) a finite set of m tests (or questions) Q1, ..., Qm, which can be used to acquire information about the unknown object to be identified; (iii) a set of m costs, C1, ..., Cm, where Ci is the cost we incur when we apply test Qi.

A solution to the above problem is a deterministic algorithm (decision tree) for choosing which questions to ask such that: (i) the unknown object will always be identified; (ii) as little cost as possible will be incurred. Since this problem is in general hard, we shall concentrate on approximation algorithms. We shall analyze a greedy approach that achieves the best known approximation ratios simultaneously for many different variations of this identification problem.

**Datum in ura**/ Date and time: 11.6.12

**Predavatelj**/ Lecturer: Prof. Luca Rondi (University of Trieste, Italy))

**Naslov**/ Title: Inverse problems and free-discontinuity problems: the inverse crack or cavity problem

**Vsebina**/ Abstract:

Many techniques developed for free-discontinuity problems, arising for example in imaging or in fracture mechanics, may be successfully applied to reconstruction methods for inverse problems whose unknowns may be characterized by discontinuous functions.

As an example we consider the inverse problem of determining insulating cracks or cavities by performing few electrostatic measurements on the boundary. We show the validity of this approach both from the theoretical point of view, by a convergence analysis, and from the numerical point of view.

**Datum in ura**/ Date and time: 4.6.12

**Predavatelj**/ Lecturer: Adam Paweł Wojda (AGH University of Science and Techology, Poland)

**Naslov**/ Title: Cyclic q-partitions of comlete uniform, and non-uniform hypergraphs

**Datum in ura**/ Date and time: 30.5.12

**Predavatelj**/ Lecturer: Karla Počkaj

**Naslov**/ Title: Construction of rigid body motions

**Vsebina**/ Abstract:

In this talk I will present the rigid body motions and the interpolation of given positions, e.g. points and orientations of a moving object.

**Datum in ura**/ Date and time: 30.5.12

**Predavatelj**/ Lecturer: Boštjan Frelih

**Naslov**/ Title: Amply regular graph products

**Vsebina**/ Abstract:

A regular graph is called amply regular if the number of common neighbours of two adjacent vertices is independent of the choice of these two vertices and the number of common neighbours of

two vertices at a distance 2 is independent of the choice of these two

vertices. In this talk we present some results about amply regular

lexicographic, deleted lexicographic and co-normal graph products.

**Datum in ura**/ Date and time: 28.5.12

**Predavatelj**/ Lecturer: dr. Fabio Vlacci (Università degli Studi di Firenze, Italy)

**Naslov**/ Title: Introduction to basic properties of a new class of regular functions of (hypercomplex) quaternionic variable

**Vsebina**/ Abstract:

The aim of this talk is to give a self-contained introduction to a new theory of regular functions over quaternions and, more in general, over a non commutative algebra. In particular, we'll give a (historic) overview of different possible approaches to a definition of regularity for quaternionic functions and focus our attention on the geometric/analytic properties related to the class of functions which are regular according to the recent definition given by Gentili & Struppa in 2007.

We'll also present some applications and results which are in some cases a generalization of the similar results in Complex Analysis, in others are quite unexpected and promising for the study of new phenomena. Some related topics will be then considered in order to show what kind of difficulties or open problems are still under investigation.

**Datum in ura**/ Date and time: 28.5.12

**Predavatelj**/ Lecturer: dr. Wilfried Imrich (University of Leoben, Austria)

**Naslov**/ Title: The distinguishing and endomorphism distinguishing number of graphs and groups

**Vsebina**/ Abstract:

The distinguishing number of graphs was introduced by Albertson and Collins 1996, and has spawned a wealth of results on finite and infinite structures. The idea of the distinguishing number is to break symmetries efficiently, where "symmetries" stands or automorphisms. If one also wishes to break endomorphisms, one arrives at the endomorphism distinguishing number. Although endomorphisms are quite untractable, compared to automorphisms, many interesting results for finite and infinite structures immediately generalize from automorphisms to endomorphisms, and many new and interesting problems arise.

**Datum in ura**/ Date and time: 24.5.12

**Predavatelj**/ Lecturer: Hiroki Koike

**Naslov**/ Title: The isomorphism problem for cyclic configurations

**Vsebina**/ Abstract:

**Abstract**: An incidence geometry consists on a set of points X of points and a set of blocks, or lines (subsets of X), such that two blocks intesect in at most one point. An incidence geometry is a *configuration*** **if every line has the same number of points and every point is incident with the same number of lines. A configuration is** ***cyclic*** **if its automorphism group contains a regular cyclic subgroup. The isomorphism problem for cyclic configurations asks for sufficient conditions to check wether two cyclic configurations are isomorphic or not. We say that two cyclic configurations are *multiplier equivalent* if some element of the multiplicative group of Z_n induces an isomorphism. A related problem is that for which n two isomorphic cyclic configurations are multiplier equivalent. In this talk we show some known results for general cyclic combinatorial objects and we present some partial results for the latter problem.

**Datum in ura**/ Date and time: 24.5.12

**Predavalnica**/ Location: Samed Bajrić

**Naslov**/ Title: The Representations of Vectorial Boolean Functions

**Datum in ura**/ Date and time: 21.5.12

**Predavatelj**/ Lecturer: dr.Ilya Ponomarenko (V. A. Steklov Institute of Mathematics,Russia)

**Naslov**/ Title: Solvability of finite Schur groups

**Vsebina**/ Abstract:

Let G be a Schur group, i.e. each Schur ring over G arises from

a suitable permutation group which contains a regular subgroup isomorphic

to G. Then the group G is solvable. This is a joint work with A.Vasiliev.

**Datum in ura**/ Date and time: 17.5.12

**Predavatelj**/ Lecturer: Alexander Vasilyev

**Naslov**/ Title: Approach of lazy calculations in application to topological graph indices in Sage. Introduction to a new molecular class

**Vsebina**/ Abstract:

**Abstract:** Previously we introduced a molecular graph class based on standard Sage graph class. The classical approach of object-oriented model proved to be not at its best on a huge amount of data. The conception of lazy calculations and some optimizations allowed us to dramatically increase the performance. We will talk about the nature of such problems in calculations and some solutions to avoid them.

**Datum in ura**/ Date and time: 17.5.12

**Predavatelj**/ Lecturer: Iva Antončič

**Naslov**/ Title: Half-arc-transitive graphs of particular orders

**Vsebina**/ Abstract:

**Abstract**: A graph is said to be half-arc-transitive if the automorphism group of the graph acts transitively on the vertex set and the edge set of the graph, but not on the arc set of the graph. In this talk we present results on classification of half-arc-transitive graphs of orders p, 2p, 3p, 4p, pq, 2pq, p^2, p^3, p^4 and 2p^2, where p and q are primes, with an emphasis on tetravalent graphs.

**DOWNLOAD!**

**Datum in ura**/ Date and time: 14.5.12

**Predavatelj**/ Lecturer: dr. Roman Nedela (Matej Bel University, Slovakia)

**Naslov**/ Title: 6-decompositions of snarks

**Vsebina**/ Abstract:

A snark is a cubic graph with no proper $3$-edge-colouring. In 1996, Nedela and \v Skoviera proved the following theorem:

$3$-edge-colourable components $M$ and $N$. Then both $M$ and $N$ can be completed to two snarks $\tilde M$ and $\tilde N$ of order not exceeding that of $G$ by adding at most $\kappa(k)$ vertices, where the number $\kappa(k)$ only depends on $k$. The known values of the function $\kappa(k)$ are $\kappa(2)=0$, $\kappa(3)=1$, $\kappa(4)=2$ (Goldberg, 1981), and $\kappa(5)=5$ (Cameron, Chetwynd, Watkins, 1987). The value $\kappa(6)$ is not known and is apparently difficult to calculate. In 1979, Jaeger conjectured that there are no 7-cyclically-connected snarks. If this conjecture holds true, then $\kappa(6)$ is the last important value to determine. Our talk is aimed attacking the problem of determining $\kappa(6)$ by investigating the structure and colour properties of potential complements in $6$-decompositions of snarks. We find a set of $14$ complements that suffice to perform $6$-decompositions of snarks with at most $30$ vertices. We show that if this set is not complete to perform $6$-decompositions of all snarks, then $\kappa(6)\geq 20$ and there are strong restrictions on the structure of (possibly) missing complements.

Part of the proofs are computer assisted.

**10.05.2012** **Lecturer: Nina Chiarelli**

**Title**:

**Split graphs and threshold graphs**

**Abstract:**The chromatic number of a graph is the minimum number of colors needed to color the vertices of the graph in such a way that no adjacent vertices have the same color. A clique in a graph is a subset of pairwise adjacent vertices. Graphs for which the chromatic number

of every induced subgraph is equal to the size of its largest clique, are called perfect graphs. In this talk we will give basic definitions and present different characterizations (with forbidden induced subgraphs and with degree sequences) for split graphs and threshold graphs, two of the many families of perfect graphs.

**10.05.2012** **Lecturer**:** Ademir Hujdurović**

**Title: Half-arc-transitive graphs with small number of alternets**

**Abstract**: A graph is said to be half-arc-transitive if the automorphism group of the graph acts transitively on the vertex set and the edge set of the graph, and not transitively on the set of all arcs of the graph. In this talk we will describe the notion of the alternets in the half-arc-transitive graphs, and give some results in the case when the number of alternets is small.

**7. maja 2012.**ob

**11:00**, bo

**v seminarski sobi v Galebu**, v okviru raziskovalnega matematičnega seminarja, predaval

**prof. dr. Mihael Perman.**

Vljudno vabljeni k udeležbi na predavanju!

**Title: Testing the roulette wheel**

**Abstract**: The roulette wheel in principle generates random numbers uniformly distributed on the set {0,1,2,...,36}. Mechanical imperfections or wilful manipulation can lead to deviations from uniformity in various ways. Gambling houses are interested in statistics that would detect such deviations as soon as possible with the smallest probability of false alarms. The talk will present the design and the logic behind various test statistics and some of the theoretical background. The questions lead to nice illustrations of statistical concepts like sufficiency and sequential methods. At the end we will also present an optimal strategy to take advantage of a biased wheel.

**23.4.2012 Lecturer: dr. Barbara Boldin**

**Title:** **Modelling viral evolution in a heterogeneous within-host environment: insights into the HIV co-receptor switch**

**Abstract**: From the point of view of a pathogen, a host is a structured and a heterogeneous environment. In the case of HIV, for example, the existence of spatial structure is supported by the fact that the virus is found in different tissues while environmental heterogeneity originates from the ability of the pathogen to exploit different types of immune cells. To understand how heterogeneity of the within-host environment affects viral evolution we formulate a mathematical model and investigate the conditions under which viral diversification occurs within a host. Applying the model to the case of HIV, we show that the model captures three main properties of the so called co-receptor switch that is observed in many HIV infections: the initial dominance of virus strains that infect CCR5+ cells, the late switch in some (but not all) HIV infections and the associated drop in the number of uninfected T-cells. This suggests that the co-receptor switch may be a result of gradual adaptation of the virus population to target cell heterogeneity. More generally, we argue that mathematical modelling and evolutionary ecology can help us better understand the course of some infections. The talk is based on joint work with Samuel Alizon.

**17.4.2012 and 24.4.2012**there was a minicourse

"

**Finite p-groups: the basics, generators, and automorphisms**" (10 lectures) given by

**Prof. Gustavo A. Fernandez Alcober**(University of the Basque Country, Bilbao, Spain).

Program:

1. Basic theory of finite p-groups.

2. Some special families of finite p-groups.

3. Generators of finite p-groups: the Frattini subgroup and the Burnside Basis Theorem.

4. Power-commutator presentations of finite p-groups.

5. Constructing automorphisms: von Dyck's theorem.

6. General structure of the automorphism group of a finite p-group

7. Automorphism groups of some known p-groups

8. Existence of outer automorphisms

9. Open problems about automorphism groups

**16.04.2012 Lecturer: Rok Požar ****(****IMFM Ljubljana)**.

**Title: ****On the split structure of lifted groups**

**Abstract**: Let *p*: *X*˜ *→ X *be a regular covering projection of connected graphs, and let CT*p *denote the group of covering transformations. We present an algorithm for testing whether a given group of automorphisms *G*˜ *≤ *Aut(*X*˜ ) lifts along *p *as a split extension of CT*p *by *G *in the case when CT*p *is abelian. Next, we present an algorithm for testing whether *G *lifts as a split extension such that some complement of CT*p *within *G*˜ has an orbit which is a section over a *G*-invariant set of vertices of *X *. Both algorithms are part of a larger package (implemented in MAGMA) for doing computations with graph covers. The implementation allows computing with graphs having semiedges.

**Slides from the talk are available here: DOWNLOAD!**

**02.04.2012 Lecturer: dr. Martin Mačaj ****(****Comenius University, Slovakia and UP FAMNIT).**

**Title: ****Nonorientable regular maps over linear fractional groups**

**Abstract**: It is well known that for any given hyperbolic pair

*(k,m)*there exist inﬁnitely many regular maps of valence

*k*and face length

*m*on an orientable surface, with automorphism group isomorphic to a linear fractional group. A nonorientable analogue of this result was known to be true for all pairs

*(k,m)*as above with at least one even entry. In this talk we establish the existence of such regular maps on nonorientable surfaces for all hyperbolic pairs.

Ob 25. obletnici Erasmusa je slovenska nacionalna agencija CMEPIUS pripravila natečaj »Erasmus in jaz«. Nagradili bodo najboljši video posnetek, fotografijo ali zgodbo z delovnim naslovom »Izkušnja z Erasmus mobilnosti kot priložnosti za osebni in strokovni razvoj študenta«. Razglasitev rezultatov in podelitev dobrih nagrad bo potekala 7. maja v Mariboru v okviru promocijske kampanje Mladi in mobilnost.

**Danes, 02. april 2012, je zadnji dan za oddajo gradiva!!!**

Več o natečaju izveste na spodnji povezavi http://www.cmepius.si/vzu/erasmus/natecaj-2012.aspx.

**28.03.2012 Lecturer: ****dr. ****Gábor Gévay **(University of Szeged, Hungary)

Title: **Geometric ( n_{k}) configurations**

Abstract: In the simplest case, a geometric (*n*_{k}) configuration is a set of *n* points and *n* lines such that each of the points is incident with precisely *k* of the lines and each of the lines is incident with precisely *k* of the points. Instead of lines, the second subset may consist of planes, hyperplanes, circles, ellipses, etc. We discuss some construction principles, and review some recently discovered classes of such configurations. We also formulate an incidence conjecture concerning a spatial (100_{4}) point-line configuration.

**Slides from the talk are available here: DOWNLOAD!**

**26.03.2012 Lecturer: dr. Marcin Anholcer **(Poznan Univeristy of Economics, Poland)

**Title: ****Group irregularity strength of graphs**.

Abstract: We investigate the \textit{group irregularity strength} ($s_\mathcal{G}(G)$) of graphs, i.e. the smallest value of $s$ such that taking any Abelian group $\mathcal{G}$ of order $s$, there exists a function $f:E(G)\rightarrow \mathcal{G}$ such that the sums of edge labels in every vertex are distinct. We prove that for any connected graph $G$ of order at least $3$, $s_\mathcal{G} (G)=n$ if $n\neq 4k+2$ and $s_\mathcal{G} (G)\leq n+1$ otherwise, except the case of some infinite family of stars.

The slides from the talk are available here: **DOWNLOAD!**

**19.03.2012 Lecturer: ****dr. Oliver Schaudt** (Universität zu Köln, Germany).

**Title**: The Price of Connectivity for Vertex Cover

**Abstract**: We study a graph parameter called the Price of Connectivity for Vertex Cover (PoC). It was recently introduced by Cardinal et al. and is defined as the ratio of the minimum size of a connected vertex cover and the minimum size of a vertex cover.We prove some structural results for the PoC. These results concern PoC-critical, PoC-perfect and PoC-near-perfect graphs.

**Slides from the talk are available here: DOWNLOAD!**

**12.03.2012 Lecturer: dr. Istvan Kovacs**

**Title: The isomorphism problem for rose window graphs**

**Abstract:**For an integer n ≥ 3, and a, r ∈ {1, 2, ..., n − 1} with r ≠ n/2, the rose window graph R

_{n}(a, r) is the graph Γ, where V (Γ) = {A

_{i }, B

_{i}| i ∈ {0, 1, ..., n − 1}}, and E(Γ) consists of four types of edges as for every i ∈ {0, 1, ..., n − 1}: {A

_{i}, A

_{i+1 }}, {A

_{i }, B

_{i}}, {A

_{i+a}, B

_{i}} and {B

_{i}, B

_{i+r}},

^{2}for which Rn (b, s) is isomorphic to Rn (a, r). We present a solution using a permutation group theoretical approach. This is a joint work with E. Dobson and Š. Miklavič.

**05.03.2012 Lecturer: dr. Marko Orel**

**Title:**

**The mathematics in computed tomography (CT)**

**Abstract:**In 1979, the Nobel Prize for Medicine and Physiology was awarded jointly to Allan

McLeod Cormack and Godfrey Newbold Hounsfield, the two pioneering scientistengineers

primarily responsible for the development, in the 1960s and early 1970s,

of computerized axial tomography, popularly known as the CAT or CT scan.

At the seminar I will present the mathematics involved in computed tomography.

**27.02.2012 Lecturer: dr. Klavdija Kutnar**

**Title: ****Cayley snarks**

**Abstract:** In this talk I will discuss the well-known conjecture that there are no snarks amongst Cayley graphs. I will present an innovative approach in solving this conjecture combining the theory of Cayley maps and the existence of independent set of vertices whose complement induces a forest in arc-transitive graphs admitting a group of automorphisms acting regularly on the set of arcs with cyclic vertex stabilizer, together with some partial results obtained thus far.

This is a joint work with Ademir Hujdurovic and Dragan Marusic.

**DOWNLOAD THE SLIDES FROM THE TALK HERE: DOWNLOAD!**

**20.02.2012 Lecturer: dr. Vito Vitrih**

**Title:**

**Pythagorean-hodograph curves**

**Abstract:**Polynomial Pythagorean-hodograph curves (PH curves) have been introduced in 1990 by Farouki and Sakkalis. They are characterized by the property that their parametric speed, i.e., the derivative of the arc length with respect to the curve parameter, is a polynomial function. Polynomial PH curves form an important class of parametric polynomial curves for which the arc length can be computed exactly and their offsets (parallel curves) are rational curves. This makes them very useful in many practical applications, e.g. in CAD/CAM systems, robotics, animation, NC machining, spatial path planning based on rotation-minimizing frames, etc.

**D**

**OWNLOAD THE SLIDES FROM THE TALK HERE: DOWNLOAD!**

**06.02.2012 Lecturer: Hiroki Koike**

**Title:** **Isomorphic Tetravalent cyclic Haar graphs**

**Abstract:** Let S be a subset of the cyclic group Zn. The cyclic Haar graph H(Zn,S) is the bipartite graph with vertex set two copies of the cyclic group and edges {x,y} where x and y are in Zn and x-y is in S. We give necessary and sufficient conditions for the isomorphism of two connected cyclic Haar graphs of valency 4.

**30.01.2012 Lecturer: Alexander Vasilyev**

**Title: Introduction to Sage. Examples of application to Graph theory**

**Abstract:**Sage (previously SAGE) is mathematical software with features covering many aspects of mathematics, including algebra, combinatorics, numerical mathematics, number theory, and calculus. In this talk we present Sage and provide some examples for usage in Graph theory. Moreover, we will talk about the stucture of the math chemistry package we are working on.

**23.01.2012 Lecturer: Samed Bajrić**

**Title: Almost Perfect Nonlinear functions**

**Abstract**: In this talk we present some basic properties of Almost Perfect Nonlinear (APN) functions over finite field of characteristic 2 and investigate some open problems. We provide the characterizations of Almost Perfect Nonlinear functions and of APN permutations by means of their component functions, which can be used in an iterated secret-key block cipher as a round function to protect it from a differential cryptanalysis. We conclude with the list of all, up to equivalence, APN and Almost Bent (AB) functions, which are equivalent to certain power functions f: GF(2^n) --> GF(2^n), f(x) = x^k.

**DOWNLOAD THE SLIDES FROM THE TALK: DOWNLOAD!**

**16.01.2012 Lecturer: **dr. **Gyorgy Kiss (***Eötvös Loránd University, Budapest***)****.**

**Title: Semiarcs and semiovals in PG(2, q)**

**Abstract**: Ovals, k-arcs and semiovals of ﬁnite projective planes are not only interesting geometric structures, but they have important applications to coding theory and cryptography, too. Semiarcs are the natural generalizations of arcs. Let Πq be a projective plane of order q. A non-empty pointset St ⊂ Πq is called a t-semiarc if for every point P ∈ St there exist exactly t lines 1 , 2 , . . . t such that St ∩ i = {P } for i = 1, 2, . . . , t. These lines are called the tangents to St at P. The classical examples of semiarcs are the semiovals (t = 1) and the subplanes (t = q − m, where m is the order of the subplane.) In this talk we consider those semiarcs in PG(2, q), which are contained in the union of three concurrent lines. Applying theorems coming from additive group theory, we prove bounds on the sizes of these semiarcs and construct new examples. We investigate strong semiovals, too. For p prime, the complete classiﬁcation of strong semiovals in PG(2, p2 ), and the proof of the nonexistence of these objects in PG(2, p) was given in [?]. We extend these results for arbitrary powers of p. In particular we prove that there is no strong semioval in PG(2, p2r+1 ) if p > 7, and prove that the size of each strong semioval in PG(2, p2r ) is 3(p2r − pr ).

**09.01.2012 Lecturer: dr. ****Gabriel Verret**

**Title: Constructing a census of small cubic vertex-transitive graphs.**

**Abstract**: We describe some recent theoretical results and various tricks which allowed us to compute a census of all cubic vertex-transitive graphs of order at most 1280. We also discuss how these methods could be expanded to higher order or valency. This is joint work with Primoz Potocnik and Pablo Spiga.