Random subcube intersection graphs. I: Cliques and covering

zbMATH Open1344.05124arXiv1309.7375MaRDI QIDQ311574FDOQ311574

Authors: Victor Falgas-Ravry, Klas Markström 

Publication date: 13 September 2016

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1309.7375

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• scientific article; zbMATH DE number 3954974
• On Random Intersection Graphs: The Subgraph Problem
• scientific article; zbMATH DE number 3889585
• Subcube Coverings of Random Spanning Subgraphs of then-Cube
• Turán and Ramsey properties of subcube intersection graphs

zbMATH Keywords

random graphslarge networkrandom intersection graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• The phase transition in inhomogeneous random graphs
• Topics in Intersection Graph Theory
• On Random Intersection Graphs: The Subgraph Problem
• Quasi-random graphs
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Connectivity of the uniform random intersection graph
• Random interval graphs
• Interval graph limits
• Diameter, connectivity, and phase transition of the uniform random intersection graph
• Threshold limits for cover times
• On Hamiltonicity of uniform random intersection graphs
• Proof of the satisfiability conjecture for large \(k\)
• Sparse random graphs with clustering
• Voting in agreeable societies
• Equivalence of a random intersection graph and G (n ,p )
• Colouring Non-sparse Random Intersection Graphs
• The Double Dixie Cup Problem
• Title not available (Why is that?)
• The Evolution of Random Subgraphs of the Cube
• Biclique covers and partitions
• Sharp thresholds of graph properties, and the $k$-sat problem
• Random interval graphs
• The vertex degree distribution of random intersection graphs
• On the connectivity of a random interval graph
• Turán and Ramsey properties of subcube intersection graphs
• Poisson approximation of the number of cliques in random intersection graphs
• Random intersection graphs whenm=?(n): An equivalence theorem relating the evolution of theG(n,m,p) andG(n,p) models
• Coloring Random Intersection Graphs and Complex Networks
• Component evolution in a secure wireless sensor network
• The asymptotic \(k\)-SAT threshold
• Large cliques in sparse random intersection graphs
• Automata, Languages and Programming
• Random subgraphs of finite graphs. III: The phase transition for the \(n\)-cube
• Component evolution in random intersection graphs
• The phase transition in site percolation on pseudo-random graphs
• An evolution of interval graphs
• Large independent sets in general random intersection graphs
• The structure of strategy-proof social choice. I: General characterization and possibility results on median spaces

Cited In (3)

• Analysis of greedy algorithm for vertex covering of random graph by cubes
• On Random Intersection Graphs: The Subgraph Problem
• Turán and Ramsey properties of subcube intersection graphs

This page was built for publication: Random subcube intersection graphs. I: Cliques and covering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q311574)