Sparse Discrete Structures

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

The extremal and probabilistic theory of combinatorial structures impacts several areas of mathematics, including number theory, combinatorics, and logic, as well as other fields such as information theory, coding theory, and theoretical computer science. The study of random structures and randomized algorithms has gained particular importance in recent years since they have proved to be useful tools in dealing with the many large real world networks that have emerged and are being actively investigated. Developing new techniques to study these complex systems is a major task that will likely continue for many years, and the theory of sparse combinatorial structures may form a theoretical foundation for understanding their large scale behavior. Various new methods in this theory will be applied in this project. One direction is to prove analogues of classical theorems in the sparse environment. Another direction is to apply the methods to various enumeration problems. At a high level, most of the problems that will be investigated seek to understand the quantitative relationship between the local and global behavior of a large system. Additionally, the methods are well-applicable in percolation, which is connected to statistical physics. Much of this work will be done with graduate students, and some of the work may be integrated into courses to help bring students into this exciting area of research. One of the most important trends in 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, powerful general transference theorems, which the PI has helped to develop, have been used to attack such questions. Even though these tools have proved useful in resolving several central conjectures, many of their potential applications have not been fully explored. For example, these methods seem to be applicable to many enumeration problems. The investigators will address several problems of this type, and they also expect that this project will lead to new exciting questions and directions. In particular, the investigators will investigate the following related areas: (i) Extremal questions in sparse structures; (ii) Embedding in subgraphs of sparse random and pseudo-random graphs; (iii) Ramsey-Turan questions; (iv) Applications of flag algebras; and (v) Problems in bootstrap percolation.