Equivalent Formulations of the Bunk Bed Conjecture

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.