A single covariance sign change in random orientations of G(n,m)G(n,m)

About 17 years old · traced to

Let G(n,m)G(n,m) be the uniformly random graph with exactly mm edges on nn vertices, and orient every present edge independently and uniformly at random. Fix distinct vertices s,a,bs,a,b, and let AA be the event that there is no directed path from aa to ss, while BB is the event that there is no directed path from ss to bb. The covariance in question is

Cov⁡(1A,1B)=P(A∩B)−P(A)P(B).\operatorname{Cov}(\mathbf{1}_A,\mathbf{1}_B)=\mathbb{P}(A\cap B)-\mathbb{P}(A)\mathbb{P}(B).

Single-sign-change conjecture. For any fixed n≥5n\ge 5, the covariance in G(n,m)G(n,m) changes sign only once between two values of mm.

References

Primary source

Sven Erick Alm, Svante Janson and Svante Linusson, “Correlations for paths in random orientations of G(n,p) and G(n,m)”, arXiv:0906.0720 (2010).

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.