In this proposal, the PI addresses some of the deepest and most important issues in probabilistic combinatorics, including sharp concentration inequalities and the semi-random method. The PI and his collaborators plan to develop new sharp concentration inequalities and apply them, together with the powerful semi-random (Rodl nibble) method to attack several well-known and long standing conjectures in combinatorics. Among others, the PI will study a series of minimax problems in finite geometry, raised in the fifties. Another topic is the study of geometrical properties of random objects. Here is a typical question: how many points does one need to pierce n random d-dimensional boxes, where a random box is obtained as the Cartesian product of d random subintervals of the unit interval ? The PI also plans to use methods from probabilistic combinatorics to attack problems arose from very practical fields such as coding theory and the study of "real-world" graphs. For educational purposes, he intends to write a textbook on sharp concentration inequalities and its applications in combinatorics and theoretical computer science. He also plans to design and teach a graduate course at UCSD on the probabilistic methods.
In the last twenty years, probability has become one of the most powerful weapons in discrete mathematics and computer science. The first main reason is that randomness helps us to overcome algorithmic and existence problems which cannot be solved deterministic means. The second main reason is that many important real-life objects (such as the internet) can be modeled by a random process. On the other hand, in many situations, the problems are so complex that traditional results from probability theory cannot be applied. The PI plans to develop new probabilistic tools which would have a break-thought impact on many such problems, some of them have been open for decades. Among others, these new tools would help us to design very efficient randomized algorithms, to prove the existence of interesting objects, and to analyze complicated processes. For educational purposes, the PI intends to write a textbook on discrete probability and its applications in discrete mathematics and theoretical computer science.
