Skip to main content
Article

Equivalent Formulations of the Bunk Bed Conjecture

Authors
  • James Rudzinski (The University of North Carolina at Greensboro)
  • Clifford Smyth (The University of North Carolina at Greensboro)

Abstract

A bunk bed graph consists of two isomorphic graphs, called the upper and lower bunks, and some additional edges, called posts; each post connects a vertex in the upper bunk with the corresponding isomorphic vertex in the lower bunk. We assign a probability to each edge with each edge in the upper bunk assigned the same probability as the corresponding isomorphic edge in the lower bunk.  The probabilities on the posts are arbitrary.  We then form a random spanning subgraph of the bunk bed graph by deleting each edge independently with the prescribed probability.  The Bunk Bed Conjecture states that in the random subgraph the probability that a vertex x in the upper bunk is connected to some vertex y in the upper bunk is greater than or equal to the probability that x is connected to z, the isomorphic copy of y in the lower bunk. We show that for each p in (0,1) the special case of the Bunk Bed Conjecture in which all edge probabilities are p is equivalent to the full conjecture.

Keywords: Percolation, bunk bed conjecture

How to Cite:

Rudzinski, J. & Smyth, C., (2016) “Equivalent Formulations of the Bunk Bed Conjecture”, North Carolina Journal of Mathematics and Statistics 2(1).

Downloads:
Download pdf

10 Views

4 Downloads

Published on
2016-05-31

Peer Reviewed

License