Sparse random graphs with clustering

In 2007, we introduced a general model of sparse random graphs with (conditional) independence between the edges. The aim of this article is to present an extension of this model in which the edges are far from independent, and to prove several results about this extension. The basic idea is to construct the random graph by adding not only edges but also other small graphs. In other words, we first construct an inhomogeneous random hypergraph with (conditionally) independent hyperedges, and then replace each hyperedge by a (perhaps complete) graph. Although flexible enough to produce graphs with significant dependence between edges, this model is nonetheless mathematically tractable. Indeed, we find the critical point where a giant component emerges in full generality, in terms of the norm of a certain integral operator, and relate the size of the giant component to the survival probability of a certain (non‐Poisson) multi‐type branching process. While our main focus is the phase transition, we also study the degree distribution and the numbers of small subgraphs. We illustrate the model with a simple special case that produces graphs with power‐law degree sequences with a wide range of degree exponents and clustering coefficients. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 269–323, 2011     

Competing first passage percolation on random graphs with finite variance degrees

We study the growth of two competing infection types on graphs generated by the configuration model with a given degree sequence. Starting from two vertices chosen uniformly at random, the infection types spread via the edges in the graph in that an uninfected vertex becomes type 1 (2) infected at rate λ₁ (λ₂) times the number of nearest neighbors of type 1 (2). Assuming (essentially) that the degree of a randomly chosen vertex has finite second moment, we show that if λ₁ = λ₂, then the fraction of vertices that are ultimately infected by type 1 converges to a continuous random variable V ∈ (0,1), as the number of vertices tends to infinity. Both infection types hence occupy a positive (random) fraction of the vertices. If λ₁ ≠ λ₂, on the other hand, then the type with the larger intensity occupies all but a vanishing fraction of the vertices. Our results apply also to a uniformly chosen simple graph with the given degree sequence.     

Proportional graphs

Let S be a finite set of graphs and t a real number, 0 < t < 1. A (deterministic) graph G is (t, 5)-proportional if for every H ∈ S, the number of induced subgraphs of G isomorphic to H equals the expected number of induced copies of H in the random graph G_{n, t} where n = |V(G)|. Let S_k = {all graphs on k vertices}, in particular S₃ = {K₃, P₂, K₂K_t, D₃}. The notion of proportional graphs stems from the study of random graphs (Barbour, Karoński, and Ruciński, J Combinat. Th. Ser. B, 47 , 125-145, 1989; Janson and Nowicki, Prob. Th. Rel. Fields, to appear, Janson, Random Struct. Alg., 1 , 15-37, 1990) where it is shown that (t, S₃)-proportional graphs play a very special role; we thus call them simply t-proportional. However, only a few ½-proportional graphs on 8 vertices were known and it was an open problem whether there are any f-proportional graphs with t ≠ ½ at all. In this paper, we show that there are infinitely many ½-proportional graphs and that there are t-proportional graphs with t≠. Both results are proved constructively. [We are not able to provide the latter construction for all f∈ Q∩(0,1), but the set of ts for which our construction works is dense in (0,1).] To support a conviction that the existence of (t, S₃)-proportional graphs was not quite obvious, we show that there are no (t, S₄)-proportional graphs.     

The Wiener Index of simply generated random trees

Asymptotics are obtained for the mean, variance, and higher moments as well as for the distribution of the Wiener index of a random tree from a simply generated family (or, equivalently, a critical Galton–Watson tree). We also establish a joint asymptotic distribution of the Wiener index and the internal path length, as well as asymptotics for the covariance and other mixed moments. The limit laws are described using functionals of a Brownian excursion. The methods include both Aldous' theory of the continuum random tree and analysis of generating functions. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 22: 337–358, 2003     

Self-Couplings and the concentration function

The concentration function of a random variable may be estimated using couplings of the variable with itself.Supported by the Göran Gustafsson Foundation for Research in Natural Sciences and Medicine.     

Multiple excitations in the core photoelectron spectrum of acetylene

A high-resolution core photoelectron spectrum of free acetylene is presented. Configuration interaction and complete active space SCF calculations were carried out for assignment and prediction of energies and intensities in the spectrum. The shake-up structure is found to be strongly dominated by intervalence π_g to π_g transitions for which multiple 2-, 3- and 4-fold excitations are important.