# Raziskovalni matematični seminar - Arhiv

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

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

**19.12.2011 Lecturer: **dr. Primož Potočnik (University of Ljubljana, Slovenia)

**Title:** **Group amalgams and locally arc-transitive graphs.**

Abstract: A group amalgam is a quintuple (L,f,B,g,R) where L,B and R are abstract groups and f:B->L and g:B->R are group monomorphisms. Given a connected locally G-arc-transitive graph X (ie. a connected graph X together with a group of automorphisms G of X such that the vertex-stabiliser G_v is transitive on the neighbourhood of v in X for every vertex v of X), one can consider the amalgam (G_v,f,G_uv,g,G_u) where f and g are the inclusion mappings. Conversely, given an amalgam (satisfying certain additional requirements), one can construct all connected locally arc-transitive graphs up to a given number of vertices that realises the amalgam. This interplay of amalgams and graphs will be described in the talk in some (but not too many) details.

**28.11.2011 Lecturer: dr. Štefko Miklavič**

**Title: **Automorphism groups of the "Rose-window" graphs which are not edge-transitive.

**Download the slides from the talk here: DOWNLOAD!**

**21.11.2011 Lecturer: Ademir Hujdurović**

**Title:** **Quasi m-Cayley graphs**

**Abstract:**A graph Γ is called a quasi m-Cayley graph on a group G if there exists a vertex

_{∞}of the vertex ∞ in the full

**14.11.2011 Lecturer: dr. Martin Milanič**

**Title:** **Hereditary efficiently dominatable graphs**

**Abstract**: An efficient dominating set (or perfect code) in a graph is a set of vertices the closed neighborhoods of which partition the graph's vertex set. It is NP-complete to determine whether a given graph contains an efficient dominating set. We study the class of hereditary

efficiently dominatable graphs, that is, graphs every induced subgraph of which contains an efficient dominating set. Based on a decomposition theorem for (bull, fork, C_4)-free graphs, we derive the forbidden induced subgraph characterization of hereditary efficiently dominatable graphs. We also present a polynomial time algorithm for finding an efficient dominating set (if one exists) in a class of graphs properly containing the class of hereditary efficiently dominatable graphs, by reducing the problem to the maximum weight independent set problem in claw-free graphs.

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

**07.11.2011 Lecturer: ****Dr. Sugata Gangopadhyay** (Department of Mathematics at Indian Institute of Technology, INDIA).

**Title:** **Boolean functions in Cryptology.**

**Download the slides from the talk: DOWNLOAD!**

**10.10.2011** **Lecturer: dr. Sergei Evdokimov ****(Petersburg Department of V.A.Steklov Institute of Mathematics, St. Petersburg, Russia)**

**Title:** **Characterization of Cyclic Schur Groups**

**Abstract:** We say that a finite group G is a Schur group if every S-ring over it is schurian, i.e. determined by a suitable permutation group on G containing the regular subgroup of right translations. Here under an S-ring over G we mean a subalgebra of the group algebra QG that contains 1_G and is closed with respect to the componentwise multiplication and inversion. In the talk a complete characterization of cyclic Schur groups is given. It follows that the smallest non-Schur cyclic group has order 72. The proof is based on the theory of circulant S-rings and on the criteria of schurity and non-schurity for them. (joint work with I. Kov´acs and I. Ponomarenko).

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

**13.06.2011 10:00 Seminarska soba v Galebu**

**Lecturer:**

**dr. Ilya Ponomarenko (Petersburg Department of V.A.Steklov Institute of Mathematics, St. Petersburg, Russia)**

**Title:** **On quasi-thin association schemes (joint with M.Muzychuk)**

**Abstract:** An association scheme is called quasi-thin if the valency of each its basic relation is one or two. A quasi-thin scheme is Kleinian if its thin residue is the Klein four-group with respect to relational product.

It turns out that any Kleinian scheme arises from near-pencil on

**06.06.2011 10:00 Seminarska soba v Galebu**

**Lecturer: Samed Bajrić**

**Title:****Linear Cryptanalysis**

**Abstract:** In this talk we present the details of linear cryptanalysis, one of the most significant attack applicable to symmetric-key block cipher. The topic is based on the analysis of a simple, yet realistically structured, basic Substitution-Permutation Network cipher. Understanding the attacks as they apply to this structure is useful, as the Rijndael cipher, recently selected for the Advanced Encryption Standard (AES), has been derived from the basic SPN architecture.

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

**30.05.2011 10:00 Seminarska soba v Galebu**

**Lecturer:**

**Alexander**

**Vasilyev**

**Title:**

**Communicability Graph and Community Structures in Complex Networks**

