Connections in Randomly Oriented Graphs

Bhargav Narayanan

doi:10.1017/S0963548316000341

Connections in Randomly Oriented Graphs

Bhargav Narayanan

School of Arts and Sciences, Mathematics

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

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 P(s → a ∩ s → b) ≥ P(s → a) P(s → b).

Original language	English (US)
Pages (from-to)	667-671
Number of pages	5
Journal	Combinatorics Probability and Computing
Volume	27
Issue number	4
DOIs	https://doi.org/10.1017/S0963548316000341
State	Published - Jul 1 2018

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Statistics and Probability
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1017/S0963548316000341

Cite this

@article{908a948c39184b4594cdb1b050a5703f,

title = "Connections in Randomly Oriented Graphs",

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 P(s → a ∩ s → b) ≥ P(s → a) P(s → b).",

author = "Bhargav Narayanan",

note = "Publisher Copyright: {\textcopyright} 2016 Cambridge University Press.",

year = "2018",

month = jul,

day = "1",

doi = "10.1017/S0963548316000341",

language = "English (US)",

volume = "27",

pages = "667--671",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "4",

}

TY - JOUR

T1 - Connections in Randomly Oriented Graphs

AU - Narayanan, Bhargav

PY - 2018/7/1

Y1 - 2018/7/1

N2 - 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 P(s → a ∩ s → b) ≥ P(s → a) P(s → b).

AB - 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 P(s → a ∩ s → b) ≥ P(s → a) P(s → b).

UR - http://www.scopus.com/inward/record.url?scp=85002142102&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85002142102&partnerID=8YFLogxK

U2 - 10.1017/S0963548316000341

DO - 10.1017/S0963548316000341

M3 - Article

AN - SCOPUS:85002142102

SN - 0963-5483

VL - 27

SP - 667

EP - 671

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 4

ER -

Connections in Randomly Oriented Graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this