4
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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