On the Edge-Density of the Brownian Co-Graphon and Common Ancestors of Pairs in the CRT

Bassino et al. have shown that uniform random co-graphs (graphs without induced (Formula presented.)) of size (Formula presented.) converge to a certain non-deterministic graphon. The edge density of this graphon is a random variable (Formula presented.) whose first moments have been computed by these authors. The first purpose of this note is to observe that, in fact, these moments can be computed by a simple recurrence relation. The problem leads us to the following question of independent interest: given (Formula presented.) i.i.d. uniform pairs of points (Formula presented.) (Formula presented.), (Formula presented.) in the Brownian CRT, what is the size (Formula presented.) of the set (Formula presented.) formed by their pairwise last common ancestors? We show that (Formula presented.) in probability, with (Formula presented.). The method to establish the recurrence relation is reminiscent of Janson's computation of moments of the Wiener index of (large) random trees. The logarithm factor in the convergence result comes from the estimation of Riemann sums in which summands are weighted by the integer divisor function—such sums naturally occur in the problem. We have not been able to analyze the asymptotics of moments of (Formula presented.) directly from the recurrence relation, and in fact our study of (Formula presented.) is independent from it. Several things remain to be done; in particular, we only scratch the question of large deviations of (Formula presented.), and the precise asymptotics of moments of (Formula presented.) is left open.