MAT344H1 Lecture 12: Ramsey Number - Party Problem
Document Summary
Show that either 3 of them are mutual friends or 3 of them are strangers. Proof: pick any vertex of g, v is adjacent to n vertices, and independent from m vertices, n + m. Theorem: let n>= 0. then there exists n >= 0 such that for all. In a sufficiently large dataset, can always find a very orderly subset. Can compute r(4, 4), know that 43 (proven in 1989) <= r(5,5) <= 48 (proven in 2017) graphs g with >= n vertices, g or contains a . We call this number a ramsey number r(n, Suppose g is a graph with vertices, pick v in g. Define r(k,l) to be the min number such that for any graph g with r(k,l) vertices, g contains a. V is adjacent to m vertices and independent from n, m+n = r(k-1, l) + r(k, l-1)-1.
