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 a number of open problems.
@article{10_37236_5472,
author = {Victor Falgas-Ravry and Klas Markstr\"om},
title = {Random subcube intersection graphs. {I:} {Cliques} and covering},
journal = {The electronic journal of combinatorics},
year = {2016},
volume = {23},
number = {3},
doi = {10.37236/5472},
zbl = {1344.05124},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5472/}
}
TY - JOUR
AU - Victor Falgas-Ravry
AU - Klas Markström
TI - Random subcube intersection graphs. I: Cliques and covering
JO - The electronic journal of combinatorics
PY - 2016
VL - 23
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/5472/
DO - 10.37236/5472
ID - 10_37236_5472
ER -
%0 Journal Article
%A Victor Falgas-Ravry
%A Klas Markström
%T Random subcube intersection graphs. I: Cliques and covering
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/5472/
%R 10.37236/5472
%F 10_37236_5472
Victor Falgas-Ravry; Klas Markström. Random subcube intersection graphs. I: Cliques and covering. The electronic journal of combinatorics, Tome 23 (2016) no. 3. doi: 10.37236/5472
