Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

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|cite|improve this question
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|cite|improve this answer
Thanks for the very interesting link! – Alex R. Aug 6 '12 at 21:22

Your Answer


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.