Consider a graph $G$ with a particular node $i$ labeled as “infected”. Other nodes start uninfected, and will become infected over time according to the following process: To each edge of the graph, we associate a Poisson process with rate $\lambda$ over the positive real numbers. Processes for different edges are independent. If the process associated with edge (j,k) has an occurrence at time $t \in [0,\infty)$ and exactly one of the nodes $j$ or $k$ is already infected at time $t$, then the other node becomes infected thereafter; otherwise both nodes remain labeled as they were before.

Now let $p^G_{ij}(t)$ be the probability that a node $j$ in graph $G$ is labeled as infected by time $t$ (given that $i$ was the original infected node). Our conjecture is the following:

Conjecture: Let $G$ be any regular graph of degree $d$ and let $H$ be the complete graph with $d+1$ nodes. Then $p^G_{ij}(t) \leq p^H_{12}(t)$ for all nodes $j$ that are neighbors to $i$ in graph $G$.

In words: Among regular graphs of degree $d$, the complete graph is the one that gives the highest infection rates to immediate neighbors of an infected node.

  • 1
    $\begingroup$ See "bunkbed conjecture" for another plausible statement about percolation that appears not to be straightforward. $\endgroup$ – Ben Barber Mar 10 '17 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.