An interesting class of results in random graph theory concerns the problem of counting the number W of times a fixed subgraph appears in a random graph. Under suitable conditions, the limit distribution is a Poisson law with suitable mean. Furthermore, upper bounds for the total variation distance between the law of W and the Poisson law can be given. The proofs rely upon the Stein-Chen method, which is a general method to establish Poisson approximations for the sum of weakly dependent indicator random variables, with small occurrence probabilities. The main virtues of the Stein-Chen method is that it gives explicit upper bounds on the total variation distance between the law to be approximated and its limit. In the paper we introduce random graphs with exchangeable hidden colors and prove an asymptotic result on the number of times a fixed graph appears as a subgraph of such a random graph. In particular we give necessary and sufficient conditions for the number of subgraphs isomorphic to a given graph to converge, under a negligibility assumption on the frequencies of colors. We prove that the limiting distribution, when it exists, is a mixture of Poisson laws. Furthermore, we discuss potential applications in Bayesian statistics.
A Poisson Approximation for Coloured Graphs Under Exchangeability
FORTINI, SANDRA
2006
Abstract
An interesting class of results in random graph theory concerns the problem of counting the number W of times a fixed subgraph appears in a random graph. Under suitable conditions, the limit distribution is a Poisson law with suitable mean. Furthermore, upper bounds for the total variation distance between the law of W and the Poisson law can be given. The proofs rely upon the Stein-Chen method, which is a general method to establish Poisson approximations for the sum of weakly dependent indicator random variables, with small occurrence probabilities. The main virtues of the Stein-Chen method is that it gives explicit upper bounds on the total variation distance between the law to be approximated and its limit. In the paper we introduce random graphs with exchangeable hidden colors and prove an asymptotic result on the number of times a fixed graph appears as a subgraph of such a random graph. In particular we give necessary and sufficient conditions for the number of subgraphs isomorphic to a given graph to converge, under a negligibility assumption on the frequencies of colors. We prove that the limiting distribution, when it exists, is a mixture of Poisson laws. Furthermore, we discuss potential applications in Bayesian statistics.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
