University of Primorska Faculty of Mathematics, Natural Sciences and Information Technologies
SI | EN

Mathematical Research Seminar - Archive

2024 2023 2022 2021 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
∞ ∈ V (Γ) and a subgroup G of the vertex stabilizer Aut(Γ)∞ of the vertex ∞ in the full
automorphism group Aut(Γ) of Γ, such that G acts semiregularly on V (Γ)\{∞} with m
orbits. If the vertex ∞ is adjacent to only one orbit of G on V (Γ)\{∞}, then Γ is called
a strongly quasi m-Cayley graph on G.We will present the classifications of quasi 2-
Cayley, strongly quasi 3-Cayley and strongly quasi 4-Cayley arc-transitive circulants.

 

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 3 points, or affine or projective plane of order 2. The main esult is that any non-Kleinian quasi-thin scheme is the two-orbit scheme of a suitable permutation group.

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 K2, Petersen, Coxeter graph and theirs truncations. We will prove that the Coxeter graph has no Hamiltonian cycle. We will also present some well-know properties of this remarkable graph.
 
 
Slides from the talk are available here: DOWNLOAD!
 
 
 
16.05.2011 9:00 Seminarska soba v Galebu
Lecturer: dr. Matjaž Kovše ( FNM, Univerza v Mariboru and IMFM, Ljubljana )
 
Title: Steiner index of a graph
Abstract: Given a subset H of k vertices in a connected graph G the k-Steiner tree problem is that of finding a connected subgraph of G that contains all the k vertices and has the minimum number of edges among all such subgraphs. The number of edges in this subgraph is denoted by sG(H). It is well known that for k3, it is generally NP-hard to compute sG(H). The k-th Steiner index of a graph G is defined as the sum of all values sG(H) where H ranges over all subsets of k vertices of G. For k=2 this definition coincides with the definition of well known and well studied Wiener index. Hamming graphs are the Cartesian products of complete graphs, and their isometric subgraphs are called partial Hamming graphs. A polynomial time algorithm for computing the k-th Steiner index of partial Hamming graphs will be presented. The main ingredient will be the canonical metric representation of a graph.
 
16.05.2011 10:00 Seminarska soba v Galebu
Lecturer: dr. Boštjan Brešar ( FNM, Univerza v Mariboru and IMFM, Ljubljana )
 
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.
We select a small portion of numerous characterizations and properties of median graphs, with an emphasis on some recent results.
 
You can download the slides from the talk here: DOWNLOAD!
 
09.05.2011 10:00 Seminarska soba v Galebu
Lecturer: dr. Ted Dobson ( Mississippi State University, Department of Mathematics and Statistics )
 
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 Z2×Zn and edge set {(1, i)(1, i+1), (0, ki)(0, ki+ k), (0, i)(1, i) : i ∈ Zn}. 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.
 
 Slides from the lecture are available here: DOWNLOAD!
 
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.

Denoting Le(G) = {x \in G| xe = 1}, Frobenius proved that |Le(G)| = ke for a
positive integer k ≥ 1. In this talk, we give a complete classification of finite groups
G with |Le(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.