The objective method: Probabilistic combinatorial optimization and local weak convergence. (English) Zbl 1037.60008

Aldous, David; Steele, J. Michael

Kesten, Harry (ed.), Probability on discrete structures. Berlin: Springer (ISBN 3-540-00845-4/hbk). Encycl. Math. Sci. 110(1), 1-72 (2004).

This survey describes a general approach to a class of problems that arise in combinatorial probability and combinatorial optimization. Formally, the method is part of weak convergence theory, but in concrete problems the method has a flavor of its own. A characteristic element of the method is that it often calls for one to introduce a new, infinite, probabilistic object whose local properties inform us about the limiting properties of a sequence of finite problems.
Section 2 develops the notion of local weak convergence and introduces the “standard construction”, which is a general recipe for building rooted geometric graphs. The theory of the maximum partial matching problem is developed in Section 3. In Section 4 the authors introduce the mean-field model of distance which is a physically motivated probability model designed to gain isight into problems for point processes. The mean-field model leads us to the PWIT, or Poisson weighted infinite tree, which is arguably the most important infinite tree model. The relationship of the PWIT to problems of combinatorial optimization is continued is Section 5. The probability theory of Euclidean combinatorial optimization is presented in Section 6. In Section 7, the last section, the authors summarize some of the circumstances that seem to be needed for the objective method to be successful and develop the background of an attractive conjecture on the independence number of a random regular graph.
This survey also contains new results. In particular, the material in Section 3 on the maximum partial matching problem is new, including the basic limit theorem (Theorem 3.3) and the theorem that determines the limit constants (Theorem 3.4). Another new result is the convergence theorem for minimal spanning trees (Theorem 5.4).
For the entire collection see [Zbl 1025.60001].

Reviewer: Zdzislaw Rychlik (Lublin)

MSC:

60C05	Combinatorial probability
60-02	Research exposition (monographs, survey articles) pertaining to probability theory
60F05	Central limit and other weak theorems
05C35	Extremal problems in graph theory

Keywords:

objective method; local weak convergence; probabilistic combinatorial optimization; geometric random graphs; random tees with random edge weights; Poisson weighted infinite tree