Global and Local Properties of Discrete Structures

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

The theory of combinatorial structures is closely related to several areas of mathematics, including algebra, logic, number theory, and probability, as well as to other fields such as information theory, coding theory, theoretical computer science, and statistical physics. Investigating random and pseudo-random structures has become an important research topic, particularly because the results and the techniques developed proved to be useful in the study of large networks in important applications. A recently-discovered connection between sparse combinatorial structures and enumeration problems yielded several deep results that call for further study. This research project focuses on understanding the robustness of important properties of dense structures and testing whether they are inherited by random sparse substructures, with the goal of developing a unified theory. The project will involve training of graduate students through involvement in the research, and it is anticipated that some of the results will be integrated into courses for graduate student training. A central focus of combinatorics over the past twenty years has been the introduction and proof of various random analogues of well-known theorems in extremal graph theory, Ramsey theory, and additive combinatorics. Recently, the so-called container method was developed, which proved to be useful to attack these questions and many others. One direction of research in this project will focus on applications of the method, and it is expected that this exploration will lead to new exciting questions and directions. In particular, the following related areas are to be investigated: (1) extremal questions in sparse structures; (2) embedding in subgraphs of sparse random and pseudo-random graphs; (3) applications of flag algebras; and (4) problems in bootstrap percolation. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.