ramsey.md

Friends and Strangers

In any party of six people either at least three of them are (pairwise) mutual strangers or at least three of them are (pairwise) mutual acquaintances.

The simple proof by pigeonhole principle is shown here and here.

However, I'd like to prove it with by brute force. As mentioned here, the only thing is to exhaust 2¹⁵ colorings and to find mutual friends / strangers in each coloring. Considering the symmetry, only 78 colorings are necessary to check.^{How to prove?}

Proof by Program

ramsey.py tries to find out colorings (where mutual friends / strangers are not found) for R(3,3)=N. It has two big nested loops:

1. Loop for 2^M colorings, where M=N*(N-1)/2 is the number of edges;
2. Loop for L=C(N,3) cliques.

The program found no coloring (without monochromatic cliques) for R(3,3)=6, and found 12 colorings for R(3,3)>5 (change N to 5), which matched our expectation:

2 colorings (swap red and blue)	10 colorings (5 directions, red <-> blue)