On the total variation distance between the binomial random graph and the random intersection graph. Issue 4 (4th January 2018)

• Record Type: Journal Article
• Authors: Kim, Jeong Han; Lee, Sang June; Na, Joohan
• Is Part Of: Random structures & algorithms. Volume 52:Issue 4(2018)
• Page Start: 662
• Page End: 679
• Publication Date: 2018-01-04
• Subjects: Intersection graph -- random intersection graph -- binomial random graph -- total variation distance; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20750
• Languages: English
• ISSNs: 1042-9832

Abstract

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 .