Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-07T05:56:23.476Z 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: b.p.narayanan@dpmms.cam.ac.uk)
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.

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

Information

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 

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