Theorem: In the limit where they post a countably infinite number of videos, all random math channels are actually the same random math channel. (Proof is left as an exercise for the reader.)
The fact this infinite graph isn't only locally connected makes it really hard to draw or visualize. It's basically a fully connected infinite graph with half the edges missing... so a bunch of the edges are missing but every vertex still has an infinite amount of edges to an infinite amount of vertices.
Even weirder, since it contains a copy of every finite or countable infinite graph. It contains a copy of a infinite fully connected graph and an infinite fully disconnected graph.
Even more trippy, to me, is that P(diameter of this graph = 2) = 1. In fact the expected value of the distance between two distinct vertices seems like it should be 3/2. So cool!
7:54 with subtitles: Remember that you're less lazy than 90% of TH-camrs just by writing subtitles (for which I thank you very much). Also amazing video!
for people who are deaf (i am not) maybe the only thing that would be more helpful is to say "[i am lazy - saying what is on screen]" just so they know they're not missing anything!
There is built-in support for editing auto generated closed captions on youtube after uploading, here is the guide that I found on yt th-cam.com/video/tWbNrm7Jo5c/w-d-xo.html video starts at 1min 6s
To blow some more minds... pause at 14:20 and realize that he never uses the extact 1/2 propability of coin flipping. Only thing needed, is that the propability of being a good vertex needs to be non-zero. So, flipping a coin or roling a dice (1=create edge, 2-6=no edge) will (almost always) construct the same infinite graph. Would be interesting to see how the propabilities behave for finite but huge graphs. Does the limit also go to 1?
I was also interested in whether the chance of two random graphs of size n being isomorphic converges to 1 as n tends to infinity... If you try to work it out head on (ie calculate the probability as a function of n and p) it gets very difficult... Did you figure it out?
@@chalkchalkson5639 It goes to zero as long as n²p and n²(1-p) go to infinity. Two graphs with different numbers of edges can never be isomorphic, which is almost certain as long as the number of edges and the number of missing edges both go to infinity.
@@NoLongerBreathedIn yeah, I guess that makes sense... the number of vertices should be binomially distributed, so in the limit we are talking normal distribution. Then just say that the corresponding integral is smaller than 1*1/(sqrt(2pi)*sigma), substitute sigma=sqrt(np(1-p)) and see that for p(1-p)=/=0 that expression converges to 0. So the integral must converge to 0, too.
Very nice video! To anyone interested in the "Logic" part mentioned at the end, the short version is this: Let's assume we have a collection of finite structures (in our case, all finite graphs - but this also works with the collections of finite ordered sets). If this collection has a few nice properties (here is an example: any two finite graphs can be joined to create a bigger finite graph; the other properties are not much more complicated), then we have an equivalent of the Rado graph. By "equivalent" I mean that it has a property very similar to the killer property, contains a copy of every member of the collection, and is unique (and also many other nice properties). This is called a Fraïssé limit, if you want to look it up.
I love infinite probability stuff. there's an infinite number of random graphs you could end up with that aren't isomorphic to the rado graph, just with probability 0 that you actually make them
Thank you, sir! This was ABSOLUTELY amazing and completely new to me even after studying computer science! Will now go and tell my friends about it ❤️🔥
I saw the isomorphic graph question and my first thought was, "the answer is definitely 0 or 1, but I have no idea which one...you could even say it's a coin flip (pun very much intended)."
14:25 I suspect there's a little more going on maybe. Like, for any U,W, the chance is "0" but really it's like 0^+, an infinitely small positive number. There are definitely cases when adding infinitely many of those 0^+ does not give 0 (I believe the harmonic series for example)
There's a part of this proof that I don't quite understand. You can show that each individual pair of subsets has a 0 chance of not following the killer property. However, there are an infinite amount of these subsets. How can we be sure that doing an infinite sum of these "0"s doesn't yield some sort of limit or something?
@@phanirithvij Because it's a product, not a sum. You multiply by a number between 0 and 1, more and more times, you keep knocking it down to zero. I suppose you could come up with a story about Hilbert's Infinite Hotel running a sale...
@@phanirithvij It's not a sum of infinite things "tending to zero", it's a countable sum of zeroes, which is zero. P(U,V fails the killer property) is 0 for every finite disjoint U,V. It is not "infinitesimal", "very small", "tending to zero", or some other fancy concept. It is zero.
Wait... is it countable? Because if we think about all the ways we can form subsets U, V in a finite graph with N vertices, the total number of subsets is proportional to the side of the powerset of the set of vertices, and the powerset of countably infinite vertices is uncountably infinite.
Ok, I think I have a convincing argument as to why the sum should be 0. If we consider the sum of all subsets U of size k and subsets V of size l, then there are a countably infinite number of those(We can think of the set of all Us of size k as being strictly smaller than the set of all ordered k tuples of natural numbers, and that second set is countably infinite). For any one of them, P(U,V has the property)=0, so the sum over those sets is 0. Now we can sum over k and l, where we have clearly countably infinite combinations of k, l, so the sum of zeroes must still be 0. This works because each "zero" isn't being multiplied by anything. Put another way, a countable sum of things "going to zero" is itself going to zero, regardless of how badly behaved the sum is(put simply, it can't be going to anything else), and this case is better because those things are "actually" zero.
The (presumably) transfinite induction required to conclude that a graph with the Extension Property contains every graph on countable vertices as an induced subgraph seems like an interesting and important omitted step.
@@kennyb3325 Fix a countably infinite graph G. We want an injection from G into the Rado graph (an embedding). Inductively define the injection so that vertex 0 in G maps to vertex 0 in the Rado graph, and vertex n in G maps to the earliest vertex in the Rado graph that has the right connections to the previous vertices (as described in the video). This is an inductive definition, and it will be defined for all infinitely many vertices in G. This is similar to how "F(0)=0, F(1)=1, F(n+2)=F(n+1)+F(n)" is an inductive definition of the Fibonacci numbers, and is defined for infinitely many n. Therefore, this is a injective function defined everywhere on G, so G is embedded in the Rado graph.
@@columbus8myhw Inductive arguments, by default, apply to arbitrarily large integers but not to infinity. There is no F(infinity) infinity Fibonacci number. Consider that you could inductively prove that if n is a finite number then n+1 is a finite number. However, this inductive proof would, thankfully, not imply that infinity is finite. As above, assume G is a graph on countable infinitely many vertices. Using induction you could convince me that the Rado graph contains any subgraph of G on arbitrarily many (but finitely so) vertices, but induction would not convince me that G in its entirety was therein contained. I guess I'll agree that any fixed vertex of G will eventually be mapped to some vertex in G, I just don't feel entirely comfortable saying that the process will "end," in some sense, with all of G embedded in the Rado graph.
Amazing theorem, graph theory is such unexplored territory to me that I am always amazed at the theorems you can get from it. What program did you use for the drawings?
Thanks for the video. Sometimes "finding" vertices that you haven't drawn would be confusing to non-graph theory people. Regardless, reasonably clear - voted for SoME1.
@@mohamadrezabidgoli8102 Yeah. Infinity is doing all the heavy lifting. It doesn't matter that edges are "rare" (as in the p = 0.1) or "common" (as in the p = 0.9), you can go infinitely far out to find an infinite amount of vertices that satisfy whatever connectivity and non-connectivity conditions you want.
I feel like there's some argumentation missing around 14:30. It does feel like it works out in the end though. You're taking the limit of p^k with l going to infinity, finding it's 0 and then doing an infinite sum over these probabilities. I think you can't do that, and that you can only take the limit at the last step. Something like: let G_k be a random graph with k vertices, p(U, W, G_k fails the killer prop) = p^k, where U and W are subgraphs of G_k. Then p(fails killer prop) = lim_{k -> \infty} \Sum_{U, W finite and disjoint subgraphs of G_k} p(U, W, G_k fails the killer prop) = lim_{k -> \infty} \Sum_{U, W finite and disjoint subgraphs of G_k} p^k = lim_{k -> \infty} 3^k \dot p^k. I don't know exactly how p depends on U, V and G_k, but I think it matters. Let me know if I'm missing something.
interesting point.. and do not forget that the number of subgraphs is uncountable (just the the power set of the natural numbers). that makes the sum notation a bit weird ^^
@@rikdegraaff891 but the statement that "for any two subgraphs there is a vertex connected to all vertices in one and to none in the other" also holds for infinite subgraphs. or am i wrong on this point?
He took the limit p^k -> 0 to compute the probability P(every vertex is bad)=0. If you look what he did, he actually proved that for any finite disjoint subsets U,W of vertices, P(U,W fail killer property)=0. There are countably many pairs of finite disjoint subsets of vertices, so the inequality is the union bound, and on the right hand side we are only summing (countably many) zeros, which is equal to zero.
this is probably my fav some1 video, but I think you should have talked more about why the alternating method works, it seems slike an useful idea and is a bit hard to accept
6:09 I paused and worked out the smallest numbers they could be. This is also the part where I think you found something cooler than me in graph theory.
The fact at the beginning did blow my mind, but I also kinda didn't pay much attention to the fact that the graph was infinite. It really messes things up in those paradoxical ways. Unfortunately, by realizing that the "infiniteness" of graphs is what's at work here, the whole problem also "breaks". You cannot really flip a coin infinitely many times. So there's kinda no paradox about drawing the same graph because you cannot really draw an infinite graph. They say, you and your friend are still rolling those coins to this day. Either way, it's pretty cool that there are no different countably infinite graphs (with some exceptions that have probability = 0 of happening).
It's about as reasonable to "pick an infinite sequence of {0,1}" as "pick a random real in [0,1]". They are both sampling from a distribution on an uncountable set. The analogous question for real numbers is something like: with probability 1 a random real will be a normal number (i.e. contain all finite digit sequences with the average density expected for their length).
At 12:47 you gave no explanation why P(v good)>0, which is a serious assumption and cannot be glanced over, like you did in the video. Without explaining why this probability is positive, the result cannot follow and there is nothing in the video that would make it obvious. I enjoyed the video, but this part feels unsatisfying to me.
Agreed. Does that have to do with that the probability is exactly 1/2 that any two vertices have an edge between them? Because I can see no other point where that probability matters, and the graphs based on different such probabilities (between 0 and 1 exclusive) would have different edge densities and thus cannot all be the Rado graph, right?
According to the wikipedia article the probability doesn't matter as long as it's strictly between 0 and 1 - you'll get the Rado graph anyway. That's weird - then I take it that its edge density is indeterminate.
@@stjernis No, because if we take p to be the probability that two vertices have an edge, then the probability that any given other vertex satisfies the killer property is p^|U|(1-p)^|V|>0 if 0
I don't understand why the sum at 14:09 holds. You have the lim k->inf [sum over all U,W of P(U,W fail killer prop)]. I understand that P(U,W fail killer prop) tends toward 0 but since the amount of U,W that exists also depends on k I don't see why you can pull the limit into the sum. For example: limit k->inf [sum from i=0 to k of 1/k] will sum to one despite the summand going to 0.
It's not that the limit was pulled into the sum. It was already there. Each summand represents "the probability that the killer property is broken with example set U and V".
Your concern is absolutely justified. A hint to what's really going on (and not being discussed) is that we have an inequality here. What's being applied here is something called Boole's inequality in probability theory (or just the property of sigma-subadditivity in measure theory) Hope that helps :)
I feel like the only potential issue with this video is stuff with infinity. You showed us procedures that work for finite amounts of points and then basically went "so it works for the limit", which I dont think its necesariliy true, but its an educational video so maybe its supposed to skip those pesky details
There are two parts that I don't understand about step 2 of the proof. (1) Why is P(v good) > 0? Since there are possibly infinite number of "v"s any finite number of cases does not show the probability is larger than zero. (2) A summation of infinitely many "really-close-to-zero"s can become non-zero. For example sum[1...p] (1/p) gives 1 when p goes to infinity (1/p goes to 0). Therefore the argument at 14:08 does not seem valid to me
You do get the same graph! In fact, there are several other explicit ways to construct Rado graphs apart from these base-n ones. Wikipedia page has some of them listed out. Also, as you might have noticed, sections 1 and 2 of this video can be dropped without effecting the rigor, or without even mentioning the Rado graphs at all. I just thought it would be nice to remove a layer of abstraction by showing an explicit construction.
Feels like an object defined with a certain kind of infinity that actually “diverges” such that its meaningfulness only lies on the definition. For example, when talking about infinite series, we can no longer alter the order of addition as we want. I suspect it would be the same here if we try to retrieve vertices just by talking about their property. The order of retrieval actually influences the structure of the mathematical object. Nice presentation anyway, very interesting topic.
The order in which we choose to go over the vertices certainly affects, say, the actual correspondence we find between the two graphs. It does not, however, affect the structure of the Rado graph itself - if you "explore" the Rado graph, it would "look the same" no matter where you go. An easier example that works in very much the same way is finding order preserving functions between the rationals and another copy of the rationals (such as the function f(x)=x+1, or f(x)=2x). You can again construct such a function step-by-step: Let's say we have decided that f(1)=2, f(3)=2.5, f(5)=100 and f(6)=101 (so far, the order is preserved: 1
@@orisegel4055 I'd assume you can do it with the power set and choice axioms right? Seems to me that the rado graph is a problematic object from a finitist or constructivist framework anyway so might as well use the two most fishy ZFC axioms :P
@@chalkchalkson5639 Well power set axiom is definitely involved in measure theory. I can't off the top of my head remember if AoC is necessary, but since only very niche groups care about using it (constuctivists and set theorists are the only example I can think of) we might as well. To be explicit, when I talked about the problem of making infinitely many random choices I was talking about measure theory (specifically, infinite powers of measure spaces). BTW, the video actually gives an explicit construction of the Rado graph that does not need AoC, but it certainly needs the axiom of infinity as well as exponentiation so I imagine it would still bother finitists.
@@orisegel4055 I mean to construct the set of edges you do it from the powerset of an infinite set, so we're definitely in a realm where even the softest of finitists are annoyed :D Also: ah you were alluding to measure theory! Yeah measure theory is really cool, though I'm not really familiar with using it in a discrete context. The only times I really had to deal with theorems from it was when dealing with weird continuous spaces (read the parts that become relevant for lebeque integration in general metric spaces) :P
@@chalkchalkson5639 So here is a cool tidbit for you: from a measure theory standpoint, there is actually no significant differences between a countably many independent Ber(0.5) variables and a single U([0,1]) variable, which is in and of itself just equivalent to the usual Lebesgue measure on the unit interval. So you actually probably do know enough measure theory to make countably many independent binary choices!
when talking about the probability of a graph being isomorphic to some other graph, which probability space and which measure are we actually working with?
My immediate intuitive answer to the question was probability 1 because the generated graph is infinite and its being compared to another graph. generally, an infinite set of things being compared to something random ends up with probability 1, although extremely unlikely
For "Step 1" in "Section 3 : Everything comes together", you could alternatively use the killer lemma by saying that G is an induced subgraph of Rado, and vice versa - hence they must be equal.
That's actually not good enough for infinite graphs. Consider an infinite binary tree T, and an infinite binary tree with an extra vertex connected to the root T+. Then either is a subgraph of the other (T is obviously an induced subgraph of T+, and T+ is induced by taking the root and one of the sides of T). But T+ has a vertex with only one neighbor, while in T every vertex has at least 2 neighbors (and all except the root have 3).
an easy to understand example of 'almost surely' is "what fraction of the integers can you divide by"? 100% - almost surely you can divide by a randomly selected integer between + - infinity.
Eh, seems to me that it's more straight forward to say that you're finding all sets of points that are arranged identically, which is at least countably infinite, if not uncountably. When you then consider all possible interconnections between those points, you will find at least one that matches the graph you started looking for.
The subsets are finite, so the probability that some arbitrary v is a good vertex is just the probability that it is adjacent to every vertex in U and not adjacent to every vertex in V. The probability that v is adjacent to every vertex in U is (1/2)^|U| where |U| is the size of U, and likewise the probability that v is not adjacent to every vertex in V is (1/2)^|V|. Because these are independent, we have P(v good)=(1/2)^(|U|+|V|)=(1/2)^k for some finite integer k. (1/2)^k>0 for all k, so we have P(v good)>0 for all finite U, V
I am fairly convinced that there are an uncountable number of finite subsets U, V of a countably infinite set of vertices because the set of all Us is the powerset of the set of vertices, and we know that the powerset of a countably infinite set is uncountable... wait, maybe the vast supermajority of All subsets of an infinite set are infinite, so the number of finite subsets of an infinite set could be countable??
Yep, if you consider the number of sets U of size k and V of size l, there are countably infinite U and V for any particular k, l, and we can sum over the countably infinite pairs of finite integers k,l, so there must be countably infinite finite disjoint sets U, V.(note the number of subsets of size "infinity" is not countable, but we ignore those by finiteness)
Do random graphs with n verticies converge to the rado graph, or is that a property that arises only at infinitely many verticies? Like generate two graphs A, B on n verticies, what is limit n to infinity of p(A isomorphic B)?
13:25 I'm not sure I understand why infinitely many vertices outside the two sets were chosen? Wouldn't one suffice to prove the probability isn't exactly 0?
The killer property states that we can find _some_ vertex outside the two sets that satisfies the property. If a single vertex doesn't work, that doesn't mean the property is false; we might have just chosen the wrong one. To negate the property, you'd need to prove that _every_ vertex outside the two sets doesn't work, and that's an infinite number of vertices. Since each one has a non-zero chance of working, the probability that one of them will eventually work approaches 1.
@12:46 I'm not convinced that P(v is good) > 0. Isn´t it possible that there is a finite number of good verticies? If so, with an infinite number of verticies, shouldn't P(v is good) = 0? What am i missing?
I smell Mathologer and Michael Penn. The chapter slide with music comes from Mathologer. "I think that's a good place to stop," is from Michael Penn. Not bad influences.
Wouldn’t there be a countably infinite amount of different rado graphs for the infinite amount of bases you can use to construct them? Would the extension (“killer”) property also apply to a graph constructed in binary? Or base 12? Or any other base? If so, then the probability that you and your friend both drew the “same” rado graph would actually be arbitrarily small. That is unless you can prove that the rado graph is indistinguishable to every rado graph of every base.
If you pick some other base and construct a graph using the same method as Rado but with that base, then you can go on to prove that it has the extension property in exactly the same way he did for base 10. Then since all graphs with that property are isomorphic, it is indeed the same no matter what base you start with.
I love infinity stuff, but it makes my brains hurt. @_@ Isn't the graph G is incomplete? There would be an infinite (I think?) number of other vertices attached to each point. I realize you obviously can't draw them all in... But a mention of it might not hurt. Unless, of course, I'm completely wrong, which I very well may be.
Ok I might be stupid but I don't get it. So there is an infinite graph with a random rule connecting vertexes to other vertexes and it happens to contain all the other graphs inside? Well I guess there is infinite amount of graphs like that so what makes this one special?
Also, I might have not understood this properly, but how the hell this graph contains all the other graphs if it is limited by its rule? If 1 can connect only to odd numbers then this graph can't contain a graph made of 1 connected to 2 right?
Thanks for the video. I just have one question about the bijection step. When selecting the smallest unmatched index of G (the graph with the killer property), what does it mean to have a smallest index? If the ordering of the indices is random, it seems to me that the smallest unmatched index could have edges connected to other unmatched indices, meaning you have mapped it to the wrong Rado index. It feels like you cannot map indices from G in any order.
You fix some indexing of the vertices of G, so the indexing is not randomised. And when selecting a vertex with correct connectivity, we are only interested the connectivity to the vertices already chosen, and will deal connectivity to other vertices later. By the killer property, there always exists some vertex with the correct connectivity, and from all such vertices we pick the smallest one.
I understand about the random graph and that it holds the killer property.. But how can you be sure that the graph drawn on infinite number of vertices with each edge having probability 0.5, is isomorphic to Rado graph or has killer?? Does this also mean that if the edges were drawn with probability of some other positive number but not equal to 0, would not lead to Rado graph??
Doesn’t really matter. We just care about the connections between them, not how they are arranged in space. We don’t even have to require that they have positions at all. So, if you want to imagine them as being on a paper, just pick whether their positions are arranged regularly or not based on whichever one is easier for you to imagine.
these random math channels that have poped up during lockdown...such a blessing
it's more thanks to SoME 1 than the pandemic
Me too
_poped up_ and _blessing_
An accidental pun.
@@officiallyaninja yeah, Grant's doing wonders for the math community
Theorem: In the limit where they post a countably infinite number of videos, all random math channels are actually the same random math channel. (Proof is left as an exercise for the reader.)
The fact this infinite graph isn't only locally connected makes it really hard to draw or visualize. It's basically a fully connected infinite graph with half the edges missing... so a bunch of the edges are missing but every vertex still has an infinite amount of edges to an infinite amount of vertices.
The connections are called edges. The points are called vertices. But yeah, infinity is a pretty wild concept.
@@DerIntergalaktische Thanks. My bad.
Even weirder, since it contains a copy of every finite or countable infinite graph. It contains a copy of a infinite fully connected graph and an infinite fully disconnected graph.
Even more trippy, to me, is that P(diameter of this graph = 2) = 1. In fact the expected value of the distance between two distinct vertices seems like it should be 3/2. So cool!
And the probability that a vertex has no edges is.. limit to 0? Are there vertices with no edges?
7:54 with subtitles: Remember that you're less lazy than 90% of TH-camrs just by writing subtitles (for which I thank you very much). Also amazing video!
for people who are deaf (i am not) maybe the only thing that would be more helpful is to say "[i am lazy - saying what is on screen]" just so they know they're not missing anything!
There is built-in support for editing auto generated closed captions on youtube after uploading, here is the guide that I found on yt th-cam.com/video/tWbNrm7Jo5c/w-d-xo.html video starts at 1min 6s
Also thanks for the yo mama joke in the subtitles ;0
To blow some more minds... pause at 14:20 and realize that he never uses the extact 1/2 propability of coin flipping. Only thing needed, is that the propability of being a good vertex needs to be non-zero.
So, flipping a coin or roling a dice (1=create edge, 2-6=no edge) will (almost always) construct the same infinite graph. Would be interesting to see how the propabilities behave for finite but huge graphs. Does the limit also go to 1?
Ah, I just wanted to ask how the graphs look with different probabilities. Thanks for responding before I wrote it down.
I was also interested in whether the chance of two random graphs of size n being isomorphic converges to 1 as n tends to infinity... If you try to work it out head on (ie calculate the probability as a function of n and p) it gets very difficult... Did you figure it out?
@@chalkchalkson5639 It goes to zero as long as n²p and n²(1-p) go to infinity. Two graphs with different numbers of edges can never be isomorphic, which is almost certain as long as the number of edges and the number of missing edges both go to infinity.
@@NoLongerBreathedIn yeah, I guess that makes sense...
the number of vertices should be binomially distributed, so in the limit we are talking normal distribution.
Then just say that the corresponding integral is smaller than 1*1/(sqrt(2pi)*sigma), substitute sigma=sqrt(np(1-p)) and see that for p(1-p)=/=0 that expression converges to 0.
So the integral must converge to 0, too.
It's amazing what you can do if you just draw an infinite number of dots and lines on a piece of paper.
i know what im doing with my evening!
@@pvic6959 my very... long... evening... - o°- zzzZZZ
Very nice video! To anyone interested in the "Logic" part mentioned at the end, the short version is this:
Let's assume we have a collection of finite structures (in our case, all finite graphs - but this also works with the collections of finite ordered sets).
If this collection has a few nice properties (here is an example: any two finite graphs can be joined to create a bigger finite graph; the other properties are not much more complicated), then we have an equivalent of the Rado graph.
By "equivalent" I mean that it has a property very similar to the killer property, contains a copy of every member of the collection, and is unique (and also many other nice properties).
This is called a Fraïssé limit, if you want to look it up.
I recommend Model Theory by Wilfrid Hodges, 7.4. Great book and it shows the connection between those two ideas of getting the random graph.
I love infinite probability stuff. there's an infinite number of random graphs you could end up with that aren't isomorphic to the rado graph, just with probability 0 that you actually make them
the omori song in the beggining hit me like a truck, definitelly wasn't expecting it, but a welcome surprise nonetheless
Thank you, sir! This was ABSOLUTELY amazing and completely new to me even after studying computer science! Will now go and tell my friends about it ❤️🔥
video starts, gets hit right away with omori title theme
"the _feels_ " T^T
I saw the isomorphic graph question and my first thought was, "the answer is definitely 0 or 1, but I have no idea which one...you could even say it's a coin flip (pun very much intended)."
14:25 I suspect there's a little more going on maybe.
Like, for any U,W, the chance is "0" but really it's like 0^+, an infinitely small positive number. There are definitely cases when adding infinitely many of those 0^+ does not give 0 (I believe the harmonic series for example)
Each individual term in the harmonic series is positive though, not 'infinitely small'. Each of the terms in this sum is exactly 0.
this guy just hits me with deep omori music without warning
This video is really excellent! Such an interesting topic, so well explained.
There's a part of this proof that I don't quite understand.
You can show that each individual pair of subsets has a 0 chance of not following the killer property.
However, there are an infinite amount of these subsets.
How can we be sure that doing an infinite sum of these "0"s doesn't yield some sort of limit or something?
yes I was wondering the same thing, sum of infinite things tending to zero. I think it needs more proof.
@@phanirithvij Because it's a product, not a sum. You multiply by a number between 0 and 1, more and more times, you keep knocking it down to zero.
I suppose you could come up with a story about Hilbert's Infinite Hotel running a sale...
@@phanirithvij It's not a sum of infinite things "tending to zero", it's a countable sum of zeroes, which is zero. P(U,V fails the killer property) is 0 for every finite disjoint U,V. It is not "infinitesimal", "very small", "tending to zero", or some other fancy concept. It is zero.
Wait... is it countable? Because if we think about all the ways we can form subsets U, V in a finite graph with N vertices, the total number of subsets is proportional to the side of the powerset of the set of vertices, and the powerset of countably infinite vertices is uncountably infinite.
Ok, I think I have a convincing argument as to why the sum should be 0. If we consider the sum of all subsets U of size k and subsets V of size l, then there are a countably infinite number of those(We can think of the set of all Us of size k as being strictly smaller than the set of all ordered k tuples of natural numbers, and that second set is countably infinite). For any one of them, P(U,V has the property)=0, so the sum over those sets is 0. Now we can sum over k and l, where we have clearly countably infinite combinations of k, l, so the sum of zeroes must still be 0.
This works because each "zero" isn't being multiplied by anything. Put another way, a countable sum of things "going to zero" is itself going to zero, regardless of how badly behaved the sum is(put simply, it can't be going to anything else), and this case is better because those things are "actually" zero.
The (presumably) transfinite induction required to conclude that a graph with the Extension Property contains every graph on countable vertices as an induced subgraph seems like an interesting and important omitted step.
You construct the bijection one vertex at a time.
@@columbus8myhw Sure, that will get you finite graphs, but you will never "finish" if the graph has countably infinite vertices.
@@kennyb3325 Fix a countably infinite graph G. We want an injection from G into the Rado graph (an embedding).
Inductively define the injection so that vertex 0 in G maps to vertex 0 in the Rado graph, and vertex n in G maps to the earliest vertex in the Rado graph that has the right connections to the previous vertices (as described in the video).
This is an inductive definition, and it will be defined for all infinitely many vertices in G. This is similar to how "F(0)=0, F(1)=1, F(n+2)=F(n+1)+F(n)" is an inductive definition of the Fibonacci numbers, and is defined for infinitely many n. Therefore, this is a injective function defined everywhere on G, so G is embedded in the Rado graph.
@@columbus8myhw Inductive arguments, by default, apply to arbitrarily large integers but not to infinity. There is no F(infinity) infinity Fibonacci number. Consider that you could inductively prove that if n is a finite number then n+1 is a finite number. However, this inductive proof would, thankfully, not imply that infinity is finite.
As above, assume G is a graph on countable infinitely many vertices. Using induction you could convince me that the Rado graph contains any subgraph of G on arbitrarily many (but finitely so) vertices, but induction would not convince me that G in its entirety was therein contained. I guess I'll agree that any fixed vertex of G will eventually be mapped to some vertex in G, I just don't feel entirely comfortable saying that the process will "end," in some sense, with all of G embedded in the Rado graph.
@@kennyb3325 I don't claim that F acts on infinity. I claim that F acts on {natural numbers}, which is an infinite set.
Amazing theorem, graph theory is such unexplored territory to me that I am always amazed at the theorems you can get from it. What program did you use for the drawings?
Thanks for the video. Sometimes "finding" vertices that you haven't drawn would be confusing to non-graph theory people. Regardless, reasonably clear - voted for SoME1.
Oh boy! You did a great job. Also with the graphics. Loved it. Am I right that for every 0
I have the same question.
Yes. For every 0
@@imacds Well, it makes it even more counter intuitive! So the one with p=0.1 and with p=0.9 are the same??
@@mohamadrezabidgoli8102 Yeah. Infinity is doing all the heavy lifting. It doesn't matter that edges are "rare" (as in the p = 0.1) or "common" (as in the p = 0.9), you can go infinitely far out to find an infinite amount of vertices that satisfy whatever connectivity and non-connectivity conditions you want.
@@imacds Mindblowing indeed. Thank you Cubba.
I feel like there's some argumentation missing around 14:30. It does feel like it works out in the end though. You're taking the limit of p^k with l going to infinity, finding it's 0 and then doing an infinite sum over these probabilities. I think you can't do that, and that you can only take the limit at the last step. Something like: let G_k be a random graph with k vertices, p(U, W, G_k fails the killer prop) = p^k, where U and W are subgraphs of G_k. Then p(fails killer prop) = lim_{k -> \infty} \Sum_{U, W finite and disjoint subgraphs of G_k} p(U, W, G_k fails the killer prop) = lim_{k -> \infty} \Sum_{U, W finite and disjoint subgraphs of G_k} p^k = lim_{k -> \infty} 3^k \dot p^k. I don't know exactly how p depends on U, V and G_k, but I think it matters. Let me know if I'm missing something.
interesting point.. and do not forget that the number of subgraphs is uncountable (just the the power set of the natural numbers). that makes the sum notation a bit weird ^^
@@deinauge7894 I think the number of pairs of disjoint, finite subgraphs is countable since the subgraphs are finite.
@@rikdegraaff891 but the statement that "for any two subgraphs there is a vertex connected to all vertices in one and to none in the other" also holds for infinite subgraphs. or am i wrong on this point?
He took the limit p^k -> 0 to compute the probability P(every vertex is bad)=0. If you look what he did, he actually proved that for any finite disjoint subsets U,W of vertices, P(U,W fail killer property)=0. There are countably many pairs of finite disjoint subsets of vertices, so the inequality is the union bound, and on the right hand side we are only summing (countably many) zeros, which is equal to zero.
this is probably my fav some1 video, but I think you should have talked more about why the alternating method works, it seems slike an useful idea and is a bit hard to accept
Aw dang wish you had more videos out! Subscribeddd
This is indeed a stunning video
Fantastic subtitles, that's a +1 from me. Reminds me of a Mathologer video :D
The subtitles are very well done! Kudos!
Great video. Very clearly explained. Waiting for more.
1:34 this is the exactly same 'WHAT??' that came out my mouth 1 second earlier :D :D
8:35 (captions) It’s never too late for a _yo mama_ joke. Great video!
This video definitely watered my sunflowers
6:09 I paused and worked out the smallest numbers they could be. This is also the part where I think you found something cooler than me in graph theory.
Glad you enjoyed!
The fact at the beginning did blow my mind, but I also kinda didn't pay much attention to the fact that the graph was infinite. It really messes things up in those paradoxical ways.
Unfortunately, by realizing that the "infiniteness" of graphs is what's at work here, the whole problem also "breaks". You cannot really flip a coin infinitely many times. So there's kinda no paradox about drawing the same graph because you cannot really draw an infinite graph. They say, you and your friend are still rolling those coins to this day.
Either way, it's pretty cool that there are no different countably infinite graphs (with some exceptions that have probability = 0 of happening).
It's about as reasonable to "pick an infinite sequence of {0,1}" as "pick a random real in [0,1]". They are both sampling from a distribution on an uncountable set. The analogous question for real numbers is something like: with probability 1 a random real will be a normal number (i.e. contain all finite digit sequences with the average density expected for their length).
BRUH OK I JUST STARTED WATCHING IT AND I DID NOT EXPECT THAT MUSICAL EMOTIONAL GUT PUNCH AT THE START GODDAMN DUDE.
At 12:47 you gave no explanation why
P(v good)>0, which is a serious assumption and cannot be glanced over, like you did in the video. Without explaining why this probability is positive, the result cannot follow and there is nothing in the video that would make it obvious.
I enjoyed the video, but this part feels unsatisfying to me.
Both sets are finite. (1/2)^n>0 for all finite n
@@viliml2763 True, I guess I just missed the fact that the “killer property” was used only for finite sets. Thank you for the reply.
Agreed. Does that have to do with that the probability is exactly 1/2 that any two vertices have an edge between them? Because I can see no other point where that probability matters, and the graphs based on different such probabilities (between 0 and 1 exclusive) would have different edge densities and thus cannot all be the Rado graph, right?
According to the wikipedia article the probability doesn't matter as long as it's strictly between 0 and 1 - you'll get the Rado graph anyway. That's weird - then I take it that its edge density is indeterminate.
@@stjernis No, because if we take p to be the probability that two vertices have an edge, then the probability that any given other vertex satisfies the killer property is p^|U|(1-p)^|V|>0 if 0
That OMORI title theme caught me offguard!
VERY interesting video, I enjoyed quite a lot! Thanks for it
Thank you! This video made my day!!❤️
I love the fact that you put some omori theme song in this video ♥
never expected to hear omori music in a math video
This video is amazing! Thank you!
Fantastic video!
So you like math and omori... wow, you are so cool
I don't understand why the sum at 14:09 holds. You have the lim k->inf [sum over all U,W of P(U,W fail killer prop)]. I understand that P(U,W fail killer prop) tends toward 0 but since the amount of U,W that exists also depends on k I don't see why you can pull the limit into the sum. For example: limit k->inf [sum from i=0 to k of 1/k] will sum to one despite the summand going to 0.
It's not that the limit was pulled into the sum. It was already there. Each summand represents "the probability that the killer property is broken with example set U and V".
Your concern is absolutely justified.
A hint to what's really going on (and not being discussed) is that we have an inequality here.
What's being applied here is something called Boole's inequality in probability theory (or just the property of sigma-subadditivity in measure theory)
Hope that helps :)
I think that's a fairly intuitive result
Really cute video, love it 😊
Assuming the disjoint sets have topology, this is very similar to bordism
I feel like the only potential issue with this video is stuff with infinity. You showed us procedures that work for finite amounts of points and then basically went "so it works for the limit", which I dont think its necesariliy true, but its an educational video so maybe its supposed to skip those pesky details
There are two parts that I don't understand about step 2 of the proof. (1) Why is P(v good) > 0? Since there are possibly infinite number of "v"s any finite number of cases does not show the probability is larger than zero. (2) A summation of infinitely many "really-close-to-zero"s can become non-zero. For example sum[1...p] (1/p) gives 1 when p goes to infinity (1/p goes to 0). Therefore the argument at 14:08 does not seem valid to me
amazing video!!!
11:23 so if you used a different base than 10, would you still get the rado graph, or will you get a graph without the killer property?
You do get the same graph! In fact, there are several other explicit ways to construct Rado graphs apart from these base-n ones. Wikipedia page has some of them listed out.
Also, as you might have noticed, sections 1 and 2 of this video can be dropped without effecting the rigor, or without even mentioning the Rado graphs at all. I just thought it would be nice to remove a layer of abstraction by showing an explicit construction.
In fact, I think the base 2 version might make the link to "flip a coin for each edge connection" feel more explicit.
Feels like an object defined with a certain kind of infinity that actually “diverges” such that its meaningfulness only lies on the definition. For example, when talking about infinite series, we can no longer alter the order of addition as we want. I suspect it would be the same here if we try to retrieve vertices just by talking about their property. The order of retrieval actually influences the structure of the mathematical object.
Nice presentation anyway, very interesting topic.
The order in which we choose to go over the vertices certainly affects, say, the actual correspondence we find between the two graphs.
It does not, however, affect the structure of the Rado graph itself - if you "explore" the Rado graph, it would "look the same" no matter where you go.
An easier example that works in very much the same way is finding order preserving functions between the rationals and another copy of the rationals (such as the function f(x)=x+1, or f(x)=2x).
You can again construct such a function step-by-step:
Let's say we have decided that f(1)=2, f(3)=2.5, f(5)=100 and f(6)=101 (so far, the order is preserved: 1
@@orisegel4055 I'd assume you can do it with the power set and choice axioms right?
Seems to me that the rado graph is a problematic object from a finitist or constructivist framework anyway so might as well use the two most fishy ZFC axioms :P
@@chalkchalkson5639 Well power set axiom is definitely involved in measure theory. I can't off the top of my head remember if AoC is necessary, but since only very niche groups care about using it (constuctivists and set theorists are the only example I can think of) we might as well.
To be explicit, when I talked about the problem of making infinitely many random choices I was talking about measure theory (specifically, infinite powers of measure spaces).
BTW, the video actually gives an explicit construction of the Rado graph that does not need AoC, but it certainly needs the axiom of infinity as well as exponentiation so I imagine it would still bother finitists.
@@orisegel4055 I mean to construct the set of edges you do it from the powerset of an infinite set, so we're definitely in a realm where even the softest of finitists are annoyed :D
Also: ah you were alluding to measure theory! Yeah measure theory is really cool, though I'm not really familiar with using it in a discrete context. The only times I really had to deal with theorems from it was when dealing with weird continuous spaces (read the parts that become relevant for lebeque integration in general metric spaces) :P
@@chalkchalkson5639 So here is a cool tidbit for you: from a measure theory standpoint, there is actually no significant differences between a countably many independent Ber(0.5) variables and a single U([0,1]) variable, which is in and of itself just equivalent to the usual Lebesgue measure on the unit interval.
So you actually probably do know enough measure theory to make countably many independent binary choices!
grath reprethenthing the penthagon
I will remember them as "normal graphs" (as for it contains a copy of every finite graph )
It's a bit more special than even the normal numbers since it contains every countable graph too.
@@neopalm2050 brutal
when talking about the probability of a graph being isomorphic to some other graph, which probability space and which measure are we actually working with?
back n forth argument
My immediate intuitive answer to the question was probability 1 because the generated graph is infinite and its being compared to another graph. generally, an infinite set of things being compared to something random ends up with probability 1, although extremely unlikely
That behaves like an injective module.
3:06 Yeah, you lost me 💀
This channel looks like the start of something good
The French twist in the pronunciation of 'coin', 'annoying' is fascinating.
Subtitles read: "So, the Rado graph is like yo mama" XD
For "Step 1" in "Section 3 : Everything comes together", you could alternatively use the killer lemma by saying that G is an induced subgraph of Rado, and vice versa - hence they must be equal.
Oh really nice way to think about it. I was not convinced about his trick about taking the smallest unused vrtx, but you did ^^
That's actually not good enough for infinite graphs.
Consider an infinite binary tree T, and an infinite binary tree with an extra vertex connected to the root T+.
Then either is a subgraph of the other (T is obviously an induced subgraph of T+, and T+ is induced by taking the root and one of the sides of T). But T+ has a vertex with only one neighbor, while in T every vertex has at least 2 neighbors (and all except the root have 3).
an easy to understand example of 'almost surely' is "what fraction of the integers can you divide by"? 100% - almost surely you can divide by a randomly selected integer between + - infinity.
What?
u gain subscriber, beautiful video
At first, I thought you were saying to flip a fair quine.
Great video!
Wait! How are you allowed to take the infinite sum at 14:10? Isn't 0 * ∞ undefined?
Cool topic. Also lol@title.
Eh, seems to me that it's more straight forward to say that you're finding all sets of points that are arranged identically, which is at least countably infinite, if not uncountably. When you then consider all possible interconnections between those points, you will find at least one that matches the graph you started looking for.
Shouldn't vertex 3 be disconnected from vertex 250? (3:55)
What assurance am I missing that gurantees that "P(v good)>0" always holds true?
U and W are finite, so P(v good) >= (1/2)^(|V| + |W|) > 0
The subsets are finite, so the probability that some arbitrary v is a good vertex is just the probability that it is adjacent to every vertex in U and not adjacent to every vertex in V. The probability that v is adjacent to every vertex in U is (1/2)^|U| where |U| is the size of U, and likewise the probability that v is not adjacent to every vertex in V is (1/2)^|V|. Because these are independent, we have P(v good)=(1/2)^(|U|+|V|)=(1/2)^k for some finite integer k. (1/2)^k>0 for all k, so we have P(v good)>0 for all finite U, V
I am fairly convinced that there are an uncountable number of finite subsets U, V of a countably infinite set of vertices because the set of all Us is the powerset of the set of vertices, and we know that the powerset of a countably infinite set is uncountable... wait, maybe the vast supermajority of All subsets of an infinite set are infinite, so the number of finite subsets of an infinite set could be countable??
Yep, if you consider the number of sets U of size k and V of size l, there are countably infinite U and V for any particular k, l, and we can sum over the countably infinite pairs of finite integers k,l, so there must be countably infinite finite disjoint sets U, V.(note the number of subsets of size "infinity" is not countable, but we ignore those by finiteness)
Do random graphs with n verticies converge to the rado graph, or is that a property that arises only at infinitely many verticies? Like generate two graphs A, B on n verticies, what is limit n to infinity of p(A isomorphic B)?
13:25 I'm not sure I understand why infinitely many vertices outside the two sets were chosen? Wouldn't one suffice to prove the probability isn't exactly 0?
The killer property states that we can find _some_ vertex outside the two sets that satisfies the property. If a single vertex doesn't work, that doesn't mean the property is false; we might have just chosen the wrong one. To negate the property, you'd need to prove that _every_ vertex outside the two sets doesn't work, and that's an infinite number of vertices. Since each one has a non-zero chance of working, the probability that one of them will eventually work approaches 1.
8:38 subtitles are incorrect :( could you fix?
how do we know the number of terms in the summation at 14:06 doesn't grow faster with k than p^k shrinks with k?
@12:46 I'm not convinced that P(v is good) > 0. Isn´t it possible that there is a finite number of good verticies? If so, with an infinite number of verticies, shouldn't P(v is good) = 0? What am i missing?
Why do all of the outside vertices need to be "bad" for the property to fail?
I smell Mathologer and Michael Penn. The chapter slide with music comes from Mathologer. "I think that's a good place to stop," is from Michael Penn. Not bad influences.
Wouldn’t there be a countably infinite amount of different rado graphs for the infinite amount of bases you can use to construct them? Would the extension (“killer”) property also apply to a graph constructed in binary? Or base 12? Or any other base? If so, then the probability that you and your friend both drew the “same” rado graph would actually be arbitrarily small. That is unless you can prove that the rado graph is indistinguishable to every rado graph of every base.
If you pick some other base and construct a graph using the same method as Rado but with that base, then you can go on to prove that it has the extension property in exactly the same way he did for base 10. Then since all graphs with that property are isomorphic, it is indeed the same no matter what base you start with.
I love infinity stuff, but it makes my brains hurt. @_@ Isn't the graph G is incomplete? There would be an infinite (I think?) number of other vertices attached to each point. I realize you obviously can't draw them all in... But a mention of it might not hurt. Unless, of course, I'm completely wrong, which I very well may be.
Reminds me of Black Swan Theory
Very nice.
What is the name of the property that a vertex might have that it is connected to just one other vertex (or a different, definite, finite number)?
1:52 I think this is not true If you define “almost” as ‘except for a finite number of cases’
Ok I might be stupid but I don't get it. So there is an infinite graph with a random rule connecting vertexes to other vertexes and it happens to contain all the other graphs inside? Well I guess there is infinite amount of graphs like that so what makes this one special?
Also, I might have not understood this properly, but how the hell this graph contains all the other graphs if it is limited by its rule? If 1 can connect only to odd numbers then this graph can't contain a graph made of 1 connected to 2 right?
Yea... infinity is 100%
funny thing.
Came from 3 blue 1 brown .
It's weird to abbreviate "vertices" as "vtx", given there is no "x". Is it a common abbreviation or is it your own?
Would this work too if instead of a coin I threw a dice?
I predict that the probability is zero
Thanks for the video. I just have one question about the bijection step. When selecting the smallest unmatched index of G (the graph with the killer property), what does it mean to have a smallest index? If the ordering of the indices is random, it seems to me that the smallest unmatched index could have edges connected to other unmatched indices, meaning you have mapped it to the wrong Rado index. It feels like you cannot map indices from G in any order.
You fix some indexing of the vertices of G, so the indexing is not randomised. And when selecting a vertex with correct connectivity, we are only interested the connectivity to the vertices already chosen, and will deal connectivity to other vertices later. By the killer property, there always exists some vertex with the correct connectivity, and from all such vertices we pick the smallest one.
I understand about the random graph and that it holds the killer property.. But how can you be sure that the graph drawn on infinite number of vertices with each edge having probability 0.5, is isomorphic to Rado graph or has killer?? Does this also mean that if the edges were drawn with probability of some other positive number but not equal to 0, would not lead to Rado graph??
Omori why
Are the points drawn in a periodic grid, or are they distributed randomly?
Doesn’t really matter. We just care about the connections between them, not how they are arranged in space. We don’t even have to require that they have positions at all.
So, if you want to imagine them as being on a paper, just pick whether their positions are arranged regularly or not based on whichever one is easier for you to imagine.
Good video
Interesting, does this hold for all numerical bases?
is the chord at the start out of the omori title theme just a coincidence?
after watching this further, yes it is so this question was unnecessary
Is it me or the time segments are an "Omori" reference :D
Why isn't 100 actually a 100%, why almost surely?