On the total variation distance between the binomial random graph and the random intersection graph. Issue 4 (4th January 2018) - Kim, Jeong Han; Lee, Sang June; Na, Joohan
Abstract: When each vertex is assigned a set, the intersection graph generated by the sets is the graph in which two distinct vertices are joined by an edge if and only if their assigned sets have a nonempty intersection. An interval graph is an intersection graph generated by intervals in the real line. A chordal graph can be considered as an intersection graph generated by subtrees of a tree. In 1999, Karoński, Scheinerman, and Singer‐Cohen introduced a random intersection graph by taking randomly assigned sets. The random intersection graph G ( n, m ; p ) has n vertices and sets assigned to the vertices are chosen to be i.i.d. random subsets of a fixed set M of size m where each element of M belongs to each random subset with probability p, independently of all other elements in M . In 2000, Fill, Scheinerman, and Singer‐Cohen showed that the total variation distance between the random graph G ( n, m ; p ) and the Erdös‐Rényi graph G ( n, p ̂ ) tends to 0 for any 0 ≤ p = p ( n ) ≤ 1 if m = n α, α > 6, where p ̂ is chosen so that the expected numbers of edges in the two graphs are the same. In this paper, it is proved that the total variation distance still tends to 0 for any 0 ≤ p = p ( n ) ≤ 1 whenever m ≫ n 4 .