Groupies in multitype random graphs

A vertex in a graph G is said to be a groupie if its degree is not less than the average degree of its neighbors. Various properties
of groupies have been investigated in deterministic graph theory (Ajtai et al. 1980]; Bertram et al. 1994]; Ho 2007]; Mackey 1996]; Poljak et al. 1995]). For example, it was proved in Mackey (1996]) that there are at least two groupies in any simple graphs with at least two vertices.
Groupies were even found to be related to Ramsey numbers (Ajtai et al. 1980]). More recently, Fernandez de la Vega and Tuza (2009]) showed that, in Erd?s-Rényi random graphs G(n, p), the proportion of vertices that are groupies is almost always very near to 1/2
as . Later the author Shang (2010]) obtained a result of similar flavor in random bipartite graphs . It was shown that the proportion of groupies in each partite set is almost always
very close to 1/2 if is balanced, namely, .

In this paper, we consider groupies in a more general random graph model, which we
call multitype random graphs. Let q be a positive integer. Denote . Define the ‘gene’ for a multitype random graph as a weighted complete graph (having a loop at each vertex) on the vertex set [q], with a weight associated to each vertex, and a weight associate to each edge ij. Note that since we deal with undirected graphs. We assume . The multitype random graph with gene is generated as follows. Let n be much larger than q, and let [n] be its vertex set. We partition [n] into q sets by putting vertex v in with probability independently. Each pair of vertices and are connected with probability independently (all the decisions on vertices and edges are made independently).

For , let represent the number of the groupies in . Thus, is the number of groupies in the multitype random graph . Denote by and . For generality, we will usually think of and as functions of n in the same spirit of random graph theory (Bollobás 2001]; Janson et al. 2000]). Let be the all-one vector. All the asymptotic notations used in the paper such as O, o, and are standard, see e.g. Janson et al. (2000]). Our first result is as follows.

Theorem 1

Let. Assume that, whereis a constant. Iffor some constant, and, then

as, whereis any function tending to infinity. Hence,

as, whereis any function tending to infinity.

When and are independent of n, the following corollary is immediate.

Corollary 1

Let. Assume thatfor, andfor all i. Then

as, whereis any function tending to infinity.

Clearly, by taking , , and , we recover the result in Shang (2010], Thm. 1) for balanced random bipartite graphs.

Theorem 1 requires that the edges between sets , are dense, namely, the multitype random graph in question resembles a dense ‘multipartite’ graph. For sparse random graphs on the
other hand, we have the following result.

Theorem 2

Let. Assume that, whereis a function of n. Iffor some constant, , and, then

as, whereis any function tending to zero. Hence,

as, whereis any function tending to zero.

It follows from Theorem 2 that we may reproduce the result for sparse Erd?s-Rényi
random graphs Fernandez de la Vega and Tuza (2009], Thm. 2) by taking , ; and the result for sparse balanced random bipartite graphs Shang (2010], Thm. 2) by taking , , and .

The multitype random graph is generated through a double random process. In the following, we will also consider
a closely related ‘random-free’ model . Given a gene defined as above, the random-free multitype random graph (a.k.a. stochastic block model Holland et al. 1983]) is constructed by partitioning [n] into q sets with . Recall that . We draw an edge vu with probability independently for and ; thus the first random step in the original construction disappears, which explains
the name ‘random-free’.

In “Proof of the main results” section, we will show Theorems 1 and 2 by first proving
analogous results for the random-free version . To illustrate our theoretical results, a numerical example is presented in “Numerical
simulations” section.