# Interpretation of probability statements in Nina Zubrilina's paper

In the paper Zubrilina - Asymptotic behavior of the edge metric dimension of the random graph (MR, the main result is

$$\operatorname{edim}(G(n,p)) \leq (1+o(1))\frac{4 \log n}{\log(1/q)},$$ where $$q= 1-2p(1-p)^2(2-p)$$.

My first question is how should I interpret the result, what is $$\operatorname{edim}$$ of random graph. Should I interpret it as $$\mathbb{P}\left[\operatorname{edim}(G(n,p)) \leq (1+o(1))\frac{4 \log n}{\log(1/q)}\right] \rightarrow 1 \text{ as n \rightarrow \infty?}$$

My second question is concerned with how to interpret lemma 2.2, it is stated that

Let $$G=G(n,p)$$ be the random graph. Let $$V,E$$ denote the vertex and edge sets. Let $$\omega \in \{1,\dotsc,n\}$$ be such that for any two distinct edges $$e_1$$, $$e_2$$ of $$E$$, a uniformly random subset $$W \subset V$$ of size $$\omega$$ satisfies $$\mathbb{P}( \text{W does not distinguish e_1, e_2}) \leq 1/n^4p^2.$$ Then $$\operatorname{edim}(G) \leq \omega.$$

So, firstly how should I understand $$E$$ as subset of a random graph, and how can I fix two edges of this seemingly random set by saying "for any two distinct edges $$e_1,e_2 \in E$$". I am confused about how I interpret such statement. Can any one clarify them?

• You should define terms in your question (like $\mathrm{edim}$, which is surely not a ubiquitous notion). Jun 25 '20 at 15:51
• Also, you should link to your MSE question to avoid duplication of effort. Anyways, it seems your concerns are about basic shorthands when dealing with random objects, which are standard but I agree can be confusing when not spelled out. Jun 25 '20 at 16:02
• The original link went to a page with only generic content for me ("0 Articles Found"). I pasted in the DOI link, which takes me to an articles-to-appear page which doesn't seem to list Zubrilina's. So I pasted in the name of the article and a link to the MR. I hope that was all all right. Apr 21 at 23:20

I just skimmed the paper. When she writes

$$\mathrm{edim}(G(n,p)) \leq (1+o(1))\frac{4 \log n}{\log(1/q)}$$, where $$q= 1-2p(1-p)^2(2-p)$$

she means this inequality holds "asymptotically almost surely", i.e., the probability that this inequality holds goes to 1 as $$n\to \infty$$ (note: this is for a fixed $$p$$). This matches what you thought, and it's clear from her use of "a.a.s" in Lemma 2.3 and in Section 3. I previously misread your interpretation to think you were suggesting the result was a bound on $$P(edim(G(n,p)))$$ which of course makes no sense.

Similarly, in Lemma 2.2, edim$$(G)$$ refers to the family of graphs, and it's enough to prove the inequality holds a.a.s. as $$n\to \infty$$. So, when she says "Let $$G = G(n,p)$$ be the random graph" she is saying $$G$$ represents the family of graphs drawn from this random variable. That's confirmed in the proof, where she talks about the expected size of the edge set, $$E$$ -- it's a random variable. I think the definition of $$\omega$$ is fine as stated. She's choosing a number to guarantee a probabilistic inequality. It would be like if I said, "Consider an $$n$$-sided die, and let $$n$$ be a number such that the probability of rolling two consecutive 1s is less than 0.01." That statement does define a number. Of course, there is a probability on a given draw of $$G = G(n,p)$$ that you get a graph with no edges, or only 1 edge, and maybe she could have spelled out how to handle those cases. But I think they are vacuous, because the definition of "edge metric dimension" says "for any distinct $$e_1,e_2\in E$$". Also, the probability of this situation occurring goes to zero as $$n\to \infty$$.

• I don't understand what you mean by "the edge metric dimension of the family of random graphs." This notion is just defined for a graph. I think that mahmoud's interpretation of the inequality holding a.a.s. is correct. For instance, the paper cites arxiv.org/abs/1208.3801 which proves a similar thing but for metric dimension instead of edge metric dimension (and states the a.a.s. bit in their theorem more clearly). Jun 25 '20 at 16:19
• @SamHopkins: I think you're right. I'll edit. Jun 25 '20 at 16:32
• The formal interpretation of Lemma 2.2 should also involve some kind of a.a.s. statement, but there's a little more unwinding to do there. Jun 25 '20 at 16:36
• I edited a second time. I just jumped the gun on the first edit. Jun 25 '20 at 16:44
• For the first case: I think that for many readers, it would still be unclear what it means to say that "the probability that $X_n\leq (1+o(1))f(n)$ goes to $1$ as $n\to\infty$". The "$o()$" notation already includes an $n\to\infty$ limit, which makes it hard to understand that statement. To interpret it really clearly one could write: for any $\epsilon>0$, the probability that $X_n\leq (1+\epsilon)f(n)$ goes to $1$ as $n\to\infty$. Jun 26 '20 at 9:45