Objectives:
Theories of dense and sparse graph limits are one of the most important recent tools of discrete mathematics. Their emergence and development have led to many breakthroughs on old problems in extremal graph theory and random graph theory, and especially have linked discrete mathematics to areas such as probability theory, functional analysis or group theory in a profound way. Recognitions related to the development of the field include the 2012 Fulkerson Prize, the 2013 Coxeter-James Prize, and the 2013 David P. Robbins Prize.
The project will study the theories of dense a sparse graph limits as well as the related theory of inhomogeneous random graphs. Specific problems in the area of inhomogeneous random graphs include questions on key graph parameters such as the chromatic number or the independence number. In the theory of sparse graph limits our main goal is to extend our understanding of local-global convergence. A further goal is to create a comprehensive theory of limits of subgraphs of hypercubes.
Programme type: PEOPLE, MARIE CURIE ACTIONS, INTRA-EUROPEAN FELLOWSHIPS (IEF)
Objectives:
The project concerns research on the frontier between discrete mathematics and theoretical computer science. Discrete mathematics is an established mathematical discipline and is playing an increasing role in various fields of mathematics. Many real-life problems can be formulated using the language of discrete mathematics. Deep mathematics is hidden behind practical problems such as devising optimal schedules, or efficient routing of data packets through the internet. These problems also suggest that besides problems typical to pure mathematics (such as existence of a solution) one often seeks their efficient algorithmic counterparts (algorithm design).
The project goals are the following:
To explore constructions of specialized families of expanders, in particular of monotone expanders
To study the applications of dimension expanders (and related) in the area of explicit Ramsey graphs
To study in detail the new concept of partition expanders
To study the combinatorial construction of Mendel and Naor can yield explicit constructions of partition expanders, and to look for applications, especially in derandomization and communication complexity
To understand the role of extractors in theoretical computer science
To understand, extend, and simplify constructions of Ramsey graph of Barak et al
To find a purely combinatorial construction of Ramsey graphs
grants
