Extremal and Probabilistic Combinatorics via Regularity and Graph Limits

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

The PI will continue his research in combinatorics and graph theory concentrating on probabilistic and extremal questions. Random structures and processes, while being an important object of study of their own, are also very effective in solving problems of discrete mathematics including those whose statement is purely deterministic. An important area of their successful application is extremal combinatorics where, broadly speaking, one has to maximize or minimize a certain parameter given some combinatorial restrictions. One example of an extremal question is the Turan function, the maximum size of a hypergraph without some fixed forbidden subgraph. This is a fundamental and key question that asks how local restrictions can affect the global structure. Despite decades of active attempts, most Turan-type questions remain wide open, such as the famous tetrahedron conjecture made by Paul Turan back in 1941. During attacks on these difficult problems mathematicians developed a number of useful and general techniques such as, for example, the Regularity Lemma. The more recent concepts of (hyper)graph limits and flag algebras seem to be very powerful tools for studying finite structures and for providing new methods of operating with large discrete objects. The PI will work on a number of combinatorial questions, in particular seeking new ways of applying these techniques. Some promising directions include the Turan function, the stability property, inequalities between subgraph densities (for example, minimizing the number of F-subgraphs in a graph of given order and size), hypergraph jumps, quantitative Ramsey-type questions, and graph embedding problems. Since both graph limits and flag algebras deal with an approximation to the studied problem, one important aspect is to develop methods for obtaining exact results from asymptotic calculations (for example, via the stability approach). Extremal and probabilistic combinatorics impacts not only mathematics but many other areas such as operations research, information theory, codes, complexity and algorithms. Random graphs and processes have been providing successful models for various complex systems (such as the Internet or social networks). Such models can be used, for example, for estimating parameters that are impossible or impractical to be determined directly and for predicting their future behavior. Graph limits (and graph regularity) provide a method of approximating large-scale objects by those of bounded complexity; this approach has already been explored in the context of parameter and property testing in computer science. The PI will research new ways of applying randomness, regularity, and graph limits to combinatorial problems. Theoretical developments in these areas may have significant practical implications.