**Abstract:**Estrada and Hatano proposed an algorithm for the detection of community structure in complex networks using the concept of network communicability.The communities are defined as the cliques of a “communicability graph”, which has the same set of nodes as the complex network and links determined by the communicability function. Then, the problem of finding the network communities is transformed to an all-clique problem of the communicability graph. In addition, we extend here the concept of the communicability to account for the strength of the interactions between the nodes by using the concept of inverse temperature of the network. We develop an algorithm to manage the different degrees of overlapping between the communities in a complex network. Finally, we amend this algorithm by eliminating the subjectivity of choosing degree of overlapping and including an additional check of the fitness of detected communities. We show that this amendment can detect some communities which remain undetected by the original Estrada and Hatano’s algorithm.

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

**23.05.2011 10:00 Seminarska soba v Galebu**

**Lecturer: Anna Klymenko**

**Title: The Coxeter Graph**

**Abstract:**

**According to Lovasz conjecture, every finite connected vertex-transitive graph contains a Hamiltonian cycle except**

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

**16.05.2011 9:00 Seminarska soba v Galebu**

**Title**:

**Steiner index of a graph**

**Abstract**: Given a subset

**16.05.2011 10:00 Seminarska soba v Galebu**

**Title: Median graphs and algebras**

**Abstract**: In this talk we present a strong connection between certain ternary algebras, called median algebras, that enjoy three simple axioms, and the class of median graphs. The latter are defined as the graphs in which for any triple of vertices the three intervals between pairs of the triple share exactly one vertex. Median graphs are the most important class in metric graph theory, and appear in several applications in Computer science, mathematical biology and elsewhere.

**You can download the slides from the talk here: DOWNLOAD!**

**09.05.2011**

**10:00 Seminarska soba v Galebu**

**Title: The isomorphism classes of all generalized petersen graphs**

**Abstract**:The generalized Petersen graphs GP(

*n, k*) were introduced by Watkins in 1969, and since then have been studied extensively. For an ordered pair (

*n, k*), where 1

*≤*

*k*

*≤*

*n*

*−*1,

*k*=

