# 0-1 laws in random graphs: probability $\beta$ is large if $k$ is large

How has the author derived here

on the page 3 in the context of random graphs and 0-1 laws

that $$\beta$$ is large if $$k\geq ((\frac{2}{\alpha})\log n)^{\frac{1}{2}}$$ ?

What I did is this:

I've substituted $$1$$ for $$\beta$$ in $$\frac{k\cdot \beta}{n}\leq\frac{1}{k^{\alpha \cdot {k\choose 2}}}$$ and I got $$(\alpha \frac{1}{2}\cdot k \cdot (k-1)+1) \leq \log_k n$$ hence approximately $$k\leq (\frac{2}{\alpha} \log_k n)^\frac{1}{2}$$

This is good, but the inequality is reversed unlike the one on the page 3 which is "$$k \geq$$" there which confuses me. Apparently the author considers both inequalities as he says there

the bound for the other direction has the same order of magnitude.

I would like to understand which direction of the inequality is the right one and how this $$\beta$$ largeness follows from $$\frac{k\cdot \beta}{n}\leq\frac{1}{k^{\alpha \cdot {k\choose 2}}}$$

• Maybe it's a mistake? If I understand correctly $\alpha$ and $n$ are both positive, which would mean that as $k$ increases, the given upper bound on the probability increases, which contradicts the claim that a larger $k$ results in a smaller probability. Mar 20 at 19:05
• @fblundun That's what I think too. But don't you have a typo in your comment too? you write [...]the given upper bound of the probability increases but the r.h.s. with increased $k$ decreases. It's mind boggling anyway. Mar 20 at 19:22
• I don't think there's a typo in my comment... I'm saying that as $k$ increases, $(1 - (\frac{1}{k^\alpha})^{k \choose 2})^\frac n k$ (which is the upper bound on the probability in question) increases. Mar 20 at 19:44
• @fblundun And whence have you taken the assertion in your first comment that larger $k$ results in a smaller probability ? Mar 20 at 19:54
• I'm not saying that the paper is claiming there's a monotonic relationship between $k$ and the probability, just that the paper is claiming to deduce from the upper bound on the probability that for all sufficiently large $k$, the probability is "small". But I think that as $k \to \infty$, the upper bound $\to 1$, so I don't see how that deduction is possible. Mar 20 at 20:42