What is the limit of a sequence of graphs?? | Benjamini-Schramm Convergence
Vložit
- čas přidán 12. 06. 2024
- This is an introduction to the mathematical concept of Benjamini-Schramm convergence, which is a type of graph limit theory which works well for sparse graphs. We hope that most of it is understandable by a wide audience with some mathematical background (including some prior exposure to graph theory), but to get the most out of the video it is helpful to know some probability theory and general topology.
Made by: Caio Alves, Aranka Hrušková, and Vilas Winstein.
Music: Jiná Geometrie (Different Geometry), composed by Peter Graham and performed by Aranka Hrušková.
Animations made in Blender and Mathematica (with the MaTeX package). Edited in kdenlive.
References:
Benjamini, I., & Schramm, O. (2011). Recurrence of distributional limits of finite planar graphs.
In Selected Works of Oded Schramm (pp. 533-545). Springer, New York, NY.
Curien, N. (2017). Random Graphs the local convergence point of view
www.imo.universite-paris-sacl...
Lovász, L. (2012). Large networks and graph limits.
Vol. 60. American Mathematical Soc., 2012.
Absolutely mindblowing. You need quite a bit of prerequisites to get behind every step of your constuctiom of the local convergence - graph limit theorem, but it's a joy to watch and listen to this explanation. Thank you!
It stroke me as a nice coincidence that because of a collaboration I just a few weeks ago read the paper of Benjamini and Schramm. So I was continuously nodding along watching this and checking whether my understanding was correct :D
This is a very comfortable level of depth that I would enjoy to see in more videos. I hope there will be more.
Randomly got this channel recommended and such a beautiful work. Please keep making them. This channel surely will grow if the content is this good.
Discovering this as I'm watching the SoME #1 playlist. So far one of the most interesting videos. Can't wait for the next one (although I definitely need to rewatch this one and work on it a bit!).
This is a great video! Really construction/definition, comfortable length, and a really good balance of accessibility and mathematical detail. So many math youtube videos and interesting but informal/nondetailed, or too detailed and terse. This found a sweet spot!
Count me subbed and looking forward to more!
I'm seriously rooting for this channel to grow! Please don't stop what you're doing. Absolutely love this ❤️
Please make more videos! 😍
This was incredibly interesting and well illustrated!
Didn't expect to ever see the name Benjamini and Schramm on CZcams! Great work.
As a computer network engineer I always get excited when I have an opportunity to expand my understanding of graph theory. Very well done! Narration sounds FANTASTIC! (despite a few mic pops), the visual style is clean and easy to read, and all points demonstrated fit together nicely. Outstanding work! It blows my mind that I can access this extremely high quality content for basically free. Thank you, and very well done!
Interesting topic and great video!
I have a question: Doesn't the infinite one-ended path also satisfy the definition of being the limit of the paths of increasing lengths? For every fixed r, the probability of seeing the vertex of degree one in the r-ball goes to zero when n goes to infinity, but zero is also the probability of seeing the vertex of degree one in the infinite one-ended path. What am I missing?
Good question. Here’s an explanation, I hope it makes sense.
The limit object is always a random rooted graph g*.
Let’s suppose that with some positive probability p, the underlying graph of g* is isomorphic to the one-way infinite path (ignoring the root).
Then there is some m and some positive probability q that g* equals the one-way infinite path, rooted at the mth vertex away from the vertex of degree one.
Thus, the (m+1)-ball in g* has probability at least q of containing the vertex of degree one, i.e. with probability at least q, the (m+1)-ball in g* will not be a length-(2(m+1)+1) path, rooted in the middle.
However, the probability that the (m+1)-ball in the uniformly randomly rooted path of length n is not a length-(2(m+1)+1) path, rooted in the middle, goes to 0, which is strictly less than q.
@@SpectralCollective That makes sense! Thank you!
Very very nice video! Super clear and inspiring. Look forward to seeing more clips like this!
Absolutely amazing, i can not wait to see more from you
Beautiful math, really well explained! Such a cool interaction of combinatorics, analysis, and topology
Great job! Looking forward to the next video!
Very detailed and enjoyable, nice work!
Well done and excellent detail. Thanks!
Really great visualizations! Every time you brought up some new terminology or piece of notation I immediately thought "Wait, what, no, I can't understand this, I'm not a graph theorist/topologist/algebraist!"
And then you would show me a picture, and I'd immediately understand.
(Also damn this video is just pretty! It explains the topic well but it's a joy to look at)
Absolutely beautiful video!
Great video! When I saw the title, I was immediately thinking of defining it using a colimit in the category of graphs. If you pick certain inclusions of the graphs into the next one, you could define the limit of the sequence by taking the colimit. However, this depends on the inclusions. If we take the inclusions from top to bottom in the following examples, we get
0 0
0-0 0-0
0-0-0 0-0-0
: :
0-0-0-0-... ...-0-0-0-0-0-...
However in case of the n-cycle graph, this doesn't work because there is no inclusion Cn -> Cn+1 :(
I was also thinking about what would happen if you didn't start with a uniform distribution of pointed graphs. For example, if you choose with probability 1 the path of length n with the root at one of the endpoints. I think you will get the one-way infinite path in this way.
Good point about the uniform distribution, you’re right that this isn’t the only way to do it. In fact, as Prokhorov’s theorem shows, you can take any sequence of random rooted graphs and obtain a limit random rooted graph.
We can identify a rooted graph g* with a RRG which is concentrated on g*, and with this identification you’re right that a sequence of paths rooted at an endpoint converges to a one-way infinite path. But, if you’re given an unrooted finite graph, the most canonical RRG is uniformly rooted.
Also, I think (but am not sure) that the convergence of rooted graphs I just described encapsulates what you mentioned about (co)limits in the category of graphs. You just have to pick some vertex of the first graph in the sequence to be the root of all the graphs in the sequence.
Absolutely wonderful. Thank you.
Thanks for the video. Very much needed.
Absolutely bananas - this is going way over my head right now, but I'm subscribed. Will have another watch
Its a cool subject, basically everything seems to be variables
Great video!
I couldn't resist clicking this
This is amazing !
Category theory gives an interesting definition of the (co)limit of a particular diagram (here, the nodes of the diagram are graphs and the arrows would be graph morphisms).
For example, it is rather clear that the colimit of the sequence of those linear graphs with prefix inclusion (ie. you're adding vertices to the right of the previous, so to speak) is the adjacency graph of the natural numbers, whereas if you choose a different kind of inclusion you'll get the adjacency graph for integers.
For the n-cycle graphs, there isn't an obvious inclusion between (n) and (m) cycles. But, there is an map from the naturals adjacency graph into each of them given by wrapping it around the circle. If we instead consider the diagram that includes an n-cycle into only the m-cycles that are factors of n, I'd bet its limit (not colimit this time) should be some infinite linear graph.
I'm not a graph theorist, so I don't know how useful any of this would be, but hey
Wonderful!!
Great video! Thank you!
My attempt for the limit graph in question.
In the n-th step we have 3 * 2^(n-1) leaves and the number of inside nodes is the sum of leaves of all previous steps which is 3 * 2^(n-1) - 2. So the probability of root to be leaf or inside node is 1/2.
If the root is leaf and we label nodes starting from zero (root) we get a line with node labels 2^k (1, 2, 4, 8...) and each of theese nodes is a root of a binary tree with k leaves.
I'm not sure about limit graph with the root as inside node, but I'd suggest that it is just the infinite orginal graph wihout leaves.
You’re right that the root will be a leaf with probability 1/2, and in that case you’ve got the correct overall rooted graph shape: it’s a one-way infinite path where each node is the root of a different finite binary tree, with depth n at the nth node along the path.
As for the case where the root is an inside node, think about the probability that the root is one step away from a leaf...
Ah yeah! So, the probability of root being one step away from leaf is 1/4, two steps away is 1/8 and so on.
And the limit graph which has probability 1/2^k will be a line with two binary trees with depth 2^(k-2) on the first node, one binary tree with depth 2^(k-1) on the second node, 2^k on the third and so on.
And it seems like all these graphs are actually isomorphic to the leaf-rooted graph.
@@seriy21 Exactly, the limit will be concentrated on a single (unrooted) graph, but the root will be chosen according to the probability distribution you described. However, these are all different when considered as *rooted* graphs, so the limit object will be a random rooted graph which can take infinitely many different values, each with positive probability.
@@SpectralCollective You mean positive probability *density*? You cannot have infinitely many outcomes with positive probability. Unless you calculate probabilities using infinitesimals...
@@viliml2763 no, I mean positive probability. The probability of the nth outcome is 1/2^n, and this works because the series 1/2 + 1/4 + 1/8 + ... converges to 1.
A minor remark for 13:39. All compact metric spaces are separable so one does not need to hypothesize separability in the statement of Prokhorov's theorem.
Good video!
4:00 Or perhaps the limit should be a pair of disconnected infinite one-way paths plus an infinite collection of infinite two-way paths that are also disconnected from the others -- like the two endpoints of a segment of the long line plus all the interior points.
I'm not sure I understand... are you saying the limit should be some sort of "long path graph" ?
great !
Well done video! Would Solid State physics or Crystallography be a special case of connected graphs? The interactions between an atom in a crystal lattice with its neighbors as a function of distance is an important concern in Solid State physics.
The fraction displayed is a typo and the real pi approximation is 355/113
I don't fully understand how I could use this. Maybe with neural networks 🤔. I really enjoyed the video 😄
Is it your research interest? It’s interesting topic!
Yes, it is a part of the area that we are working in.
Very Nice!
Ist the limit to the graph at 12:15 a "Tree" where you can't see the "Roots" or the "leafs"??
I am lacking the proper terminology/ the graph theory background, but this would be my intuition.
It's a bit more complicated than that. We're about to publish another video which might help you answer the question.
👏🏼👏🏼👏🏼👏🏼👏🏼
8:30 Did not quite capture the point being made here as it was lost in the notation which was unfamiliar to me. Great video overall
One thing that bugs me the first time I see definition on 8:40: talking about 'the' limit only makes sense if there is only one / one-class of answer to the 'limit' question.
The explanation kind of just assumed there will only one graph as the limit.
This is a good point! And there are limit theories where one sequence can converge to multiple different limits. However, in the context of this video, it can be shown that limits must be unique. Keep in mind, though, that a limit is not just one graph, but is rather a probability distribution on rooted graphs (i.e. a random rooted graph).
this is what I would like to do at my job
You are so lucky to be happy.
> press subscribe.
> see there is only one video
> sad
We are working on more, don’t worry!
1:00 335/113 is a terrible approximation of pi, being as it's 2.964...
Yep that was a typo. It should have been 355/113
Did you mean the approximation of pi is 355/113 instead of 335/113?
Wow, good eye! Yes, that was a typo.
Thats it
Or the wolfram physics proyect
Typo alarm: not 335 but 355 / 113 equals about pi. Around 10000 times better than 22/7, but not as useful for hand-calculated calc checks.
Yeah, I still like 314/100 more :d
is the limit the graph
0100
1011
0100
0100
with 2/3 of the area being in the forked part and 1/3 being in the stem?
No, even though you are correct in that lots of the probability will be concentrated in leaves (albeit less than 2/3), so this is a step in the right direction! Note that in the graph you suggest, every vertex is in distance at most 1 from a leaf, but in the balls, an asymptotically positive proportion of vertices will be further apart from a leaf, so you should try to make your limit reflect this.
pi is better to be thought of as the closest number in a sequence of approximations, that *cannot* be achieved
Hence it is "limit"
And that explains weird stuff about real numbers too, such as 0.9999... = 1
kind of hard to follow as presented. one thing that would have helped immensely is if you had started off with some definitions, on the assumption that not all viewers would be familiar with graph theory and associated terminology. for instance, you talk a lot about "sparse graphs". this would make a lot more sense if I knew what a "sparse graph" was.
Thanks for the feedback! We created this video with the assumption that the viewer has some background in graph theory. There are plenty of great videos on CZcams which give the basics, so we didn't want to repeat all of that.
By the way, there is no such thing as a "sparse graph." In fact, "sparse" is an adjective that should be applied to a sequence of graphs, not just a single graph. For this video, our definition of a "sparse" sequence of graphs is that there is some bound D on the degree of any vertex in any graph of the sequence. We say "sparse graph limits" because we construct a graph limit theory which works for sparse sequences of graphs, and the word "sparse" just comes along as a qualitative descriptor of the type of graph limit we're constructing.
You should talk about graph neural networks
Great video!
Well done video! Would Solid State physics or Crystallography be a special case of connected graphs? The interactions between an atom in a crystal lattice with its neighbors as a function of distance is an important concern in Solid State physics.