Sparse random and pseudorandom graphs and graph Ramsey theory

• Applicant: Professor Dr. Yury Person
• Subject Area: Mathematics
• Term: from 2014 to 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 263484357

Sparse random and pseudorandom graphs, and graph Ramsey theory as well are nowadays among the most important and influential topics investigated in extremal and probabilistic combinatorics, which have diverse connections to other areas of mathematics such as geometry, algebra and number theory and to theoretical computer science. The basic objects of study are graphs which are versatile models both for real life applications and for theoretical study. A typical problem concerning random graphs is what properties a graph sampled at random according to some probability distribution will possess? Pseudorandomness is a concept which tries to capture such properties in a deterministic way, which should make it more applicable to practical studies. Ramsey theory is a fascinating area whose main leitmotiv is a phenomenon observed throughout many branches of mathematics that every large enough structure must exhibit certain patterns, or put it in words of Theodore Motzkin: ``Complete disorder is impossible''. All topics have in common, that it often suffices to provide an algorithm or an embedding strategy which finds a smaller desired structure within some large structure. Our goal is to further explore these important topics by studying conditions under which one can find various spanning structures in random and pseudorandom graphs, and by investigating open problems of graph Ramsey theory.

• DFG Programme: Research Grants