The Probabilistic Method

点击翻译按钮获取中文摘要

9970822The investigator will continue his study of The Probabilistic Method, a legacy of the late Paul Erdos that remains in a very active stage. The original, and still basic, applications are to discrete mathematics when one wishes to prove the existence of an object having certain properties. Very roughly, a random object is appropriately defined and it is shown that the random object has the desired properties with positive probability. The methodology strongly intersects with the use of randomness in Theoretical Computer Science, the interaction going both ways. If a random algorithm can be proven to have positive chance of success then the existence of a success is guaranteed. Further, the output of random algorithms is very much of interest for its own sake. As the random object evolves there are certain critical regions, dubbed threshold functions, where the probability of events move rapidly from near zero to near one. Using methods from mathematical logic the investigator attempts to describe the possible threshold functions for all events expressible in a given logical language.Randomness is now recognized to play an important role in many computer algorithms. The investigators particularly study packing algorithms. How can a set of partially overlapping requests - for bandwidth, takeoff slots or whatever - be handled to satisfy the maximal number of requests? With the random greedy algorithm the requests are taken in randomly shuffled order and then each is approved if not conflicting with previous approvals. Oftimes this natural and easily implemented algorithm can be shown to give near optimal results though analysis of it has proved to be particularly subtle. A second, though related, area is in percolation effects. Large systems are (often) nonlinear - they undergo a phase transition (liquid to gas, low crime to high crime) which is qualitative as well as quantitative in a surprisingly short period of time. With the appropriate scaling the investigator shall spread out this transition so as better to understand the phenomenon.