Monochromatic Subgraphs in Randomly Colored Dense Multiplex Networks

Abstract

Given a sequence of graphs $G_n$ and a fixed graph $H$, denote by $T(H,G_n)$ the number of monochromatic copies of the graph $H$ in a uniformly random $c$-coloring of the vertices of $G_n$. In this paper we study the joint distribution of a finite collection of monochromatic graph counts in networks with multiple layers (multiplex networks). Specifically, given a finite collection of graphs $H_1,H_2,\dots ,H_d$ we derive the joint distribution of $(T(H_1,G_n^{(1)}),T(H_2,G_n^{(2)}),\dots ,T(H_d,G_n^{(d)}))$, where ${\mathbf{G}}_n=(G_n^{(1)},G_n^{(2)},\dots ,G_n^{(d)})$ is a collection of dense graphs on the same vertex set converging in the joint cut-metric. The limiting distribution is the sum of 2 independent components: a multivariate Gaussian and a sum of independent bivariate stochastic integrals. This extends previous results on the marginal convergence of monochromatic subgraphs in a sequence of graphs to the joint convergence of a finite collection of monochromatic subgraphs in a sequence of multiplex networks. Several applications and examples are discussed.

31 pages, 3 figures