I asked this question on Math.stackexchange but got no answer.

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?

  • 1
    $\begingroup$ You should define terms in your question (like $\mathrm{edim}$, which is surely not a ubiquitous notion). $\endgroup$ Jun 25 '20 at 15:51
  • 3
    $\begingroup$ 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. $\endgroup$ Jun 25 '20 at 16:02
  • $\begingroup$ 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. $\endgroup$
    – LSpice
    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$.

  • $\begingroup$ 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). $\endgroup$ Jun 25 '20 at 16:19
  • $\begingroup$ @SamHopkins: I think you're right. I'll edit. $\endgroup$ Jun 25 '20 at 16:32
  • $\begingroup$ 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. $\endgroup$ Jun 25 '20 at 16:36
  • $\begingroup$ I edited a second time. I just jumped the gun on the first edit. $\endgroup$ Jun 25 '20 at 16:44
  • 1
    $\begingroup$ 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$. $\endgroup$ Jun 26 '20 at 9:45

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.