Premium
On the total variation distance between the binomial random graph and the random intersection graph
Author(s) -
Kim Jeong Han,
Lee Sang June,
Na Joohan
Publication year - 2018
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20750
Subject(s) - combinatorics , mathematics , block graph , intersection graph , discrete mathematics , line graph , random regular graph , random graph , complement graph , interval graph , graph power , graph , 1 planar graph
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 .