License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.30
URN: urn:nbn:de:0030-drops-188556
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18855/
Lengler, Johannes ;
Martinsson, Anders ;
Petrova, Kalina ;
Schnider, Patrick ;
Steiner, Raphael ;
Weber, Simon ;
Welzl, Emo
On Connectivity in Random Graph Models with Limited Dependencies
Abstract
For any positive edge density p, a random graph in the Erdős-Rényi G_{n,p} model is connected with non-zero probability, since all edges are mutually independent. We consider random graph models in which edges that do not share endpoints are independent while incident edges may be dependent and ask: what is the minimum probability ρ(n), such that for any distribution ? (in this model) on graphs with n vertices in which each potential edge has a marginal probability of being present at least ρ(n), a graph drawn from ? is connected with non-zero probability?
As it turns out, the condition "edges that do not share endpoints are independent" needs to be clarified and the answer to the question above is sensitive to the specification. In fact, we formalize this intuitive description into a strict hierarchy of five independence conditions, which we show to have at least three different behaviors for the threshold ρ(n). For each condition, we provide upper and lower bounds for ρ(n). In the strongest condition, the coloring model (which includes, e.g., random geometric graphs), we show that ρ(n) → 2-ϕ ≈ 0.38 for n → ∞, proving a conjecture by Badakhshian, Falgas-Ravry, and Sharifzadeh. This separates the coloring models from the weaker independence conditions we consider, as there we prove that ρ(n) > 0.5-o(n). In stark contrast to the coloring model, for our weakest independence condition - pairwise independence of non-adjacent edges - we show that ρ(n) lies within O(1/n²) of the threshold 1-2/n for completely arbitrary distributions.
BibTeX - Entry
@InProceedings{lengler_et_al:LIPIcs.APPROX/RANDOM.2023.30,
author = {Lengler, Johannes and Martinsson, Anders and Petrova, Kalina and Schnider, Patrick and Steiner, Raphael and Weber, Simon and Welzl, Emo},
title = {{On Connectivity in Random Graph Models with Limited Dependencies}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
pages = {30:1--30:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-296-9},
ISSN = {1868-8969},
year = {2023},
volume = {275},
editor = {Megow, Nicole and Smith, Adam},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18855},
URN = {urn:nbn:de:0030-drops-188556},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.30},
annote = {Keywords: Random Graphs, Independence, Dependency, Connectivity, Threshold, Probabilistic Method}
}
|
Keywords: |
|
Random Graphs, Independence, Dependency, Connectivity, Threshold, Probabilistic Method |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
04.09.2023 |
