2011 - Spring semester

June 6, 12:00 PM, Room #60
Mirjana Rakić (Novi Sad): Doubly biased Maker-Breaker Connectivity game

We study (a:b) Maker-Breaker Connectivity game, played on the edge set of K_n, the complete graph on n vertices, where the winning sets are all spanning trees of K_n. Maker and Breaker take turns in claiming previously unclaimed edges of K_n, with Breaker going first. Breaker claims b edges per turn, while Maker claims a edges per turn. Maker wins the game if by the end of the game he manages to claim all edges of one spanning tree. Breaker wins otherwise. We will determine the winner of the game for almost all values of a and b. 

This is joint work with Dan Hefetz and Miloš Stojaković.

The lecture will be followed by a small season-closing celebration. 

June 2, 12:00 PM, Room #60
Milan Merkle (Belgrade): What do we know about medians?

For a given data set one may define various measures of mean value, among which the usual arithmetic mean was the most frequently used. The notion of an arithmetic mean can be extended to vector spaces, and generalized to the notion of mathematical expectation of random variables. The classical statistical paradigm is based on the arithmetic mean and the method of least squares, yielding a complete and rich theory, with abundance of analytical results. The median (the number which is in the middle of an ordered set of data) and, more generally, quantiles, are used in statistics as a robust alternative to the classical approach. However, since the median is not linear (considered as an operator on the set of probability measures), the theory is not so smooth as it is with expectations, and there are only a few generally known results. In the talk we will present some of less known properties and discuss generalisations to the multivariate case, as well as a recent result about Jensen's inequality for medians, connections to Pitman's nearness criterion and related results.

May 26, 12:00 PM, Room #60
Vladimir Kostić (Novi Sad): Cartesian ovals around generalised eigenvalues

In this talk we will present some new ideas about obtaining parametrisable curves around generalised eigenvalues, and address the applications of these results in numerical algorithms and methods.

May 19, 12:00 PM, Room #60
Miloš Stojaković (Novi Sad): Consistent digital line segments

We will introduce a novel and general approach for digitalisation of line segments in the plane that satisfies a set of axioms naturally arising from Euclidean axioms. In particular, we will show how to derive such a system of digital segments from any total order on the integers. As a consequence, using a well-chosen total order, we manage to define a system of digital segments such that all digital segments are, in Hausdorff metric, optimally close to their corresponding Euclidean segments.

This is joint work with Tobias Christ and Dömötor Pálvölgyi.

May 12, 12:00 PM, Room #60
Danka Matić (Novi Sad): Applications of correspondence analysis

Correspondence analysis is a descriptive technique for representing tabular data graphically. It is a generalization of a simple graphical concept — the scatterplot.

Using a few examples we will show how to standardise the frequencies in cross-tabulation table and how to reduce the dimensionality of the points that represent rows and columns in the table. As a special case we will show how to represent these points in the two-dimensional space.

May 5, 12:00 PM, Room #60
Igor Dolinka (Novi Sad): Finite groups are big as semigroups

I will present and discuss a recent proof by N. Ruškuc and myself showing that any finite group with at least three elements occurs as a maximal subsemigroup of a countably infinite semigroup. Finite lattices that are maximal sublattices of infinite lattices were completely classified in 2001 by Freese, Ježek and Nation; the analogous problem in the class of all groups is open and it is closely connected to the Burnside problem (in particular, to the so-called Tarski monster groups). Some generalisations and open problems will be formulated.

The lecture is dedicated to the memory of two recently deceased colleagues: Jaroslav Ježek (Prague) and János Szendrei (Szeged).

April 28, 12:00 PM, Room #60
Maja Nedović (Novi Sad): On eigenvalue bounds of the Schur complement for some diagonally dominant matrices

The theory of the Schur complement plays an important role in many areas, as well as in the theory of H-matrices. In 2005, Jianzhou and Zhang presented a sort of a "'vertical" eigenvalue separation for the Schur complement of a strictly diagonally dominant matrix. Starting from that point, we obtain new bounds for eigenvalues of the Schur complement of some special H-matrices in terms of  the entries of the original matrix instead of those of the Schur complement. Also, we show how an analogous result for a wider class of matrices can be applied in estimating the bounds for eigenvalues of the Schur complement of an SDD matrix.

April 14, 12:00 PM, Room #60
Ljiljana Cvetković (Novi Sad): An open problem in eigenvalue localisation theory

Let π be a partition of the set of indices N = {1,2,...,n} into subsets S₁,S₂,...,S_m. Let χ(π) be the set of all diagonal matrices W which have the following block form: W = [x_kI(k)]_m×m, where x_k are positive numbers and I(k) is the |S_k|×|S_k| identity matrix. A matrix A is said to be an H_π-matrix if there exists a matrix W from χ(π) such that AW is an SDD matrix. A matrix A is said to be an H(m)-matrix if there exists a partition π such that matrix A is an H_π-matrix (m is number of sets S_k ). Obviously, H(1) is the SDD class, and H(2) is our CKV class (set of all matrices for which there exists a subset S such that A is an S-SDD matrix). My conjecture is that for each 1 ≤ m ≤ n, the set of H_π-matrices can be described by the condition that all principal minors of a particular set of matrices should be positive.

