Connections in randomly oriented graphs

DOI10.1017/S0963548316000341MaRDI QIDQ3177366zbMATH OpenOpenAlexFDO

Authors Bhargav P. Narayanan

Publication date 24 July 2018

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05)

Abstract: Given an undirected graph $G$, let us randomly orient $G$ by tossing independent (possibly biased) coins, one for each edge of $G$. Writing $aightarrowb$ 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 $mathbbP(sightarrowacapsightarrowb)gemathbbP(sightarrowa)mathbbP(sightarrowb)$ for any three vertices $s$, $a$ and $b$ of $G$.

Recommendations

• Correlation of Paths Between Distinct Vertices in a Randomly Oriented Graph
• Positive association of the oriented percolation cluster in randomly oriented graphs
• A counter-intuitive correlation in a random tournament
• Correlations for paths in random orientations of \(G(n,p)\) and \(G(n,m)\)
• First critical probability for a problem on random orientations in \(G(n,p)\).

Cites work

• scientific article; zbMATH DE number 3198427 (Why is no real title available?)
• A counter-intuitive correlation in a random tournament
• An inequality for the weights of two families of sets, their unions and intersections
• Correlation of Paths Between Distinct Vertices in a Randomly Oriented Graph
• Correlations for paths in random orientations of \(G(n,p)\) and \(G(n,m)\)
• General percolation and random graphs
• Infinite paths in randomly oriented lattices
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(7)

• A counter-intuitive correlation in a random tournament
• Positive association of the oriented percolation cluster in randomly oriented graphs
• First critical probability for a problem on random orientations in \(G(n,p)\).
• scientific article; zbMATH DE number 2091895 (Why is no real title available?)
• Correlations for paths in random orientations of \(G(n,p)\) and \(G(n,m)\)
• When are random graphs connected
• Correlation of Paths Between Distinct Vertices in a Randomly Oriented Graph

This page was built for publication: Connections in randomly oriented graphs

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