Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $G(n,p)$ be the usual Erdős-Rényi random graph. Let $T$ be the number of triangles in a realization of such a random graph. After counting $T$, let $T'$ be the number of triangles after selecting a pair of vertices, uniformly at random and then redrawing the edge with the same probability $p$. Are there any asymptotic results in $n$ of $P(T'\mid T)$? If it helps, one can assume that $T$ is chosen to be larger than the expected number of triangles. Moreover, notice that choosing a vertex pair uniformly is equivalent to just fixing two vertices and subsequently redrawing the edge. References would be greatly appreciated!

share|improve this question

1 Answer 1

up vote 0 down vote accepted

You may want to have a look at this paper. There are calculations in there closely related to your question. But whether this helps depends on what kind of information about $P(T'|T)$ you are looking for.

share|improve this answer
    
Thanks for the very interesting link! –  Alex R. Aug 6 '12 at 21:22

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.