2
$\begingroup$

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}}}$$

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – fblundun
    Mar 20 at 19:05
  • $\begingroup$ @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. $\endgroup$
    – user113823
    Mar 20 at 19:22
  • $\begingroup$ 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. $\endgroup$
    – fblundun
    Mar 20 at 19:44
  • $\begingroup$ @fblundun And whence have you taken the assertion in your first comment that larger $k$ results in a smaller probability ? $\endgroup$
    – user113823
    Mar 20 at 19:54
  • $\begingroup$ 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. $\endgroup$
    – fblundun
    Mar 20 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.