Meaning of Choosing an Edge Incident with the Root of An Isomorphism Class of Rooted Graphs

31 Views Asked by At

$\newcommand{\mf}{\mathfrak}$ Let $\mf G^\bullet$ be the collection of all the isomorphism classes of finite rooted graphs.

(An isomorphism of two rooted grpahs $(G, u)$ and $(H, v)$ is a bijection $f:V(G)\to V(H)$ such that $f(u)=f(v)$ and $f(x)f(y)$ is an edge in $H$ if and only if $xy$ is an edge in $G$.)

Now let $C$ be a particular element of $\mf G^\bullet$. I am unable to understand the meaning of the following phrase:

Choose an edge incident with the root of $C$.

My problem is that $C$ is not a rooted graph but an isomorphism class of rooted graphs. I could choose a representative of $C$ and then choose an edge incident with the root of the representative. But how do I say that the chosen edge is an edge incident with the root of $C$. The problem is that there may be more than one isomorphism between two representatives of $C$. So once an edge of a particular representative is chosen, there is no unique way to get an edge in any other representative.

Here is the context where the above came up:

On pg. 340 of Lovasz's Large Netwroks and Graph Limits, the author writes the following (not paraphrasing):

Let $D$ be a positive integer. Let $\mf G^\bullet$ be the set of isomorphism classes of all the countable rooted graphs whose degrees are bounded by $D$. There is a certian $\sigma$-algebra $\mf U$ on $\mf G^\bullet$ (The exact descriptiotn of this $\sigma$-algebra is not important for the purpose of this post). Let $\sigma^*$ be a probability distribution on $\mf G^\bullet$.

Choose a rooted graph $H$ from $\mf G^\bullet$ according to $\sigma^*$ and then choose a uniform random edge incident with the root.

This last line is the reason why I asked the question.

1

There are 1 best solutions below

0
On BEST ANSWER

Your thought is exactly correct. When it is said to pick an isomorphism class $C$, you should immediately think that you're picking a representative of $C$. The reason that they're grouped into isomorphism classes is that you're going to have problems describing the $\sigma$-algebra if you considered labelled graphs.