Random and pseudorandom structures and their applications

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

The study of randomly constructed objects, such as random graphs, had immense impact on discrete mathematics and related fields over the past fifty years. For example, the tools developed to solve open problems in the theory, now famously named the probabilistic method, provided a new way of thinking and serves as a link between combinatorics, analysis, number theory and geometry. Also, the random objects themselves found applications in fields such as theoretical computer science and statistical physics. As an instance, they are utilized as a theoretical framework for studying massive networks (e.g., internet, social networks, and neural networks) which are becoming of growing importance. Yet despite the great amount of work devoted to this topic over the past fifty years, many interesting unresolved questions, especially regarding the global structure of random graphs, still remain to be answered. Furthermore, the successful development of the theory of random graphs served as a natural motivation for the study of pseudorandom graphs, which can be informally described as deterministic graphs that behave like truely random graphs. Problems in the theory of pseudorandom graphs often are motivated by practical problems and are connected to deep philosophical questions such as, "Can we imitate true randomness?".In this project, the PI plans to study open problems in the field of random and pseudorandom graphs to further develop the theory and deepen the understanding of these fasicnating objects. The main problems that the PI plans to focus on are the conjectures of Krivelevich and Sudakov on Hamiltonicity of pseudorandom graphs, and of Kahn and Kalai on the threshold of appearance of fixed spanning subgraphs in binomial random graphs. These problems were chosen because they are representative problems that address the challenges that we are currently facing in understanding the global properties of random and pseudorandom graphs. The PI also plans to study related problems in combinatorics such as Sidorenko's conjecture, explicit construction of Ramsey graphs, and Turan-type problems in hypercubes.