I was reading a bit in the book High-dimensional probability theory by Roman Vershynin and I was trying to do Exercise 2.4.2 and I do think I still have some misunderstandings regarding the statement of the exercise even.
Let me first restate the preceding Proposition 2.4.1:
There is an absolute constant $C$ such that the following holds. Consider a random graph $G \sim G(n, p)$ with expected degree satisfying $d \geq C \log n$. Then, with high probability (for example, $0.9$), all vertices of $G$ have degrees between $0.9d$ and $1.1d$.
So here I read the statement as that we first fix some $n, p$ and then there exists some constant $C$ (possibly depending on $n$ and $p$) and the rest of statement follows here. Is this true?
After the proof, the author states the following assumption and afterwards exercise 2.4.2 which I am trying to do:
Sparser graphs, those for which $d = o(\log n)$, are no longer almost regular, but there are still useful bounds on their degrees. The following series of exercise makes these claims clear. In all of them, we shall assume that the graph size $n$ grows to infinity, but we don't assume the connection probability $p$ to be constant in $n$.
Consider a random Graph $G \sim G(n, p)$ with expected degres $d = O (\log n)$. Show that with high probability (say, $0.9$), all vertices of $G$ have degrees $O (\log n)$.
First of all, I find the expression "Consider a random Graph $G$ ..." weird since this basically states that we pick one graph (and hence one $n$?) and how does this align with $n$ tending to infinity. Secondly, I was wondering what exactly the statement, which is supposed to be proven, is. Is it something like $$ \mathbb{P} (\forall i \leq n \; \exists C_i : d_i \leq C_i \log n) \geq 0.9 \, , $$ which would have been roughly my guess if it were not for the $n$ tending to infinity. Because, this doesn't really make sense for a fixed $n$ since then there would always exist such (large enough) constants $C_i$ making the desired inequality true.
My best guess might be something in the direction of $$ \mathbb{P} (\forall n \; \forall i \leq n \; \exists C_i : d_i^n \leq C_i \log n) \geq 0.9 \, . $$ But then again I am confused, for example, about the roles of th $C_i$ since these were previously fixed to the $i$-th vertex which doesn't work anymore if $n$ and thus $G$ is not fixed anymore.
I guess what might work is this $$ \mathbb{P} (\forall i \; \exists C_i \; \forall n \geq i : d_i^n \leq C_i \log n) \geq 0.9 \, . $$ where $d_i^n$ would be just the $i$-th vertex of the random graph $G_n$ but then again I am not sure if this is the right formalization of the statement that with high probability all vertices of $G$ have degrees $O (\log n)$.
Can you help me with my misunderstandings?
Thank you!
Edit:
I am trying to check whether I really understood @Misha Lavrov's answer. So if I would try to formalize the statement of the exercise with the actual meaning of "with high probability" (instead of $0.9$) this would be something like the following:
Let $p_n$ be $O (\frac{\log n}{n - 1})$, i.e. there exists a constant $C_1$ and $n_0$ such that $p_n \leq C_1 \frac{\log n}{n - 1}$ is fulfilled for all $n \geq n_0$. Consider random graphs $G \sim G(n, p_n)$. Then for all $\epsilon > 0$, there is a constant $C_2$ and $N_0$ such that for all $n \geq N_0$ $$ \mathbb{P}[ \forall i, \deg(v_i) \leq C_2 \log n ] \geq 1 - \epsilon. $$
Is this correct?
In particular, I assumed that $C_2$ is also allowed to depend on $\epsilon$. Also, I am still unsure at what point the random graphs $G(n, p_n)$ are supposed to be introduced. I guess one would choose them at the earliest point (?), i.e. after choosing a sequence $p_n$.
You should read sentences in order. If a paragraph begins by saying "There is an absolute constant $C$ such that the following holds" then the constant $C$ is absolute: it does not depend on the values of variables that are not mentioned until later in the paragraph.
The expected degree $d$ is always equal to $(n-1)p$. So, the statement is:
The "probability of $0.9$" is bad phrasing on the author's part, but that's irrelevant for now; I'll leave it until the end.
The exercise that comes later is trickier to understand, because statements with multiple big-$O$ expressions are often tricky to understand. Each of those big-$O$ expressions is hiding a quantifier, and you need some experience with the topic to know what the reasonable quantifiers are.
The claim
first of all has to be understood as a statement about limiting tendencies as $n \to \infty$, because $O(\log n)$ is only meaningful when $n \to \infty$. As mentioned in the preceding paragraph, picking a probability $p$ means picking a function $p(n)$.
We should read this claim as follows:
Here, the constant $C_2$ can depend on $C_1$, but of course it must not depend on $n$.
In any case, none of the quantifiers on these variables should be inside the probability. The probability should only have one quantifier: the quantifier over the vertices. That is, we want $$\Pr[\forall i, \deg(v_i) \le C_2 \log n] \ge 0.9.$$ (But we want this statement to hold for all sufficiently large $n$.)
As a final note, the use of "with high probability" to mean "with probability at least $0.9$" is bad, because "with high probability" already has a different technical meaning in the study of random graphs: it means "with probability tending to $1$ as $n \to \infty$". In these examples, a "with high probability" statement also holds in this sense of the phrase.