Let $G=(V,E)$ be a finite simple 2-connected graph. Let $B\subseteq E$ be a set of bad edges of size $k:=|B|$. For each edge $e\in E$ we toss a fair coin ($p=1/2$) and if the outcome is head, we hit the edge $e$ and we let it die (sorry about that). At the end of the process, we consider the set of survived edges $S$ and we look at the graph $G[S]$ consisting of survived edges only. Let $C_1, \ldots, C_n$ be the connected components of $G[S]$ and let $e=(u,v)$ be a dead edge: we say that $e$ died with honor if there exists just a single component $C_i$ s.t. $u,v\in C_i$, that is $e$ dies with honor if it doesn't connect two different components of the survived edges graph.

What can we say about the probability $P_H$ of the event $H=$"all the bad edges $B$ are dead and at least one died with honor" ? Can we lower bound somehow this probability as a function of $k$ ? Can we find structural hypothesis over $G$ or particular distributions for random $G$ in order to do that ?

  • 7
    $\begingroup$ I love the phrase, but I'm curious about the motivation for it. Why does an edge "die with honor" in this case ? i.e why is it dishonorable for an edge to have died disconnecting two components ? $\endgroup$ Jan 24, 2014 at 22:46
  • $\begingroup$ The colorful phrase comes from the fact that at the end of the process we would like to distinguish bad dead edges from the good dead ones, but we can look what is going on just inside the connected components. So if a bad edge dies inside a connected component we can recognize that it was indeed bad. $\endgroup$
    – XORwell
    Jan 25, 2014 at 9:27
  • 1
    $\begingroup$ Ah. so "died with dishonor" means "could not be identified". Gruesome, but I get it. $\endgroup$ Jan 25, 2014 at 18:11
  • $\begingroup$ means "it was bad, but it could not be identified"... I can rephrase... $\endgroup$
    – XORwell
    Jan 25, 2014 at 18:50
  • $\begingroup$ I might not understand the question but if G is a cycle and k is at least 2, then this probability is zero. $\endgroup$
    – domotorp
    Jan 25, 2014 at 20:23


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.