Maximum number of symmetric extensions in random graphs (Q6622732)

This paper generalises results on the limiting distribution of the maximum degree of a random graph or co-degree of \(k\)-sets of vertices of a random graph. In this generalisation, symmetric extensions of a given set are considered. These are rooted graphs \((R,H)\) where \(R\) is the set of root vertices with the property that \(R\) can be partitioned into classes and each non-root vertex is either adjacent to no vertex in a class or to all vertices in a class. The authors consider the maximum number of extensions of this type that a set of vertices of the binomial random graph \(G(n,p)\) has. They show that under appropriated scaling the distribution of this random variable converges to a certain distribution. Unlike the case of the maximum degree or the co-degree of \(k\)-sets of vertices, this may not be the Gumbel distribution.