Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-23T13:32:01.506Z Has data issue: false hasContentIssue false
  • English
  • Français

Connections in Randomly Oriented Graphs

Published online by Cambridge University Press:  06 December 2016

BHARGAV NARAYANAN
BHARGAV NARAYANAN*
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Given an undirected graph G, let us randomly orient G by tossing independent (possibly biased) coins, one for each edge of G. Writing a → b for the event that there exists a directed path from a vertex a to a vertex b in such a random orientation, we prove that for any three vertices s, a and b of G, we have ℙ(s → a ∩ s → b) ⩾ ℙ(s → a) ℙ(s → b).

Keywords

Primary 60C05Secondary 60K35
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Special Issue 4: Special Issue: Oberwolfach Workshop , July 2018 , pp. 667 - 671
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Ahlswede, R. and Daykin, D. E. (1978) An inequality for the weights of two families of sets, their unions and intersections. Z. Wahrsch. Verw. Gebiete 43 183–185.Google Scholar
[2] Alm, S. E., Janson, S. and Linusson, S. (2011) Correlations for paths in random orientations of G(n, p) and G(n, m). Random Struct. Alg. 39 486–506.Google Scholar
[3] Alm, S. E. and Linusson, S. (2011) A counter-intuitive correlation in a random tournament. Combin. Probab. Comput. 20 1–9.Google Scholar
[4] Alon, N. and Spencer, J. H. (2008) The Probabilistic Method, third edition, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley.Google Scholar
[5] Grimmett, G. R. (2001) Infinite paths in randomly oriented lattices. Random Struct. Alg. 18 257–266.Google Scholar
[6] Harris, T. E. (1960) A lower bound for the critical probability in a certain percolation process. Proc. Cambridge Philos. Soc. 56 13–20.Google Scholar
[7] Leander, M. and Linusson, S. (2015) Correlation of paths between distinct vertices in a randomly oriented graph. Math. Scand. 116 287–300.CrossRefGoogle Scholar
[8] Linusson, S. A note on correlations in randomly oriented graphs. arXiv:0905.2881Google Scholar
[9] McDiarmid, C. (1981) General percolation and random graphs. Adv. Appl. Probab. 13 40–60.Google Scholar