Robustness of properties of random and pseudo-random graphs

Combinatorics is a fundamental area of Mathematics which has found important applications in many of its branches, such as Algebra, Ergodic Theory, Geometry, Number Theory, Probability Theory, Topology and others. It is also highly influential in many other scientific disciplines as well as in the solution of real life problems. The field has experienced explosive growth in recent decades, mainly due to the development of computers and the central role of Combinatorics in Theoretical Computer Science.

The theory of random graphs is an important area of Combinatorics which lies at its interface with Probability Theory. It has numerous applications in Theoretical Computer Science and in the physical, biological and social sciences and its study is key to the development of all of these areas. For example, random graphs are used to model massive real life networks (such as the Internet) and phenomena (such as the spread of an epidemic).

The proposed project explores properties which are satisfied by sparse random graphs in some robust fashion. For example, instead of just requiring a network of computers (modelled by an appropriate graph) to be connected (so that each computer will be able to communicate with all others) we will require that the network remains connected even if some connections become faulty due to malicious attack. In addition to the direct contribution to the development of the theory of random graphs, this line of research continues an exciting new trend in Extremal Combinatorics of transferring fundamental results from the setting of dense graphs to the setting of sparse graphs. It can also potentially lead to general embedding results for sparse pseudo-random graphs. The dense case is well understood via the celebrated Regularity and Blow-up Lemmas, but relatively little is known for the sparse case. Finally, the project also involves the theory of Positional Games and aims to prove game-theoretic analogues of classical results of Extremal Combinatorics.

The proposed project will contribute to the development of Combinatorics, a fundamental discipline with strong connections to other important branches of Mathematics as well as other scientific disciplines. The main focus of the project is on the theory of random and pseudo-random graphs. This is an important field which lies at the intersection of Combinatorics and Probability Theory. It has had an instrumental impact on various scientific disciplines in the last 50 years. These include, in particular, Computer Science, Physics, Biology and Economics. This influence is on theoretical aspects of such fields as well as on practical aspects. The former includes, in particular, Probability Theory, Complexity Theory and Statistical Mechanics, whereas VLSI design and the analysis of massive networks (such as the internet as well as certain biological networks) are examples of the latter. The proposed project thus has the potential to contribute to the development of many important disciplines which, in turn, could lead to developments in industry.

The proposed project will involve the study of resilience of graphs and the existence of factors in graphs, both key concepts in Extremal Combinatorics. It will also study Positional Games on graphs. The theory of positional games has experienced remarkable growth in recent years. This is partly due to its deep connections to many fundamental areas of Mathematics and Theoretical Computer Science, such as Ramsey Theory, Complexity Theory and derandomization. It is a branch of classical Game Theory, an area of Mathematics which has found applications in a variety of fields such as Economics, Management, Operations Research, Political Science, Psychology, Statistics, Biology and many others. This highlights the interdisciplinary nature of the project and its potential for building bridges between several scientific disciplines.

While combinatorial questions are often extremely hard to solve, they are often very easy to communicate to an audience with very limited mathematical background. This makes combinatorics ideal for popularizing mathematics to the general public and encouraging young talented people to engage in mathematical research. Certain aspects of the proposed project (such as the mathematical theory of games and the role of graphs in modelling certain real-life phenomena) are particularly suitable for such outreach activities.