← All problems

Positive correlation of paths in the annealed random graph model for all parameters

13 years old · traced to

Let GG be the annealed randomly oriented Erdős–Rényi graph G⃗(n,p)\vec G(n,p), with distinct vertices a,s,b,ta,s,b,t, and let {s→a}\{s\to a\} and {t→b}\{t\to b\} be the events that directed paths exist from ss to aa and from tt to bb. Positive-correlation conjecture. For every n≥4n\geq 4 and p∈(0,1]p\in(0,1], the events {s→a}\{s\to a\} and {t→b}\{t\to b\} are positively correlated. The paper proves this for sufficiently large nn at each fixed p∈(0,1]p\in(0,1] and reports computational support for the stronger uniform assertion, which remains open in the supplied text.

References
  1. Svante Linusson and Madeleine Leander, “Correlation of paths between distinct vertices in a randomly oriented graph”, arXiv:1303.3961 (2013).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.