Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $G'$ be a graph obtained from $G$ after contracting each edge with probability $p$. Let $n = |V(G)|, e = |E(G)|$.

I would like to compute (or at least obtain a lower bound) for $E[|V(G')|]$ in terms of some known graph invariants (number of edges, degree sequence, connectivity,..)

I am sure I am not the first one that studied such a probabilistic space and since I couldn't find any estimates for $E[|V(G')|]$ in my textbook I am asking: is there any simple identity/estimate for $E[|V(G')|]$ ? Is there any reference to a paper studying this quantity?

Edit: I have removed the completely wrong attempt to estimate $E[|V(G')|]$.

share|improve this question
    
I don't think your calculation is right. If I understand it correctly, you subtracted one vertex for each contracted edge. However, if you have, say, a triangle subgraph and you contract two of its edges, then the whole trinagle is already collapsed to a point, hence contracting the third edge has no effect on the number of vertices. –  Emil Jeřábek Mar 28 '11 at 14:28
    
(However, if you do make the incorrect assumption that each contracted edge decreases the vertex count, then you should get $E|V(G')|=n-pe$ by linearity of expectation.) –  Emil Jeřábek Mar 28 '11 at 14:32

3 Answers 3

up vote 5 down vote accepted

The expected number of vertices of $G'$ is given by a sum (over all sets of edges) that bears a certain resemblance to the Tutte polynomial $T(x,y)$ of (the graphical matroid associated to) $G$, as defined, for example, at http://en.wikipedia.org/wiki/Matroid#Tutte_polynomial. A quick calculation (maybe too quick --- I don't guarantee the following and I apologize for any errors here, but something like this should be true) indicates that, if we let $v,e,c$ be the number of vertices, edges, and components of $G$, then the expected number of vertices of $G'$ is

$$c+p^{v-c}(1-p)^{e+c-v}\frac{\partial T(x,y)}{\partial x}\left(x=\frac1p,y=\frac1{1-p}\right).$$

EDIT: In answer to the question about how I got this, and in the interest of correcting missing factors of $p$ and $1-p$ in the answer above, here are some details.

I'll use the notation $v,e,c$ as above. In addition, for any subset $S$ of the edges, I'll write $z(S)$ for the number of points after the edges in $S$ are contracted; it's also the number of connected components of the graph with the same vertices as $G$ but only the edges in $S$. Note that the rank of $S$ in the graphical matroid is $v-z(S)$. Obviously, $z(S)$ is always at least $c$; it turns out to be convenient to work with the difference, which I'll abbreviate $q(S)=z(S)-C$. Taking the definition of the Tutte polynomial $T(x,y)$ from the Wikipedia page linked above, and using the connection between ranks and $z$, we get $$ T(x,y)=\sum_{S\subseteq E}(x-1)^{z(S)-c}(y-1)^{|S|-v+z(S)}= \sum_{S\subseteq E}(x-1)^{q(S)}(y-1)^{|S|-v+c+q(S)}. $$

Compare this with the expectation of $q$, namely $$ \sum_{S\subseteq E}q(S)p^{|S|}(1-p)^{|E|-|S|}= (1-p)^{|E|}\sum_{S\subseteq E}q(S)\left(\frac p{1-p}\right)^{|S|}. $$

We can convert $T(x,y)$ into this expectation in a few steps, as follows. First, if we differentiate $T(x,y)$ with respect to $x$ and multiply the result by $x-1$, the effect is to bring down a factor $q(S)$ from the exponent without changing anything else. That factor $q(S)$ matches part of what we want in the expectation of $q$. Next, we can make the $x-1$ and $y-1$ stuff in $T$ match the $p$ and $1-p$ stuff that we want. First set $y-1=p/(1-p)$; equivalently, $y=1/(1-p)$. Then the terms in $T$ will have the factor $(p/(1-p))^{|S|}$ that we want. They also have other factors that we don't want, namely $(x-1)^{q(S)}$ and $(p/(1-p))^{-v+c+q(S)}$. We can get rid of the $q(S)$ powers here by setting $x-1=(1-p)/p$; equivalently $x=1/p$. What remains is an unwanted factor $(p/(1-p))^{-v+c}$ that doesn't involve $S$ and can therefore be pulled out of the sum. Collecting all this stuff (and hoping that I'm copying everything correctly --- copying is sometimes the hardest part of mathematics), I get that the expectation of $q$ is $$ (1-p)^e\cdot \left[\left((x-1)\frac{\partial T(x,y)}{\partial x}\right) (\frac1p,\frac1{1-p})\right]\cdot\left(\frac p{1-p}\right)^{v-c}, $$ which simplifies to $$ p^{v-c-1}(1-p)^{e+c-v+1}\frac{\partial T}{\partial x}\left(\frac1p,\frac1{1-p}\right). $$ Finally, add $c$ to get the expectation of $z$.

share|improve this answer
    
Could you please explain how you got this answer? –  Jernej Jul 11 '11 at 14:23
    
I've edited the answer to include an explanation and a correction. –  Andreas Blass Jul 11 '11 at 18:12

Let's color each edge red with probability $p$, independently of other edges. Two vertices of $G$ glue together if and only if they are connected with a red path. Hence, your $V(G')$ is exactly the number of connected components of the subgraph, obtained from $G$ by keeping the red edges and removing all other (non-colored) edges. That is, you are interested in the expected number of connected components in the random subgraph of $G$, obtained by deleting every edge of $G$, randomly and independently from other edges, with probability $q:=1-p$. This quantity has been studied: see, for instance, this paper by Alon, or just google for something like "connected components of a random subgraph".


To complement the answer above, here is a simple lower bound which, intuition suggests, may be reasonably sharp for a wide class of graphs.

For a given vertex $v$, the probability that $v$ gets disconnected from the rest of the graph is $q^{d(v)}$ (where $d(v)$ denotes the degree of $v$). Therefore, the expected number of connected components of $G'$ is at least $$ \sum_v q^{d(v)}. $$ Now, let $\bar d$ denote the average degree of $G$. Since $G$ has at least $n/2$ vertices of degree at most $2\bar d$, the expected number of connected components is $\Omega(nq^{2\bar d})$. Thus, we have, say,

$$ {\mathsf E}(V(G')) = \Omega(ne^{-3p {\bar d} }) $$

subject to some mild technical restriction (like $p<1/2$).

share|improve this answer

Rather than complicated, that sum would be quite simple if it were correct. It doesn't depend on the structure of the original graph, only on the numbers of vertices and edges. It is also wrong.

Consider $G$, a complete graph on $4$ vertices plus $2$ isolated vertices, and $H$, a hexagon. Both have $6$ vertices and $6$ edges. However, there is no way for $G'$ to have fewer than $3$ vertices, while $H'$ can have $1$ or $2$. Any correct formula for the probability that the contracted graph has $2$ vertices must depend on properties of the graph other than just the number of vertices and edges.

Here is a more subtle approach which also doesn't work (exactly): Order the vertices, and for each vertex $v$, consider the number of vertices of lower index which are adjacent to $v$, $d^-(v)$. For $v$ to be the least index in its equivalence class (a vertex in $G'$), it is necessary that none of these edges are contracted. However, this is not sufficient, since it could be that $(v_2,v_3)$ and $(v_3,v_1)$ are contracted even though $(v_2,v_1)$ is not. However, for any ordering, you at least get the bound

$$E|V(G')| \le \sum_v (1-p)^{d^-(v)}.$$

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.