Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-18T06:29:43.347Z Has data issue: false hasContentIssue false

Poisson Approximation of the Number of Cliques in Random Intersection Graphs

Published online by Cambridge University Press:  14 July 2016

Katarzyna Rybarczyk*
Affiliation:
Adam Mickiewicz University
Dudley Stark*
Affiliation:
Queen Mary, University of London
*
∗ Postal address: Faculty of Mathematics and Computer Science, Adam Mickiewicz University, ul. Umultowska 87, 61-614 Poznań, Poland.
∗∗ Postal address: School of Mathematical Sciences, Queen Mary, University of London, London E1 4NS, UK. Email address: d.s.stark@qmul.ac.uk
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A random intersection graph G(n, m, p) is defined on a set V of n vertices. There is an auxiliary set W consisting of m objects, and each vertex v ∈ V is assigned a random subset of objects W v ⊆ W such that w ∈ W v with probability p, independently for all v ∈ V and all w ∈ W . Given two vertices v 1, v 2 ∈ V , we set v 1 ∼ v 2 if and only if W v1 ∩ W v2 ≠ ∅. We use Stein's method to obtain an upper bound on the total variation distance between the distribution of the number of h-cliques in G(n, m, p) and a related Poisson distribution for any fixed integer h.

Information

Type
Research Article
Copyright
Copyright © Applied Probability Trust 2010