2012 - Spring semester

June 14, 11:00 AM, Room #60
Marko Savić (Novi Sad): A linear time algorithm for optimal feed-link placement in polygonal networks

A polygon representing transportation network is given, together with p, a point in its interior. We aim to extend the network by inserting a line segment, called feed-link, which connects p to the boundary of the polygon. Geometric dilation of some point q on the boundary is the ratio between the length of the shortest path from p to q through the extended network and their Euclidean distance. The utility of a feed-link is inversely proportional to the maximal dilation over all boundary points. We give a linear time algorithm for computing the feed-link with the minimum overall dilation, thus improving upon the previously known algorithm of almost O(n log n) complexity.

June 12, 13:00 PM, Amphitheatre I
Volker Mehrmann (Berlin): Numerical solution of eigenvalue problems in acoustic field computation and car design

June 7, 12:00 PM, Room #60
Andreas Kühne (München): Mathematics in the work of Nicolaus Copernicus

May 10, 12:00 PM, Room #60
Đura Paunić (Novi Sad): Olga Taussky-Todd (1906-1995)

April 26, 12:00 PM, Room #60
Ljiljana Cvetković (Novi Sad): Nekrasov matrices and their applications

As is well-known, the class of strictly diagonally dominant (SDD) matrices is intimately related to the Jacobi iterative method; in a similar fashion, the class of Nekrasov matrices arises from the Gauss-Seidel method. There is an connection between these two classes, which enables several interesting applications.

April 12, 12:00 PM, Room #60
Maja Nedović (Novi Sad): The Schur complement - its historical development, eigenvalues and closure properties

Based on the book by Fuzhen Zhang, The Schur Complement and its Applications, we give the early development of the Schur complement and illustrate its power as a rich and basic tool in mathematical research and applications. The special emphasis is on results concerning the eigenvalues of the Schur complement for some matrix classes based on diagonal dominance. Also, we analyze matrix classes that enjoy closure properties under Schur complementation, or, in other words, we examine which properties remain invariant under transformations of this type.

April 5, 12:00 PM, Room #60
Miloš Stojaković (Novi Sad): Approximate sorting

We will look at a variation of one of the most important problems in computer science - devising a comparison based algorithm for sorting n given values in ascending order. Our goal is to explore possibilities and obstacles for producing a (deterministic or randomized) algorithm that outputs the order that is "not far" from the ascending order, and (hopefully) runs faster than the classical sorting algorithms.

This is joint work with Joachim Giesen and Eva Schuberth.

March 29, 12:00 AM, Room #60
Michael Pinsker (Paris): Reducts of Ramsey structures: the canonical approach

Consider the following problem: We are given a countably infinite base structure S in a finite relational language; the goal is to determine its reducts, i.e., all relational structures T on the domain of S which have a first-order definition in S. When doing so, we identify reducts T, T' of S when they are first-order interdefinable.

This problem has been studied for numerous base structures S, in particular for homogeneous structures. For example, Cameron showed that the dense linear order has 5 reducts, Thomas proved that the random graph has 5 reducts as well, and Junker and Ziegler found that the dense linear order with a constant has 116 reducts.

With the original goal of refining Thomas' classification of the reducts of the random graph, Bodirsky and I developed a general method that turns out to be applicable to a considerable class of homogeneous base structures S, namely the class of such structures which are ordered and have a certain combinatorial property called the Ramsey property. For example, the method has since been used in order to find the reducts of the random partial order (number of reducts: 5 again!) and the random triangle-free graph with a constant (number of reducts: 13).

I will present our method and outline how it can be used in order to reprove Thomas' theorem.

March 22, 12:00 PM, Room #60
Vladimir Kostić (Novi Sad): An unsupervised competitive neural network in modeling of stability in the formation of cognitive maps

Neural network models of human brain represent large- and multi-time-scales nonlinear dynamical systems that contain neuron activity and synaptic changes of the formed cognitive maps. These systems are the basis for every single cognitive task and their complex dynamical behavior is more and more thoroughly mathematically investigated. These biological networks, inherently, undergo many parametric perturbations, thus, understanding instabilities of their dynamical behavior is an important task. Therefore, in this talk, we will first develop conditions on the activation functions, synaptic weights and impact weights of external stimuli, relatively to neural timescales, that guarantee global stability of a network, and later investigate influence of certain perturbations that occur in nature.

March 8, 12:00 PM, Room #60
Ljiljana Cvetković (Novi Sad): Circles alternative to Geršgorin circles

The simple and nice idea of localizing eigenvalues of a given matrix by circles, as it was done by Geršgorin in his famous theorem, can be combined with a similarity transformation that corresponds to the first step of Gaussian elimination. The resulting  area can localize eigenvalues much better that original Geršgorin set.