Invariant probability measures and dynamics of exponential linear type maps

Abstract

We consider the problem of the asymptotic size of the random maximum-weight matching of a sparse random graph, which we translate into dynamics of the operator in the space of distribution functions. A tight condition for the uniqueness of the globally attracting fixed point is provided, which extends the result of Karp and Sipser [Maximum matchings in sparse random graphs. 22nd Ann. Symp. on Foundations of Computer Science (Nashville, TN, 2830 October, 1981). IEEE, New York, 1981, pp. 364375] from deterministic weight distributions (Dirac measures ) to general ones. Given a probability measure which corresponds to the weight distribution of a link of a random graph, we form a positive linear operator (convolution) on distribution functions and then analyze a family of its exponents, with parameter , which corresponds to the connectivity of a sparse random graph. The operator relates the distribution F on the subtrees to the distribution F on the node of the tree by F=exp (F). We prove that for every probability measure and every <e, there exists a unique globally attracting fixed point of the operator; the probability measure corresponding to this fixed point can then be used to compute the expected maximum-weight matching on a sparse random graph. This result is called the e-cutoff phenomenon. For deterministic distributions and >e, there is no fixed point attractor. We further establish that the uniqueness of the invariant measure of the underlying operator is not a monotone property of the average connectivity; this parallels similar non-monotonicity results in the statistical physics context. © 2008 Cambridge University Press.