A variant of the Erdos-Renyi random graph process

We consider a natural variant of the Erdős-Rényi random graph process in which \(k\) vertices are special and are never put into the same connected component. The model is natural and interesting on its own, but is actually inspired by the combinatorial data fusion problem that itself is connected t...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2018-06
Main Authors: Logan, Adam, Molloy, Mike, Pralat, Pawel
Format: Article
Language:English
Subjects:
Apexes
Combinatorial analysis
Data integration
Graph theory
Multisensor fusion
Phase transitions
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider a natural variant of the Erdős-Rényi random graph process in which \(k\) vertices are special and are never put into the same connected component. The model is natural and interesting on its own, but is actually inspired by the combinatorial data fusion problem that itself is connected to a number of important problems in graph theory. We will show that a phase transition occurs when the number of special vertices is roughly \(n^{1/3}\), where \(n\) is the number of vertices.
ISSN:2331-8422