[Math] Erdős-Rényi Random Graph Triangle Number

graph theoryprobabilityprobability theory

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!

Best Answer

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.

Related Question