Unfamiliar notations

#1

I was recently skimming a paper regarding disjoint set products and vanishing average functions - I’m not sure if it has much value, but I found a notation and concept that are both unfamiliar to me. This may just be me lacking in graph theory knowledge.

Given p \in (0,1), a graph sequence \{ G_n \}^\infin_{n=1} is called p-quasi-random, if, in the limit, it behaves similarly to the sequence of Erdős–Rényi random graphs \boldsymbol{G(| V(G_n) |, p)}.

My questions here are:

  1. Is it weird to be talking about the limit of a sequence of graphs?
  2. My uneducated parsing of this is V(G_n) is the set of vertices in G_n, and | \mathrm{ \ thing \ } | is pretty ubiquitously “how big is thing”. But what’s the outer G doing? This might be something super niche and only related to Erdős–Rényi random graphs, in which case I don’t really care.

“RTFM” is an acceptable response, but at least mention a suitable “M” if that’s your answer. Also this thread could be used/updated for more general math notation questions.

#2

Yeah V(G_n) is the set of vertices in G_n and |V(G_n)| is the number of these vertices.

G(|V(G_n)|, p) is the Erdos-Renyi random graph generated with |V(G_n)| vertices and a probability p of adding an edge between any two vertices.

The limit of a sequence of graphs is interesting… Here is a simple paper I just found on it. It briefly mentions the limit of Erdos-Renyi random graphs specifically.

You define a “density” function d(G, H) between graphs G and H as the probability of a randomly sampled subgraph of G with |H| vertices being be isomorphic to H. A sequence of graphs G_n converges if d(H, G_n) \rightarrow 0 for every graph H. Weird.

They define an object called a graphon to be the limit of such a convergent sequence. They show a convergent sequence of graphs converges to a graphon, all graphons are the limits of some convergent sequence of graphs, and if two graphons are the limit of some sequence, they are weakly isomorphic (this is a weak sense of the uniqueness of limits).

The graphon object is pretty interesting. The paper is understandable so it might be worth reading some of if you’re interested.

#3

I’ll likely skim through it at least. Graph theory is definitely widely applicable, but I am definitely a novice in that area of mathematics so I hesitate to try and learn too much about what seems to be a niche subgenre.

I’m tempted to devote my life to research so I could have the chance to name something like “graphon”.

I was about to ask what makes graphs isomorphic, but luckily I remembered that I have at least a rudimentary understanding of thinigs and was capable of answering myself through Wikipedia. It’s been a while since I’ve done anything very math-intensive…

1 Like