This proposal concerns research in extremal and probabilistic combinatorics. Broadly speaking, extremal combinatorics addresses the existence of and theoretical bounds on the sizes of combinatorial objects with certain local restrictions imposed. Many of the important problems, while simple to state and attractive, are often representative of more general phenomena in mathematics, and lead to many unexpected and useful applications in other areas. For example, the topics of expander graphs and Ramanujan graphs have had a major impact on coding, complexity and information theory. These problems also lead to new theoretical methods, perhaps the most remarkable instance of which is the probabilistic method pioneered by the renowned mathematician Paul Erdos. Extremal combinatorial methods lead to the construction of new and more efficient codes for correcting errors in data transmission, the reduction of the number of bits required for Monte-Carlo algorithms, such as randomized algorithms for primality testing. In fact, the spectacular recent breakthrough of a deterministic algorithm for primality testing is highly connected to preceding randomized algorithms which were long known to exist. In my proposal I plan to study further theoretical and practical applications, including the problem of time-complexity of matrix multiplication, quadratic sieve-type integer factoring algorithms, and questions in other areas of mathematics. In mathematics, this work has implications in functional analysis, projective geometry, spectral graph theory, coding theory, and algorithms. While these open problems are important and clearly difficult, some major inroads are possible by combining probabilistic and combinatorial techniques with some new ideas.
Combinatorial mathematics lies at the heart of many modern-day operations, such as digital security, web searching, and reliable data transmission. Examples include multiplication of large arrays of numbers for qualitative web searches -- these matrices tend to have billions of rows and columns; the RSA cryptosystem, which underpins much of modern digital security, and is based strongly on the belief that factoring integers is difficult; finally, transmission of data over noisy or unreliable channels is at the core of coding theory, where one attempts to design novel ways of encoding a message so that even if the message is perturbed in transmission, the receiver can still figure out with high probability what the original message was. One of the major ingredients for constructing such good error-correcting codes is the existence of combinatorial objects known as expander graphs. Using explicit constructions and variants of these objects, together with basic probabilistic arguments, one can compress a message in an optimal way such that the receiver has an excellent chance of figuring out what the original message was. Constructions of graphs with such extremal properties is fundamental to the proposed research. In addition, the researcher plans to use combinatorial and probabilistic techniques to approach the problems of matrix multiplication and integer factoring, both of which are central to the concrete examples listed above. The researcher plans to investigate both the practical and theoretical applications of the above-mentioned combinatorial and probabilistic methods.
The PI conducts research in extremal and probabilistic combinatorics. Broadly speaking, extremal combinatorics addresses the existence and theoretical bounds on the sizes of combinatorial objects with certain local restrictions imposed. This area of mathematics is part of fundamental research in mathematics, but also leads to many unexpected and useful applications in other areas of science, such as theoretical computer science. This area has also lead to new theoretical mathematical techniques, perhaps the most remarkable instance of which is the probabilistic method pioneered by P. Erdos. This method now pervades broad areas of mathematics. The author has published over thirty papers in internationally renowned journals, and delivered over twenty invited lectures at conferences for leading researchers in the field. He is currently an advisor for PhD students in combinatorics and graph theory at the University of California, San Diego. Perhaps the most popular combinatorial object is the graph. This is an object consisting of vertices and links or edges between the vertices, and has been used to model a number of real-world networks as well as random processes. Notable examples include the world-wide web graph, and the field of random graphs, where links occur according to some probability distribution. The web and many other objects, such as social networks, can be modeled as such a mathematical object to determine large scale phenomena, such as the famous concept of "six degrees of separation" and topological properties of the large-scale network. In their seminal paper, Erdos and Renyi discovered a number of fascinating phenomena concerning random graphs, for example, there is a critical density of edges at which the random graph has a large connected component with high probability. The author has studied together with experts in the area various other so-called threshold phenomena for random graphs, such as the appearance of a subgraph where all vertices are linked to the same number of other vertices (called a k-regular subgraph). The authors come close to determining the threshold for this property, and it has recently been shown empirically by physicists where the threshold should be. Even more recently, the threshold was shown to be sharp. The growth of the study of random graphs is explosive and central in modern combinatorics and statistical physics. The author is also interested in studying properties of graphs which behave like random graphs – these are called pseudorandom graphs – and have strong links to applications in coding theory, cryptography and theoretical computer science. One of the fundamental "extremal problems" is to construct on n points a graph with as many edges as possible and no cycles of prescribed length. With a number of coauthors the author has studied this problem from many angles, and has the strongest results on a number of open conjectures. The constructed objects tend to have beautiful properties – in addition to pseudorandomness – and are very interesting also from a mathematical point of view, for instance, the densest graph on 30 vertices without any hexagons alongside. The author has connected the problem to various other areas in number theory and computational complexity. This area requires both combinatorial but also subtle probabilistic and algebraic arguments to make progress. With modern combinatorial tools, we now have a much better understanding of the difficulty of these extremal problems, and their importance in both mathematics and in applications. Nevertheless, many central problems remain open and their solution is likely to lead to exciting new developments in both mathematics and the related applied sciences.
