8
$\begingroup$

The situation is as follows: assume we have a sequence of simple weighted graphs $(G_n)_{n\in\Bbb{N}}$. For the terminology that follows I refer to Limits of dense graph sequences by László Lovász and Balázs Szegedy. Let us suppose that $(G_n)_{n}$ is convergent. The limit object, as I understand it correctly, is going to be a graphon, i.e., a symmetric measurable function $W:[0,1]^2\to[0,1]$. To such a graphon I can associate a random graph.

My question: Is it possible that a graphon $W$ gives rise to an ordinary (infinite) graph $G$ which is not a random graph, i.e., are there conditions on $W$ or the sequence $(G_n)_n$ such that I can construct one graph out of it (maybe up to isomorphisms)? If so, what are the conditions and are there any references? I hope I am clear enough about this question? Looking forward hearing from you. Best regards.

Improve this question
$\endgroup$
2
  • $\begingroup$ Recall that the way you view a finite graph on $n$ vertices as a graphon is by drawing an $n \times n$ grid on $[0,1] \times [0,1]$ and filling the value of the adjacency matrix (either zero or one) in each square. Unfortunately, I don't think there's a way to do something analogous for infinite graphs... $\endgroup$
    – Sam Hopkins
    Commented Dec 13, 2019 at 15:26
  • 1
    $\begingroup$ Just a comment: If you are interested in bounded degree graphs, then there is a different limit theory for that, with different limit objects called graphings. Unfortunately, the theory it is less well understood, though. Take a look at Part 4 of Lovasz's book web.cs.elte.hu/~lovasz/bookxx/hombook-almost.final.pdf $\endgroup$
    – Jon Noel
    Commented Dec 18, 2019 at 21:54

1 Answer 1

Reset to default
2
$\begingroup$

Given a graphon, you can build a sequence of random graphs on $n$ vertices converging to it by sampling $n$ numbers in the interval, and connecting them independently with probability given by the graphon. You can do this construction with a countably infinite number of vertices as well.

A relevant fact is that for the constant graphons $W=p$ (for $p>0$), the random graph you get this way is the infinite Erdos-Renyi graph, also called Rado graph. These random graphs are actually not random: they are all isomorphic to each other with probability $1$ (and they also don't depend on $p$).

It seems to me that the forward backward argument showing almost sure uniqueness of the Rado graph extends to infinite random graphs associated by general graphons, but this would need to be checked.

In any case, these infinite random (or not random actually) graphs lose a lot of information compared with the graphons generating them. This is already apparent with constant graphons, as the obtained infinite graph doesn't depend on the value $p$ of the graphon. This relates to the fact that there's no canonical probability measure on infinite sets: looking only at infinite graphs one loses the notion of density.

Improve this answer
$\endgroup$
7
  • $\begingroup$ So you're talking about generating a random graph on countably infinitely-many vertices according to the probability distribution the graphon defines? $\endgroup$
    – Sam Hopkins
    Commented Dec 13, 2019 at 20:22
  • $\begingroup$ yes, indeed. right. (need at least 12 characters sry) $\endgroup$
    – alesia
    Commented Dec 13, 2019 at 20:23
  • $\begingroup$ And if you restrict yourself to locally finite graphs as limit objects of finite graphs? $\endgroup$
    – Douglas W.
    Commented Dec 14, 2019 at 9:35
  • $\begingroup$ @DouglasW.: no, the Rado graph is far from locally finite. Every vertex has infinite degree. $\endgroup$
    – Sam Hopkins
    Commented Dec 14, 2019 at 15:45
  • $\begingroup$ @DouglasW. If the limit has uniformly bounded vertex degree then the corresponding graphon is zero. I also think the infinite random graph produced by a non zero graphon cannot have locally finite degree, but I'm not sure $\endgroup$
    – alesia
    Commented Dec 14, 2019 at 16:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .