Thank you for your explanations. Easy to follow. At the minute 11:42, you pick any vertex, let's say 𝑣, and it has a degree of 9. This means there are 9 edges incident with 𝑣. By the pigeonhole principle, among these 9 edges, at least one color must appear at least 5 times because ⌈9/2⌉=5 Therefore, there must be at least 5 red or 5 blue edges. The statement "4 blue and 6 red" was likely a mistake; the correct numbers should be 5 of one color and 4 of the other. Am I right? I'm still learning Ramsey Therorem.
@abushiebaibrahim8221 The statement is "4 blue or 6 red" (not "4 blue and 6 red") and is correct as stated. Your statement "5 red or 5 blue" is also correct, but not as helpful for this proof. There are 9 edges incident with the vertex v and each of these 9 edges is colored red or blue. Is it possible to have fewer than 4 blue edges and at the same time fewer than 6 red edges? If so, we would have at most 3 blue edges and at the same time at most 5 red edges for a total of at most 8 colored edges. However, the degree of the vertex is 9 and so there is an edge unaccounted for. This argument shows that the answer to the rhetorical question is no. As a result, either there is at least 4 blue edges or at least 6 red edges. This combination of configurations is exactly what we need to continue this particular line of argument. Same logic also shows that there is at least 5 red edges or at least 5 blue edges among the 9 (since again if you had at most 4 red edges and at most 4 blue edges, you would be missing one edge). You could also argue that there is at least 3 red edges or at least 7 blue edges among the 9 using the same argument. The combination you choose has to allow you to finish the argument.
r(2, m) is the smallest positive integer s such that if you color the edges of the complete graph K_s then, regardless of how the coloring was done, you are guaranteed a blue K_2 or a red K_m. r(2, m) cannot be 2 (as long as m>2) since I can color the one edge of K_2 red, and then I will have neither a blue K_2 nor a red K_m. Note that you have to decide which color is the first color and which color is the second color before your adversary colors the edges of K_s. So even though in that particular coloring there is a red K_2, that is not enough. We had specified we wanted a blue K_2 or a red K_,m, and we got neither.
![The most beautiful equation in math, explained visually [Euler’s Formula]](http://i.ytimg.com/vi/f8CXG7dS-D0/mqdefault.jpg)
Thanks, your explanations are so good! And I love the slides, it's very easy to understand thanks to all the animations.
I am glad you liked it. Thank you for your support!
🍎
Thank you so much for the video. Great explanation!
Thank you for your support.
Thank you for your explanations. Easy to follow. At the minute 11:42, you pick any vertex, let's say
𝑣, and it has a degree of 9. This means there are 9 edges incident with
𝑣. By the pigeonhole principle, among these 9 edges, at least one color must appear at least 5 times because
⌈9/2⌉=5
Therefore, there must be at least 5 red or 5 blue edges. The statement "4 blue and 6 red" was likely a mistake; the correct numbers should be 5 of one color and 4 of the other. Am I right? I'm still learning Ramsey Therorem.
@abushiebaibrahim8221 The statement is "4 blue or 6 red" (not "4 blue and 6 red") and is correct as stated. Your statement "5 red or 5 blue" is also correct, but not as helpful for this proof. There are 9 edges incident with the vertex v and each of these 9 edges is colored red or blue. Is it possible to have fewer than 4 blue edges and at the same time fewer than 6 red edges? If so, we would have at most 3 blue edges and at the same time at most 5 red edges for a total of at most 8 colored edges. However, the degree of the vertex is 9 and so there is an edge unaccounted for. This argument shows that the answer to the rhetorical question is no. As a result, either there is at least 4 blue edges or at least 6 red edges. This combination of configurations is exactly what we need to continue this particular line of argument. Same logic also shows that there is at least 5 red edges or at least 5 blue edges among the 9 (since again if you had at most 4 red edges and at most 4 blue edges, you would be missing one edge). You could also argue that there is at least 3 red edges or at least 7 blue edges among the 9 using the same argument. The combination you choose has to allow you to finish the argument.
@6:25 Why can't we simply write
r(2,m) = 2?
Ramsey number is the minimum of such number
r(2, m) is the smallest positive integer s such that if you color the edges of the complete graph K_s then, regardless of how the coloring was done, you are guaranteed a blue K_2 or a red K_m. r(2, m) cannot be 2 (as long as m>2) since I can color the one edge of K_2 red, and then I will have neither a blue K_2 nor a red K_m. Note that you have to decide which color is the first color and which color is the second color before your adversary colors the edges of K_s. So even though in that particular coloring there is a red K_2, that is not enough. We had specified we wanted a blue K_2 or a red K_,m, and we got neither.