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

DOI10.1002/RSA.20358MaRDI QIDQ5388971zbMATH OpenOpenAlexFDO

Authors Sven Erick Alm, Svante Janson, Svante Linusson

Publication date 24 April 2012

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

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

zbMATH Keywords

annealedcorrelationdirected pathsquenchedrandom directed graphs

Mathematics Subject Classification ID

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

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.

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

Cites work

• A correlation inequality for connection events in percolation
• A counter-intuitive correlation in a random tournament
• 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
• On percolation and the bunkbed conjecture
• Probability Inequalities for Sums of Bounded Random Variables
• Probability: A Graduate Course
• Some conditional correlation inequalities for percolation and related processes

Cited in

(6)

• A counter-intuitive correlation in a random tournament
• Connections in randomly oriented graphs
• 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)\)
• 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)