CO8 Small Ramsey Numbers: r(3, 4)=9, r(3, 5)= 14, r(4,4) =18

Описание: Proofs for the Ramsey Numbers r(3, 4), r(3,5), and r(4,4). One proposition, in one sweep, helps us find all three. Subscribe ‪@Shahriari‬ for more undergraduate math videos. After quickly reviewing Ramsey's Theorem and Ramsey Numbers, we prove that if r(n-1,m) and r(n,m-1) are both even integers, then r(n,m) is less than or equal to r(n-1,m)+r(n,m-1)-1. This allows us to show that r(3,4) is no more than 9, and, then it follows that r(3, 5) is less than or equal to 14 and r(4,4) is less than or equal to 18. Examples are provided to show that we indeed have equality.#combinatorics
00:00 Introduction
00:55 Reminder r(3,3)=6 (   • CO6 What is Ramsey Theory?  )
01:34 r(3,4) = 9. What does it mean?
04:41 The arrow notation
06:27 Ramsey's Theorem (   • CO7 Proof of Ramsey's Theorem for 2 colors  )
07:22 Ramsey Numbers
08:01 Ramsey Numbers: Initial cases
09:03 Recursive inequality for Ramsey Numbers (   • CO7 Proof of Ramsey's Theorem for 2 colors  )
10:48 Key fact & Strategy for Proof of small Ramsey numbers
13:46 Proof of Key Fact split into 3 cases
16:52 Proof of Cases 1 & 2
19:16 Proof of Case 3
23:01 Applying the Key Fact to get upper bounds for r(3,4), r(3, 5), and r(4,4)
23:46 Example: r(3,4) is more than 8
26:04 Example: r(3,5) is more than 13
27:46 Example: r(4,4) is more than 17
28:58 Other videos of interest
Next Ramsey Theory Video:    • CO21 Upper and Lower Bounds for Ramsey Num...  

Videos on Ramsey Theory:
What is Ramsey Theory?    • CO6 What is Ramsey Theory?  
Proof of Ramsey's Theorem for 2 colors    • CO7 Proof of Ramsey's Theorem for 2 colors  
Small Ramsey Numbers r(3,4)=9, r(3,5)=14, and r(4,4) = 18    • CO8 Small Ramsey Numbers: r(3, 4)=9, r(3, ...  
Upper & Lower Bounds for Ramsey Numbers    • CO21 Upper and Lower Bounds for Ramsey Num...  

A series of lectures on introductory Combinatorics. This full course is based on my book
Shahriar Shahriari, An Invitation to Combinatorics, Cambridge University Press, 2022.
DOI: https://doi.org/10.1017/9781108568708

For an annotated list of available videos for Combinatorics see
https://pomona.box.com/s/by2ay2872avx...
YouTube Playlist:    • Combinatorics, An Invitation  

Shahriar Shahriari is the William Polk Russell Professor of Mathematics at Pomona College in Claremont, CA USA
Shahriari is a 2015 winner of the Mathematical Association of America's Haimo Award for Distinguished Teaching of Mathematics, and six time winner of Pomona College's Wig teaching award.


Subscribe to my channel ‪@Shahriari‬​