The Probabilistic Method in Combinatorics

点击翻译按钮获取中文摘要

This award supports the principal investigator's research on the investigation of the use and applications of the powerful technique known as the probabilistic method, pioneered by Paul Erdos more than sixty years ago. In the last few decades the method has experienced tremendous development, propelled by applications in many areas of science, and in particular in theoretical computer science. The project includes foundational problems in combinatorics where randomization plays a crucial role. Further development of the existing tools as well as invention of new tools and techniques will be used to solve those problems, and to investigate both practical and theoretic applications. Plans to disseminate the new discoveries at major international conferences of experts are included as part of the project.The probabilistic method has become a cornerstone of research in modern combinatorics. This project studies the main open problems and applications, including the Kahn-Kallai conjecture and related problems regarding the threshold behavior of graph properties in random graphs. The aim is to find threshold functions for the appearance of large graphs in a random graph, to prove universality-type results, and to develop general tools for embedding general graphs into arbitrary graphs and digraphs satisfying some given desired pseudorandom properties. Another salient part of the project is the broad topic of packing problems, which concerns partitioning combinatorial objects into members from a specified family of objects. The study of the classical tree-packing conjecture and related problems has led to the development of new embedding techniques which can be useful in different areas and form a central part of the project. The project also considers the broad topic of random sums, which is known as the Littlewood-Offord problem. Motivated by a central problem in the theory of random matrices, resilience-type versions of these question and also working with sums of dependent random variables are considered, with potential impact on error-correcting codes and cryptography.