Article contents
Connections in Randomly Oriented Graphs
Published online by Cambridge University Press: 06 December 2016
Abstract
Given an undirected graph G, let us randomly orient G by tossing independent (possibly biased) coins, one for each edge of G. Writing a → b for the event that there exists a directed path from a vertex a to a vertex b in such a random orientation, we prove that for any three vertices s, a and b of G, we have ℙ(s → a ∩ s → b) ⩾ ℙ(s → a) ℙ(s → b).
Keywords
- Type
- Paper
- Information
- Combinatorics, Probability and Computing , Volume 27 , Special Issue 4: Special Issue: Oberwolfach Workshop , July 2018 , pp. 667 - 671
- Copyright
- Copyright © Cambridge University Press 2016
References
- 1
- Cited by