Publication
Ergodic Theory and Dynamical Systems
Paper

Invariant probability measures and dynamics of exponential linear type maps

View publication

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.

Date

Publication

Ergodic Theory and Dynamical Systems

Authors

Topics

Share