1
$\begingroup$

On a random graph $G_{n,p}$, I want to know the probability that some subset of verticies is degree one. Take it to be the verticies $A = \{1,2,\dots,k\}$.

My approach for this is to notice that if they are all degree one, then there must be an even number of verticies in $A$ that all pair with one another, and the rest of the verticies that don't pair within another vertex in $A$ must connect to exactly one vertex in $[n] - A$.

I them sum over the probability of even numbers $2j\leq k$ such that the $2j$ verticies all pair with one another and nothing else, and the $k-2j$ verticies all connect to exactly one vertex in $[n]-A$ and nothing else.

I want to know if I'm missing anything, or if this is a valid approach.

$\endgroup$
  • $\begingroup$ What does that mean: subset of verticies is degree one. $\endgroup$ – Maria Mazur Apr 6 at 16:07
  • $\begingroup$ @MariaMazur Presumably, that all the vertices in that subset are degree one, but don't nitpick. $\endgroup$ – Misha Lavrov Apr 6 at 16:13
1
$\begingroup$

This is valid, especially if you're trying to compute the exact probability. (You should also, if you're not doing so already, include a factor for the number of ways to choose $j$ edges between $k$ vertices.)

If the random graph is sparse (which it ought to be: for $p \gg \frac{\log n}{n}$, we don't get any degree-one vertices with high probability) and $A$ is not too large, then looking at edges inside $A$ is more work than you need to do, when all you want is an asymptotic probability.

The probability that there are any edges inside $A$ is at most $\binom{|A|}{2}p$. When this is a $o(1)$ term, we can ignore it, and assume $A$ is independent. This makes the rest of the calculation much simpler, because you can just multiply the probabilities together for each vertex in $A$.

If you are later planning to sum over all choices of $A$, you do have to say a bit more than "this is a $o(1)$ term" because there are $O(n^{|A|})$ such choices. However, even then, the case where $A$ is independent dominates all other cases: when $A$ is independent, you get to choose $O(n^{|A|})$ neighbors for the degree $1$ vertices of $A$, and when $A$ contains $j>0$ edges, you only get to choose $O(n^{|A|-2j})$ neighbors.

$\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.