Random subcube intersection graphs I: cliques and covering

2013/09/27 by Falgas-Ravry, Victor, Markström, Klas
#05C80 #60C05 #60K35 #Combinatorics (math.CO) #FOS: Mathematics #G.2.2 #G.3 #Probability (math.PR)

paper · doi:10.48550/arxiv.1309.7375

Abstract

We study random subcube intersection graphs, that is, graphs obtained by selecting a random collection of subcubes of a fixed hypercube Q_d to serve as the vertices of the graph, and setting an edge between a pair of subcubes if their intersection is non-empty. Our motivation for considering such graphs is to model `random compatibility' between vertices in a large network. For both of the models considered in this paper, we determine the thresholds for covering the underlying hypercube Q_d and for the appearance of s-cliques. In addition we pose some open problems.

Related

• Random intersection graphs and their applications in security, wireless communication, and social networks
• Hyperbolicity, degeneracy, and expansion of random intersection graphs
• Threshold Functions in Random s-Intersection Graphs
• Large random intersection graphs inside the critical window and triangle counts
• Random intersection graphs with communities