Correlations for paths in random orientations of G(n,p) and G(n,m)

DOI10.1002/RSA.20358zbMATH Open1238.05239arXiv0906.0720OpenAlexW2019853612MaRDI QIDQ5388971FDOQ5388971

Authors: Sven Erick Alm, Svante Janson, Svante Linusson 

Publication date: 24 April 2012

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: We study random graphs, both $G(n,p)$ and $G(n,m)$, with random orientations on the edges. For three fixed distinct vertices s,a,b we study the correlation, in the combined probability space, of the events a -> s and s -> b. For G(n,p), we prove that there is a p_c=1/2 such that for a fixed p<p_c the correlation is negative for large enough n and for p>p_c the correlation is positive for large enough n. We conjecture that for a fixed nge 27 the correlation changes sign three times for three critical values of p. For G(n,m) it is similarly proved that, with $$, there is a critical p_c that is the solution to a certain equation and approximately equal to 0.7993. A lemma, which computes the probability of non existence of any k directed edges in G(n,m), is thought to be of independent interest. We present exact recursions to compute P(a -> s)$andP(a->s,s->b)$. We also briefly discuss the corresponding question in the quenched version of the problem.

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

Recommendations

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

zbMATH Keywords

correlationquenchedannealeddirected pathsrandom directed graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80)

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• Probability: A Graduate Course
• General percolation and random graphs
• Some conditional correlation inequalities for percolation and related processes
• A correlation inequality for connection events in percolation
• On percolation and the bunkbed conjecture
• Infinite paths in randomly oriented lattices
• A counter-intuitive correlation in a random tournament
• Correlations for paths in random orientations of \(G(n,p)\) and \(G(n,m)\)

Cited In (6)

• A counter-intuitive correlation in a random tournament
• Positive association of the oriented percolation cluster in randomly oriented graphs
• 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)\)
• Connections in randomly oriented graphs
• First critical probability for a problem on random orientations in \(G(n,p)\).

This page was built for publication: Correlations for paths in random orientations of \(G(n,p)\) and \(G(n,m)\)

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