The project will explore seven explicit conjectures in three broad areas of probabilistic analysis of algorithms, empirical processes and random graphs. Several connections between these apparently different areas will be clarified and used in the solutions of the conjectures. Karp's probabilistic polynomial time algorithm for the traveling salesman problem, leads to considerations of random graphs with special properties. Thus the central limit theorem and the large deviation theory of the traveling salesman problem have connections with quantities of interest in the random graph theory such as minimal spanning trees, and minimal matchings. Some of the new techniques used include the theory of Sobolov inequalities and the Efron-Stein inequality. Theory of random trees is developed by putting specific probability distributions on the trees with n vertices. It will be shown that the use of Harper's method leads to a richer theory of random trees. Harper's method in turn leads to connections with the empirical process of lines. The novelty of the research is its problem-driven approach and the elucidation and exploitation of the interconnections of seemingly divergent fields.
