Ramsey Theory 3: Ramsey Numbers and Ramsey's Theorem
ฝัง
- เผยแพร่เมื่อ 20 ม.ค. 2014
- In this video, Kaj Hansen defines Ramsey numbers and proves that they exist.
Part of a series of videos by Kaj Hansen on Ramsey Theory. He's an undergraduate mathematics student at the University of Georgia. He's working to make Ramsey Theory more accessible to a broader mathematical audience. - วิทยาศาสตร์และเทคโนโลยี
Extremely good explanation!!!!!!!!!! This dude knows he's stuff!
Great lecture! Thanks for making this
thanks for the videos pal, you saved me some precious time for my exam :)
Great tutorial, thanks!
Great Video! Thanks!
2:22
The perfect topology for a meeting between members of a top-secret cult.
good job
good talk brother : )
Hi, at 12:53, how do you know that you can connect the s-1 vertices to the fixed vertex v via a red edge? How do you know that all of the s-1 vertices belong to the set A? Nice explanation btw.
I did not get that too, but I figured it out. Because there |A|>=R(s-1,t). It means there are at least |A| many vertices connected to our chosen vertex v through red edges. Then all these vertex has cardinality at least R(s-1,t). Then there exist a Ks-1 with red colouring. Since they connected to our chosen vertex v by red edges. So it has Ks with red colouring.
In the proof of Ramsey's theorem, I can't understand why we use those cases for the size of A and B. Why can't we switch the values and say that A >= r(s,t-1) or B >= r(s-1,t)?
I believe it's because A is the set connected to v via red edges, and we need those red edges to augment the red clique from size s-1 to s. Similarly, we use the blue edges connecting v to B to augment the blue clique from size s-1 to t.
At 8:16 explain Why the lAl +|B| =R(s, t-1)+R(t,s-1) -1
Since we have established that 5 is too small for R(3, 3) isn't it supposed to be that R(3, 3) needs to be equal or higher than 6 rather?
So he opens the video by making reference to his first video where he shows that R(3,3)5. The combination of those two results is that R(3,3,)=6.
Uardito I see, thank you !
I'd say this is a bit misleading, since at 2:40, you say that by showing that K(3,3) is not 5, you've shown that it is in 6. But that is not true, you've only shown that it must be larger than 5, but not that 6 is enough, that would require a completely different proof.
Jakub Arnold I appreciate you keeping us honest here, but I think what he's presented is in fact correct, though I think there might have been a way to make it a little clearer. In the first video, he showed that R(3,3)5. Those two statements together prove that R(3,3)=6.
That being said, you criticism speaks to, I think, a problem that we wrestled with, but failed to completely solve. In these videos we're experimenting with a new way of communicating mathematics. Most math is learned from books and classes, both of which have a very rigid linearity to them and people expect to put a lot of time into it in each sitting. TH-cam videos are the opposite in both respects: people don't tend to stick around for more than five minutes and they'll watch videos in any order they please. So in producing these videos, we wanted to organize the content so that each video was as self contained as possible and as short as possible. I was okay with one video making reference to other videos in the series as long as that reference was clear and easy to follow.
I think you've convinced me that we failed in that respect here. I don't know. While I'm no longer as obsessed with math content as I was a year and a half ago, I still think this is a legitimate and interesting problem and any observations or ideas on how to do it better are welcome :)
Kaj Hansen defines Ramsey numbers and proves that they exist.
I don't understand how R(s,t) being finite if s+t = n - 1 isn't obvious.
Assuming both s and t are finite the result of adding them together would have to be finite. Then n-1 would have to be finite. And then n would have to be finite as well. And R(s,t) was defined in the video as being n.
But you wouldn't have stated that hypothesis and went to all that trouble to prove it if it was that obvious so I must be missing something.
I see the confusion. We were a little sloppy when we made the video and didn't specify that the n in this proof has nothing really to do with the n in the definition earlier in the video. (Or we could have just used different letters.) This n is the variable we're going to induct on, which is a little bit a of a cheat; we _really_ want to induct on s and t and this n is our way to weasel out of going all Inception-y by making an induction argument within an induction argument for s and t separately.
Does that make sense?
Thanks! Now I understand.
12:00
8:53
3:05
I don't understand 9:04 when you say |A| >= R(s-1, t) or |B| >= R(s,t-1). How do you know that A is dependent on R(s-1, t) and that B is dependent on R(s,t-1)? Why did you write what you wrote instead of writing |A| >= R(s, t-1) or |B| >= R(s-1,t)? Is this arbitrary? Because didn't you already assign that A corresponds to red and s corresponds to red?
I also did not understand the explanation of why R(s-1,t) and R(s,t-1) are finite at 6:00. How does the induction hypothesis show that they're finite? And how do you know s-1+t=n-1, when before you said s+t=n-1?
I am not very familiar with the method of induction, so I don't quite get where the induction is coming into play. Usually, you have a base case where n=1. Then you do inductive hypothesis where n=k. Then you do inductive step where n=k+1. But what was the process in this case?
Thank you so much for making this video.
the same exact place i am here..
came for the ramsey numbers, stayed for the lad
13:20
0:23
11:17
This guy looks like a serious player
He is cute, smart and generous to provide an easy explanation for an interesting subject, - who wouldn't want to meet someone like that?
5:08
10:22
This dude totally looks and sounds like SNL's Bill Hader!
This isn't valid logic because you start off with the assumption that R(s,t)
i sound like they were saying sex