Probability a given path occurs in a uniformly random simple graph

Question

Let $(G_n)$ be a sequence of uniformly sampled simple graphs with $|G_n|=n$ and $\deg i = D_i$ where the $(D_i)_{i=1}^n$ are iid random variables with mean $\mu$.

Let $\gamma$ be the path $(1,2, \cdots, k)$. Does there exists a constant $C>0$ such that $$P(\gamma \in G_n) \leq C (\mu/n)^k\text{ for all $k,n \geq 1$?}$$

The inspiration for this question is the sparse Erdos-Renyi graph, which by definition satisfies $P(\gamma \in G(n, \mu/n)) = (\mu/n)^k$.

We are looking for a proof of the analogous bound for simple graphs with prescribed degree sequences, but the slight dependence between the edges has us stumped.

Answer 1

For sparse random regular graphs, and if $k \ll n$, the bound holds

The idea is to use the configuration model: take $\mu$ stubs out of each of $n$ vertices, then create edges by picking a uniformly random matching of the $\mu n$ stubs total. This produces a multigraph in general, but in the sparse case - when $\mu$ is constant - there is a lower bound independent of $n$ on the probability that the graph will be simple. So when we condition on getting a simple graph, it will not affect the result.

If we fix a path with $k$ edges and $k+1$ vertices, there are $\mu \cdot [\mu(\mu-1)]^{k-1} \cdot \mu = O( (\mu(\mu-1))^k)$ ways to choose the stubs that are matched together to build the path. For each choice of those stubs, there is a probability of $\frac{1}{\mu n - 1} \cdot \frac1{\mu n - 3} \cdots \frac1{\mu n - 2k+1}$ that those stubs will be connected. When $k$ is small compared to $n$, this probability is $O(1/(\mu n)^k)$, giving an overall probability of $O((\frac{\mu-1}{n})^k)$.

This is even better than the $(\frac \mu n)^k$ we were hoping for! As an extreme example, if $\mu=1$, then the random graph is a uniformly random matching, and the probability of getting any path with $k \ge 2$ edges is $0$, not proportional to $\frac1{n^k}$.

In general, the constant could be worse

Here's an example. Suppose that $D_i$ is equally likely to be $0$ or $4$, so that $\mu=2$. We can repeat the calculation we did in the regular case, except:

• A fixed path has a probability of $\frac1{2^{k+1}}$ of being viable to begin with: this is the probability that all its vertices have degree $4$ and not $0$.
• There are $4 \cdot 12^{k-1} \cdot 4 = \Theta(12^k)$ ways to match up the stubs along the path, given that all its vertices do have degree $4$.
• When $n$ is large, there are close to $2n$ stubs total; when $k$ is small, the probability that a given realization of the path is chosen is $\Theta(1/(2n)^k)$.

Multiplying these together, we get $\frac1{2^k} \cdot 12^k \cdot \frac1{(2n)^k} = (\frac 3n)^k$, instead of the desired bound of $(\frac \mu n)^k = (\frac 2n)^k$.

This bound suggests that the correct constant in the base of the exponent is more like $\frac{\mathbb E[D(D-1)]}{\mathbb E[D]}$, though more work would have to be done to prove this in general. (For Erdos-Renyi graphs, the degree distribution is $D \sim \text{Poisson}(\mu)$, and $\mathbb E[D(D-1)] = \mu^2$, which is why we get $(\frac \mu n)^k$ there.)

These calculations also assume that $k$ is small compared to $n$, otherwise, the factor of $\frac1{\mu n-1} \cdot \frac1{\mu n-3} \cdots$ would (1) be significantly different from $(\frac1{\mu n})^k$ and (2) fail to take into account that the total number of edges might significantly depend on the degree of our $k+1$ vertices.