*n/*2, the generalized Petersen graph GP(

*n, k*) has vertex set Z

_{2}

*×*Z

_{n}and edge set

*{*(1

*, i*)(1

*, i*+1)

*,*(0

*, ki*)(0

*, ki*+

*k*)

*,*(0

*, i*)(1

*, i*) :

*i*

*∈*Z

_{n}

*}*. Many well-known graphs are generalized Petersen graphs, with GP(5

*,*2) being the Petersen graph itself, GP(4

*,*1) being the skeleton of the three dimensional cube, GP(10

*,*2) being the skeleton of the dodecahedron, and GP(10

*,*3) is the Desargues graph (the Levi or incidence graph of the Desargues configuration). In this talk, we determine necessary and sufficient conditions for two generalized Petersen graphs GP(

*n, k*) and GP(

*n, ℓ*) to be isomorphic. The conditions are that either

*k*

*≡ ±ℓ*(mod

*n*) or that

*kℓ*

*≡ ±*1 (mod

*n*).

**You can download the slides from the talk here: DOWNLOAD!**

**18.04.2011. ob 10:00 Seminarska soba v Galebu**

**Predavatelj: dr.**

**Alexander Mednykh (Sobolev Institute of Mathematics, Novosibirsk, Russia)**

**Title**:

**Counting coverings and maps**

**Abstract**: In this lecture we give a new method to count finite sheeted coverings of

manifolds with a finitely generated fundamental group. We apply it to count

branched and unbranched coverings over compact surfaces (bordered or with

empty border).

As a consequence, we suggest a new approach to count maps on surfaces up to

orientation preserving homeomorphism. The further development of the method

gives us a possibility to count chiral maps (or twins) by number of edges on a

closed orientable surface.

**You can download the slides from the talk here: DOWNLOAD!**

**04.04.2011.**ob

**10:00 Seminarska soba v Galebu**

**Predavatelj: Q.Sergio Hiroki Koike**

**Title**:

**On isomorphism of cyclic Haar graphs.**

**Abstract**: Given a cyclic group and a subset of this group, we define a cyclic Haar graphs as a bipartite graph with two copies of the cyclic group and a edge

**{i,i+j}**with

**i**in one partition and

**i+j**in the other.

Given a fix cyclic Haar graph

**H(n,A)**. We say that

**A**is an

**HI**-set if for any subset

**B**of the cyclic group such that the cyclic Haar graphs

**H(n,A)**and

**H(n,B)**are isomorphic then there is an element

**f**in the affine group of the cyclic group which maps

**B**into

**A**. The graph isomorphism problem in the class of cyclic Haar graphs is, esentially, to describe the pairs

**A**and

**B**for which the graphs

**H(n,A)**and

**H(n,B)**are isomorphic but there is not such function which maps

**B**into

**A**.

In this talk we will discuss some tools to find which graphs are isomorphic and there is an element

**f**in the affine group of the cyclic group which maps

**B**into

**A**.

**28.03.2011.**ob

**10:00 Seminarska soba v Galebu**

**Predavatelj: dr.Martin Milanič**

**Title**:

**Towards a combinatorial characterization of equistable graphs - partial results on a conjecture of Orlin**

**Abstract**: Equistable graphs are graphs for which there exists a linear functional which characterizes the maximal stable sets of the graph. (A stable set is a set of pairwise non-adjacent vertices.) A conjecture due to Jim Orlin states that every equistable graph is a general partition graph (i.e., the intersection graph of a set system over a finite set S such that the maximal stable sets correspond precisely to the partitions of S using only sets from the family).

Orlin's conjecture holds within the class of chordal graphs; if true in general, it would provide a combinatorial characterization of equistable graphs. In this talk, we will explain the known connections between general partition graphs, equistable graphs, and triangle graphs, and show some partial results on Orlin's conjecture. In particular, we will present a complete characterization of equistable graphs decomposable with respect to the Cartesian or the tensor product.

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

**21.03.2011.**ob

**10:00 Seminarska soba v Galebu**

**Predavatelj: mag. Boštjan Frelih**

**Title**:

**Classification of cubic symmetric fivecirculants**

**Abstract**: A fivecirculant is a graph admitting an automorphism having five cycles of equal length in its cycle decomposition. A graph is said to be symmetric if its automorphism group acts transitively on the set of its arcs. In this talk, we give a classification of cubic symmetric fivecirculants.

**14.03.2011.**ob

**10:00 Seminarska soba v Galebu**

**Predavatelj: dr. Vito Vitrih**

**Title**:

**High order parametric polynomial approximation of conic sections**

**Abstract**: In this talk a particular shape preserving parametric polynomial approximation of conic sections will be presented. An ellipse and a hyperbola can be represented in a parametric form using e.g. trigonometric and hyperbolic functions. But, in contrast to a parabola, they do not have a parametric polynomial parameterization. In many applications a parametric polynomial approximation of conic sections is needed and it is important to derive accurate polynomial approximants. We will derive polynomial approximants with the highest possible approximation order in a closed form.

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

**07.03.2011.**ob

**10:00 Seminarska soba v Galebu**

**Predavatelj: Ademir Hujdurović**

**Title**:

**Bipartite locally distance transitive graphs.**

**Abstract**: In this talk we introduce the definition of locally distance transitive graph, and prove some basic properties. We also discuss possible characterization of bipartite locally distance transitive graphs.

**28.02.2011.**ob

**10:00 Seminarska soba v Galebu**

**Predavatelj: dr. Štefko Miklavič**

**Title**:

**A problem from the theory of distance-regular graphs (Part II)**

**Abstract**:In this talk we present a problem from distance-regular graphs. A solution of this problem would lead to a complete classification of Q-polynomial distance-regular graphs with a maximal possible girth.

**21.02.2011.**ob

**10:00 Seminarska soba v Galebu**

**Predavatelj: dr. Štefko Miklavič**

**Title**:

**A problem from the theory of distance-regular graphs (Part I)**

**Abstract**:In this talk we present a problem from distance-regular graphs. A solution of this problem would lead to a complete classification of Q-polynomial distance-regular graphs with a maximal possible girth.

**31.01.2011**. ob **10:00 Seminarska soba v Galebu**

**Predavatelj: dr.**

**Jiangtao Shi**(School of Mathematical Sciences, Peking University, China)

**Title**: **On an inverse problem to Frobenius's theorem**

**Abstract**: Let *G* be a finite group and *e* a positive integer dividing |G|, the order of G.

*L*

_{e}(G) = {x \in*G| x*Frobenius proved that

^{e}= 1},*|L*=

_{e}(G)|*ke*for a

*k*≥ 1. In this talk, we give a complete classification of finite groups

_{e}(G)| ≤

*2e*for every

*e*dividing |G|.

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

**10.01.2011**. ob

**10:00 Seminarska soba v Galebu**

**Predavatelj: dr. Bojan Kuzma**

**Naslov**:

**On conversion of permanent into determinant.**

**Povzetek**: Though definition of permanent looks deceptively similar to determinant, the former is much harder to calculate than the later. A possible remedy is to convert a matrix such that the permanent of original matrix equals determinant of converted matrix. This conversion is given by a map on matrices. We will show that for matrices over finite fields no such bijective conversion is possible.