April 8, 12:00 PM, Room #60
Marie-Françoise Roy (Rennes): Certificates of positivity

If a polynomial takes only positive values, is it possible to produce a certificate making it obvious?

This problem has a long story with two different approaches.

One approach, by Polya and Bernstein, is to express the polynomial in a convenient basis where the positivity of all the coefficients will imply the positivity of the polynomial. The Bernstein basis, univariate and multivariate, plays a key role there.

Another approach, suggested by Minkowski and Hilbert, is to express the polynomial as a sum of squares: this is the famous 17th Hilbert problem. The proof by Artin that a positive polynomial is always a square of rational functions is beautiful, but provides no construction. In both these approaches there are effectiveness, complexity and computational issues addressed in several recent papers or work in progress.

April 7, 12:00 PM, Room #60
Dragan Mašulović (Novi Sad): Simplicity in homogeneous graphs and digraphs

An interval of a relational structure defined on a set A is a subset I of A whose elements are related to each point in A \ I in the same way; a structure having no nontrivial intervals is called simple. We characterise all simple homogeneous graphs and digraphs in terms of their finite subgraphs. Furthermore, we characterise a broader class of semisimple homogeneous graphs and digraphs, in which every nontrivial interval induces a subgraph with no edges.

This is a joint work with I. Dolinka.

March 31, 12:00 PM, Room #60
Vladimir Kostić (Novi Sad): Link between generalised diagonal dominant matrices and spontaneous synchronisation phenomena

Global synchronisation of oscillators is found abundantly in nature, emerging in fields from physics to medicine and biology; moreover, it is an inherent phenomenon in many social behaviours, as well as an important law in technology and engineering. This talk will consider the famous Kuramoto model widely used and investigated to describe the synchronisation behaviour of a generalised system of interacting oscillators. With a large number of oscillators with different natural frequencies, the Kuramoto model predicts that, if they are allowed to interact strongly enough, the oscillators will all start oscillating at the same rate. The model provides a mathematical basis for studying the conditions under which synchronisation can occur, and, in addition, when is the achieved synchronisation frequency is stable. The main contribution of this talk will be to reveal how generalised diagonal dominant matrices can play an important role in this model.

March 24, 12:00 PM, Room #60
Zagorka Lozanov-Crvenković (Novi Sad): A book review of D. Salsburg's `The Lady Tasting Tea: How Statistics Revolutionized Science in the Twentieth Century' (W.H. Freeman & Co., 2001)

March 17, 12:00 PM, Room #60
Tijana Radivojević (Novi Sad), Miroslav Nikolić (Novi Sad): Possibilities of applications of generalised diagonal dominance

Applications of the Lotka-Voltera equations in modelling the structure of ecosystems and their stability can been analysed by using eigenvalue theory. If the system matrix is strictly diagonally dominant, then the system is stable; however, this is not really necessary. In this presentation we encounter situations where such a structure is damaged, e.g. by climate changes, etc. We examine stability issues using CKV localisation.

March 10, 12:00 PM, Room #60
Robert D. Gray (Lisbon): Maximal subgroups of free idempotent generated semigroups

The set of idempotents of an arbitrary semigroup has the structure of a so called biordered set (or regular biordered set in the case of von Neumann regular semigroups). These structures were studied in detail in work of Nambooripad (1979) and Easdown (1985). There is a notion of a free idempotent generated semigroup on a biordered set, and it was conjectured by McElwee in 2002 that the maximal subgroups of such a semigroup are all free (in fact, this had been conjectured since the early 1980's). The first counterexample to this conjecture was given by Brittenham, Margolis and Meakin (2009), where it was shown that the free abelian group of rank 2 is a maximal subgroup of the free idempotent generated semigroup arising from a certain 72-element semigroup.

In this talk I will present some recent work (joint with Nik Ruškuc) which shows that every group is a maximal subgroup of some free idempotent generated semigroup.

March 3, 12:00 PM, Room #60
Éva Jungábel (Novi Sad): Homomorphism-homogeneity in monounary algebras

A structure (A , f ) consisting of a  non-empty set A equipped with a unary operation (transformation)  f : A → A is called a monounary algebra. Following Cameron and Nešetřil, a (first-order) structure is said to be homomorphism-homogeneous if any homomorphism between its finitely generated substructures extends to an endomorphism of the entire structure. In this talk we supply a complete description of homomorphism-homogeneous monounary algebras.

February 24, 12:00 PM, Room #60
Ljiljana Cvetković (Novi Sad): Eigenvalue localisation refinements for matrices related to positivity

New eigenvalue localisation results and methods for matrices with a constant row or column will be presented, together with the numerical examples that show the efficiency of the proposed methods. Extensions of the results to other classes of matrices will be additionally analysed.

February 17, 12:00 PM, Room #60
First internal meeting of sc:ala members in the spring semester 2011.