MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

First of all, I apologise if my question is not very specific. I am not really looking for a concrete answer but rather some hints and pointers what could be used/applied in this situation. A concrete example of how this is handled in practice would be nice too!

I read the very interesting article Terence Tao wrote about the crossing number inequality:

I was wondering, how could one apply the same trick to other graph invariants where the amplified inequality only applies to connected graphs. More formally:

Let $i:G \mapsto \mathbb{R}$ be some graph invariant $f,g$ functions such that the inequality:

$i(G) \geq f(|V(G)|) + g(|E(G)|)) \;\;\;\;(1) $

holds for all connected graphs $G$.

Let $G'$ be the graph obtained from $G$ after we remove some of the vertices (or edges) with probability $p\in [0,1]$.

In the same manner as with the crossing number inequality, one would like to apply the inequality to $G'$ and examine the expected value of the obtained quantities. That is:

$E(i(G')) \geq E(f(|V(G')|)) + E(g(|E(G')|)) \;\;\;\;(2)$.

The problem with the last inequality is that it only holds when $G'$ is connected,which needs not to be. The obvious way to fix the problem is to modify $(1)$ so that it holds even when $G$ is not connected. In practice it can be hard to modify $(1)$ and still obtain a bound that will give a good inequality when estimating $(2)$.

So my question is: is there any known trick to force $G'$ to remain connected or somehow "handle" the disconnectedness case?

share|cite|improve this question
I've never heard of such a trick but one thing you could try is first fixing a spanning tree (deterministically or, perhaps more usefully depending on the situation, according to the uniform or another distribution), then doing the random edge deletion only on edges that don't belong to the spanning tree. Without knowing more about the invariants you want to consider, I don't have any better idea than that. – Louigi Addario-Berry Feb 7 '11 at 16:19
That Tao post is very nice... – Igor Rivin Feb 8 '11 at 3:56
What seems tricky here is that if the property holds for any connected graph, and in particular a tree, then even if p = 1/n, there's a high probability of the property failing. So you're dealing in a very narrow range. – Suresh Venkat Feb 8 '11 at 8:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.