This proposal concentrates on two areas of research: the extremal theory of graphs and hypergraphs, and the theory of discrete random structures. Both belong to the main stream of contemporary discrete mathematics and enjoy a broad range of applications in mathematics and computer science. Extremal theory of graphs and hypergraphs is at the frontier of combinatorics, demanding more and more sophisticated proof techniques. Some of the notoriously difficult problems have remained open for more than 50 years, stimulating steady progress of research. Randomness continues to play a fundamental role in demonstrating the existence of combinatorial structures with desired properties, in modeling real life large networks, as well as in the design of efficient algorithms. The aim of the proposed research is to get a better understanding of some phenomena occurring in both these areas, and how they interact. Our specific goals are to study to what extent the minimum degree in graphs and hypergraphs determines their structure and to transfer classical results, of extremal and Ramsey type, to sparse random environments.
The project, owing to its international character, will serve as a means of further development of collaboration between the best researchers from various parts of the world. The investigators will work towards popularizing the results of their research by publishing in high-quality journals and presenting addresses at prestigious international conferences. Having access to students, both graduate and undergraduate, they will be in a position to disseminate their achievements also at these levels of academic education. In particular, the problems described in this proposal will be a good source of doctoral research topics for current and future students.
