Correlation of paths between distinct vertices in a randomly oriented\n graph

2013/03/16 by Svante Linusson, Linusson, Svante, Madeleine Leander +1
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1303.3961

openalex publication_date 2013/03/16 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28

Abstract

We prove that in a random tournament the events s\→ a and\n t\→ b are positively correlated, for distinct vertices a,s,b,t\n\∈ K_n. It is also proven that the correlation between the events\n s\→ a and t\→ b in the random graphs G(n,p) and\nG(n,m) with random orientation is positive for every fixed p>0 and\nsufficiently large n (with m= \lfloor p binomn2 \rfloor). We\nconjecture it to be positive for all p and all n. An exact recursion for\n P( s\→ a \∩ t\→ b ) in gnp is given.\n

Citations

• A note on correlations in randomly oriented graphs

Related

• Correlations for paths in random orientations of G(n,p) and G(n,m)
• A counter-intuitive correlation in a random tournament
• Path correlations in a randomly oriented complete bipartite graph
• A note on correlations in randomly oriented graphs
• First critical probability for a problem on random orientations in G(n,p)