Turan-type problems and probabilistic methods in extremal combinatorics

University Of California-San Diego, La Jolla CA

Investigators

Abstract

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.