Find a bound for the probability that a random simple graph with p = 1/2 + \alpha does not contain a Hamilton cycle

62 Views Asked by At

So I had a reasonable seeming solution using a Chernoff bound, but then realized I'd forgotten to add 1 when calculating my Delta and now my solution just seems off, any input would be welcome.

Let Xi be the degree of node i, $E[X_i] = (n-1)(\frac12 + \alpha)$

Chernoff: $P[Xi <= (1 + \delta)E[X_i] <= e^{-E[X_i]\delta^2/3}$

$(1+\delta)(n-1)(\frac12 + \alpha) = \frac n2 $ $\delta = \frac {-n}{2(n-1)(1/2 + \alpha)} + 1 \approx \frac{-1}{2(\frac12 + \alpha)} =\frac{2\alpha}{(2\alpha+1)}$

So using this gives me a bound of $e^{(-(n-1)(\frac12 + \alpha)(\frac{2\alpha}{(2\alpha+1)})^2/3} = e^{-(n-1)(\frac{2\alpha^2}{(2\alpha + 1)})/3}$ Now with union bound the probability of not all nodes having degree >= $\frac12$ is $ne^{-(n-1)(\frac{2\alpha^2}{(2\alpha + 1)})/3}$, and from the contrapositive of Dirac's theorem this represents a bound for the probability of a random graph with $p = \frac12 + \alpha$ not containing a Hamilton cycle.

Now I feel like I must have made a mistake somewhere, since for small $\alpha$ the term $e^{-(n-1)(\frac{2\alpha^2}{(2\alpha + 1)})/3}$ approaches 1, so the probability approaches n, which means it can't be a probability. Any inputs are appreciated thanks

1

There are 1 best solutions below

1
On BEST ANSWER

Your calculation looks reasonable (I didn't check every detail, just the result) and you should not be concerned.

First of all, the union bound gives an upper bound on a probability, but the value it gives does not need to be smaller than $1$. In cases where the union bound gives a value larger than $1$, this just means that it is not telling you anything useful.

For example, suppose I flip $n$ coins, and want to union-bound the probability that at least one coin lands heads. Each coin lands heads with probability $\frac 12$, so the union bound says that the probability that at least one coin lands heads is at most $\frac n2$. Is this a mistake? No, it's a valid upper bound: the probability is $1 - (\frac12)^n$, and $1 - (\frac12)^n < \frac n2$. It's just that the union bound is not the right tool here.

Second, in your case the result is not concerning, and the union bound seems to be doing just fine. For a small but fixed $\alpha$, the constant $(\frac{2\alpha^2}{(2\alpha + 1)})/3$ will be small but positive. For example, when $\alpha = 0.01$, it is a bit over $0.000065$. But this means that you're getting a bound of roughly $n e^{-0.000065n}$, and this is still going to $0$ as $n \to \infty$. Just, you know, very slowly. When $n$ is a million, the bound becomes very small.

(It is true that if, for example, $\alpha = \frac1n$, then $e^{-(n-1)(\frac{2\alpha^2}{(2\alpha + 1)})/3} \to 1$ as $n \to \infty$. But if the edge probability is $\frac12 + \frac1n$, we shouldn't actually expect all the vertices to have degree more than $\frac n2$, so this is not surprising. We need $\alpha$ to be a positive constant for your method to work.)

You should also keep in mind that Dirac's theorem is not a very powerful tool to use here. It works, but if you want better bounds, you'll need better strategies. And if you look around for results on Hamiltonian cycles in random graphs, you see that they appear in $G_{n,p}$ for a much smaller $p$, so you can potentially prove much stronger results for $G_{n,1/2}$.