MARK KAC SEMINAR

We study the top Lyapunov exponents of random products of positive matrices and obtain an efficient algorithm for its computation. As in the earlier work of Pollicott, the algorithm is based on the Fredholm theory of determinants of trace-class linear operators. In this article we obtain a simpler expression for the approximations which only require calculation of the eigenvalues of finite matrix products and not the eigenvectors. Moreover, we obtain effective bounds on the error term in terms of two explicit constants: a constant which describes how far the set of matrices are from all being column stochastic, and a constant which measures the minimal amount of projective contraction of the positive quadrant under the action of the matrices. This is joint work with Ian Morris.

References:

• Pollicott, Mark. "Maximal Lyapunov exponents for random matrix products." Inventiones mathematicae 181.1 (2010): 209-226.
• Jurga, Natalia, and Ian Morris. "Effective estimates on the top Lyapunov exponent for random matrix products." arXiv preprint arXiv:1901.10944 (2019).

Empirical findings have shown that many real-world networks are scale-free in the sense that there is a high variability in the number of connections of the elements of the networks. Spurred by these empirical findings, models have been proposed for such networks. In this talk, we describe a particular class of random graphs in which edges are present independently but with unequal edge occupation probabilities, that are moderated by appropriate vertex weights. For such models, it is known precisely when there is a giant component, meaning that a positive proportion of the vertices is connected to one another. Empirical studies show that many real-world networks have degree sequences with diverging second moment, where the vertices with largest degrees or `hubs' play a profound role in the network's functionality.

Percolation on networks is one of the simplest models for network functionality. It can be interpreted as describing the effect of random attacks on the network, where edges are removed independently with a fixed probability. Interestingly, networks with diverging second moment degree tend to be robust to such random attacks, in the sense that a giant component remains after percolation for any fixed positive retention probability.

We investigate the critical behavior for two popular models of complex networks with diverging second moments, the configuration model and the generalized random graph. We identify what the critical values are, and how they scale with the graph size. Interestingly, this scaling turns out to be rather different for the configuration model, where hubs share many edges between them, and the generalized random graph, for which hubs are connected by at most one edge. Thus, the single-edge constraint plays a significant role. This clears up part of the confusion in the physics literature.

[This is joint work with Shankar Bhamidi, Souvik Dhara, Johan van Leeuwaarden and Sanchayan Sen.]