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!
[Math] Erdős-Rényi Random Graph Triangle Number
graph theoryprobabilityprobability theory
Related Solutions
The probability that there is at least one triangle can be expressed using inclusion/exclusion:
$$ \mathbb{P}\biggl(\bigcup_{i=1}^n A_i\biggr) =\sum_{k=1}^n (-1)^{k-1}\sum_{\scriptstyle I\subset\{1,\ldots,n\}\atop\scriptstyle|I|=k} \mathbb{P}\left(\bigcap_{i\in I} A_i\right)\;, $$
where the $A_i$ are the events of individual triangles existing. I don't see a way to evaluate this in closed form, but it can be used to expand the desired probability in powers of $p$, and truncating the sum at some $k$ yields successively improved bounds (upper bounds for odd $k$ and lower bounds for even $k$). In the asymptotic case of fixed $\lambda=np$ as $n\to\infty$, the series can be summed exactly and yields a probability of $1-\mathrm e^{-\lambda^3/6}$.
The $k=1$ term is just the expectation value that Douglas gave in his now-deleted answer, $\binom n3p^3$, which is an upper bound for the desired probability by the first moment method (which can be regarded as a special case of the present approach).
The term for $k=2$ triangles yields contributions with $5$ and $6$ edges. With $5$ edges, there are $\binom n4$ ways to select four vertices and $6$ ways to select one of the $6$ edges between them that isn't used, for a contribution of $6\binom n4p^5$. With $6$ edges, we can either have $5$ different vertices, with $5$ options to choose the shared vertex and $\frac12\binom42=3$ options to choose pairs among the remaining $4$, for a contribution of $15\binom n5p^6$, or we can have $6$ different vertices, with $\frac12\binom63=10$ options to choose triangles among them, for a contribution of $10\binom n6p^6$. Thus the desired probability $q$ is bounded by
$$ \binom n3p^3-\left(6\binom n4p^5+15\binom n5p^6+10\binom n6p^6\right)\le q\le\binom n3p^3\;. $$
Asymptotically, if you keep $\lambda=np$ constant as $n\to\infty$, this becomes
$$\frac{\lambda^3}6-\frac{\lambda^6}{72}\lesssim q\lesssim\frac{\lambda^3}6\;.$$
For $k$ edges, the only contribution with enough powers of $n$ to match the $k$ powers of $p$ is one where there is only one edge per vertex, namely where the $k$ edges form $k/3$ triangles among $k$ vertices. Thus, asymptotically, the desired probability is given by
$$ q\sim\sum_{j=1}^\infty(-1)^{j-1}\frac{\lambda^{3j}}{6^jj!}=1-\mathrm e^{-\lambda^3/6}\;. $$
In the original form of your question, in which you had $p=1/n$ and thus $\lambda=1$, this would be $1-\mathrm e^{-1/6}\approx0.1535$.
If you want the full finite-size expansion in powers of $p$ up to $6$-th order, you need to include the contribution $\binom n4p^6$ from all $6$ edges formed by $4$ vertices to get
$$ q = \binom n3p^3-\left(6\binom n4p^5+15\binom n5p^6+10\binom n6p^6+\binom n4p^6\right)+O\left(p^7\right)\;. $$
Let $X$ be the total number of cycles, $X_k$ the number of cycles of length $k$ in $G$, and $Y_k$ the number of cycles of length $k$ in a random graph of size $k$.
Note that:
- ${\sf E}[X] = \sum_{k=2}^n {\sf E}[X_k]$.
- ${\sf E}[X_k] = {n \choose k} {\sf E}[Y_k]$.
- ${\sf E}[Y_k] = (k!/k)p^k = (k-1)!p^k$.
The last one is because a cycle of length $k$ is a permutation of numbers from $1$ to $k$ but the first vertex does not matter (a cycle does not have a first vertex). The probability of each edge being present is $p$, so the probability of $k$ edges being present is $p^k$.
We have:
\begin{align*} {\sf E}[X] &= \sum_{k=2}^n E[X_k] \\ &= \sum_{k=2}^n {n \choose k} E[Y_k] \\ &= \sum_{k=2}^n {n \choose k} (k-1)! p^k \\ &= \sum_{k=2}^n \frac{n!}{k!(n-k)!} (k-1)! p^k \\ &= \sum_{k=2}^n \frac{n!}{(n-k)!k} p^k \\ &= \sum_{k=2}^n \frac{n\ldots (n-k+1)}{k} p^k \\ \end{align*}
For a simple lower bound we can drop the first half of the sum: \begin{align*} &\geq \sum_{k=n/2}^{n} \frac{n\ldots (n-k+1)}{k} p^k \\ &\geq \sum_{k=n/2}^{n} \frac{(n/2)^{k}}{n} p^k \\ &\geq \frac{1}{n}\sum_{k=n/2}^{n} (np/2)^{k} \\ &= \frac{(\frac{np}{2})^{n+1}-(\frac{np}{2})^{\frac{n}{2}}}{\frac{np}{2}-1} \end{align*}
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.