Hostname: page-component-7b9c58cd5d-f9bf7 Total loading time: 0 Render date: 2025-03-15T03:45:49.779Z Has data issue: false hasContentIssue false
  • English
  • Français

A Counter-Intuitive Correlation in a Random Tournament

Published online by Cambridge University Press:  13 May 2010

SVEN ERICK ALM  and
SVANTE LINUSSON
SVEN ERICK ALM
Affiliation:
Department of Mathematics, Uppsala University, PO Box 480, SE-751 06, Uppsala, Sweden (e-mail: sea@math.uu.se)
SVANTE LINUSSON
Affiliation:
Department of Mathematics, KTH – Royal Institute of Technology, SE-100 44, Stockholm, Sweden (e-mail: linusson@math.kth.se)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Consider a randomly oriented graph G = (V, E) and let a, s and b be three distinct vertices in V. We study the correlation between the events {a → s} and {s → b}. We show that, counter-intuitively, when G is the complete graph Kn, n ≥ 5, then the correlation is positive. (It is negative for n = 3 and zero for n = 4.) We briefly discuss and pose problems for the same question on other graphs.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 1 , January 2011 , pp. 1 - 9
Copyright
Copyright © Cambridge University Press 2010

References

[1]Alm, S. E. and Linusson, S. A counter-intuitive correlation in a random tournament (early version of the present paper). arXiv:0906.0240Google Scholar
[2]Alm, S. E. and Linusson, S. (2009) Correlations for paths in random orientations of G(n, p). Preprint. arXiv:0906.0720Google Scholar
[3]van den Berg, J. and Kahn, J. (2001) A correlation inequality for connection events in percolation. Ann. Probab. 29 123–126.Google Scholar
[4]van den Berg, J., Häggström, O. and Kahn, J. (2006) Some conditional correlation inequalities for percolation and related processes. Random Struct. Alg. 29 417–435.CrossRefGoogle Scholar
[5]Grimmett, G. R. (1999) Percolation, Springer, Berlin.CrossRefGoogle Scholar
[6]Grimmett, G. R. (2001) Infinite paths in randomly oriented lattices. Random Struct. Alg. 18 257–266.CrossRefGoogle Scholar
[7]Häggström, O. (2003) Probability on Bunkbed Graphs. InProc. FPSAC'03: Formal Power Series and Algebraic Combinatorics (Linköping, Sweden). Available at http://www.fpsac.org/FPSAC03/ARTICLES/42.pdf.Google Scholar
[8]Linusson, S. (2009) A note on correlations in randomly oriented graphs. Preprint. arXiv:0905.2881.Google Scholar
[9]Linusson, S. (2010) On percolation and the bunkbed conjecture. Combin. Probab. Comput. XX.Google Scholar
[10]McDiarmid, C. (1981) General percolation and random graphs. Adv. Appl. Probab. 13 40–60.CrossRefGoogle Scholar