Probability a given path occurs in a uniformly random simple graph

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.

• So you are first sampling a degree sequence $(D_1, D_2, \dots, D_n)$ by taking $n$ iid samples from a distribution with mean $\mu$, then (presumably) conditioning on it being a degree sequence, then uniformly sampling a realization of that degree sequence? Commented Jun 11, 2021 at 3:54
• Yes. One must condition the degrees to be valid. Commented Jun 11, 2021 at 13:06

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.

• Thanks. Doesn't this suggest the answer is yes though since the configuration model bound you give is even stronger? Commented Jun 11, 2021 at 21:33
• Whoops, I did the hard work, but then compared the two bounds incorrectly. It's less exciting this way, since I only looked at a special case. Commented Jun 11, 2021 at 21:44
• @MatthewJunge I've updated my answer to look at a different example where we get a worse result. Commented Jun 13, 2021 at 19:33
• Great example. I am convinced that $(\mathbb E [ D(D-1)] / (\mu n))^k$ is a more likely universal bound, but one that will only hold for $k = o(n)$. This points us in the right direction and no doubt will save us a lot of time. Thank you very much. Commented Jun 14, 2021 at 13:40
• Are there any references that you think might show some techniques for bounding the probability of a path being present along $1,2,\cdots,k$? It seems that the expected number of such paths is $\mathbb E \frac{ [ D_1 \left(\prod_{i=2}^{k-2} D_i (D_i-1) \right) D_k ] }{\prod_{i=1}^k (S_n - 2i) }$ with $S_n = \sum_1^n D_i$. I imagine there are standard ways to deal with the dependence between the numerator and denominator here, but I am struggling to get rigorous bounds. Commented Jun 21, 2021 at 14:09