Existence of small subgraphs of a random graph, but conditioned to intersect a pair of vertices.

149 Views Asked by At

What is the probability a subgraph $\Gamma$ isomorphic to the connected graph $H$ exists in the Erdős–Rényi random graph $G(n,p)$, with $p=n^{-\alpha}$ for some $\alpha<1$, but, we also want $\Gamma$ to have two specific vertices $v,w$ of $G$ at specific points $x,y$?

For example, the start and end vertices of a path graph $\Pi_m$ of $m$ edges intersecting two specific vertices of $G$.

If we look at the distribution of $\Gamma$, according to Bollobás in [Chapter 4, 1], as $n \to \infty$ this is $\text{Poisson}(\mu)$ with some mean to be calculated, but only if we don't condition on these specific vertices existing in the subgraph at the fixed points. The distribution is then, on the whole, not Poisson, as the variance will exceed the mean since the subgraphs are more likely to overlap. But are there some existence probabilities (or limiting distributions) similar to $1-e^{-\mu}$, as the $\text{Poisson}(\mu)$ would suggest?

1

There are 1 best solutions below

6
On BEST ANSWER

Even for the ordinary problem, the limit is Poisson for a very specific range of $p$, and only for some $H$. The general rule we hope for, if $H$ is a nice graph, is that for $p$ below a threshold, the number of $\Gamma$s tends to $0$; for $p$ at the threshold, the number of $\Gamma$s is Poisson; for $p$ above the threshold, the number tends to infinity with $n$.

The first thing that happens if we fix two vertices is that the threshold changes. For example, if $H$ is a path on $3$ vertices with endpoints $v$ and $w$, the expected number of copies of $H$ in $G$ with fixed vertices $x,y$ to play the role of $v,w$ is $(n-2)p^2$. So the threshold probability is $p = \frac1{\sqrt n}$. (Before, the expected number was roughly $n^3p^2$, and so the threshold was $p = n^{-3/2}$.) Beyond that, it should be standard to prove that when $p = \frac{c}{\sqrt n}$, the number of copies of $H$ is Poisson with mean $c$ in the limit.

The second thing that happens is that a different class of subgraphs will cause us problems. For example, if $H$ is a $4$-cycle and $v,w$ are opposite vertices, then the number of copies of $H$ is actually just $\binom{X}{2}$, where $X$ is the number of copies of the path in the previous example. This is not Poisson at the threshold (though we can still work out the distribution) and the reason is that there is a lot of overlap between different copies of $H$.

That's not going to be a universal thing that happens (and it was already a thing to worry about for some graphs before we fixed the vertex pair). For example, let $H$ be the graph $K_4 - vw$: a $4$-clique, but with edge $vw$ removed. Then the expected number of copies of $H$ with $v,w=x,y$ is roughly $n^2 p^5$, so the threshold is $p = n^{-2/5}$. The number of pairs of copies of $H$ sharing one of the middle vertices is roughly $n^3 p^8$, which is $n^{-1/5}$ at the threshold; so the second moment method, at least, works just fine. I think probably the Poisson limit will go through as well.

The last thing that happens is that we get a very different outcome when $vw$ is an edge of $H$, which I've avoided in the examples above. In this case, we get a mixed distribution: with probability $p$, $xy$ is an edge of $G$ and we can proceed as before, and with probability $1-p$, $xy$ is not an edge of $G$ and there are no copies of $H$. This means that the threshold for copies of $H$ is now when $p$ is constant, though, and in that case we already expect the number of copies of $H$ to tend to infinity in the limit.