Projects

We study the polynomial-time approximability of NP-hard combinatorial optimization problems. In this area, most of our recent results deal with vertex partitions of graphs, under local constraints that prescribe lower bounds on the number of neighbors of each vertex in its class.

Partner institution: LAMSADE, Université Paris-Dauphine (http://www.lamsade.dauphine.fr/)

National Office for Research and Technology (IKTA-00064/2003)
[ OMFB-00495/2004 ]

The MOBILE INNOVATION CENTRE (MIK) was founded as a result of the call for proposals „The Establishment of R&D and Innovation Centre for Mobile Communication” supported by the National Office for Research and Technology. The Centre is based on the cooperation of universities, an academic research institution, industrial companies, suppliers and organisations dealing with scientific research and innovation, including the representatives of profit-oriented and non-profit sectors.

We plan to continue our research in the area of extremal discrete mathematics. The central question of this field has the following form: determine the maximum (or minimum) size of a discrete mathematical object that satisfies a certain condition. It turns out that this general topic has connections to very diverse fields (geometry, design theory, number theory, algebra, topology, etc.) and to areas with important concrete applications in everyday life (computer science, coding theory, cryptography, optimization and scheduling problems, communication and networking problems, etc.).

The gradual deployment of broadband networks throughout the research community and the fact that network capacity grows with much greater rate than CPU power and storage capacity (Moore's Law vs. storage improvements vs. optical improvements) have led to the creation of a distributing environment for sharing resources known as the Grid paradigm. This integrated networking & middleware environment is also called eInfrastructure.

The eLearning project of NIIF ( National Information Infrastructure Development Program ) was initiated with the objective of promoting the wide scale utilisation of eLearning technologies in the education institutions of NIIF using the excellent network infrastructure of NIIF.

The Regularity Lemma turned out to be one of the most powerful tools in solving Ramsey type, covering, and partitioning problems in graph and hypergraph theory. Recent results of the team lead by V. Rödl shows that finally a very useful (but complicated) hypergraph version of the Regularity Lemma is also obtained. In the last year we already managed to solve a couple of longstandig open problems using the Regularity Lemma-Blow-up Lemma method. For example we determined the exact value of the Ramsey numbers of paths in case of three colors, which solved a conjecture of Faudree and Schelp.