The degree-two vertex conjecture for random tournaments

From papers

Let G=(V,E)G=(V,E) be a connected graph, and let aa, ss, and bb be three distinct vertices in VV. The events {as}\{a\to s\} and {sb}\{s\to b\} record directed reachability in the random tournament associated with GG.

Degree-two vertex conjecture. If ss has degree at most two, then the events {as}\{a\to s\} and {sb}\{s\to b\} are independent or negatively correlated.

This extends the corresponding result for trees and the established bound for cycles. The claim concerns the sign of the correlation when the distinguished vertex has degree at most two; no resolution is supplied in the source.

Progress summary

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

Sources & referencesView supporting material

Primary source

Sven Erick Alm and Svante Linusson, “A counter-intuitive correlation in a random tournament”, arXiv:0906.0240 (2009).

Solutions 0

No solutions have been posted yet.