xlv. Party Problem (Ramsey R(3,3) = 6)

Problem. Among how many people must there be three mutual friends or three mutual strangers? Answer: 6 ($R(3,3)=6$): 5 people are not enough.

bool monoTriangle(int n, long long colouring) {   // bit e = colour of edge e in the order (0,1), (0,2), ..., (n-2, n-1)
    vector<vector<int>> col(n, vector<int>(n)); int e = 0;
    for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) col[i][j] = col[j][i] = colouring >> e++ & 1;
    for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) for (int k = j + 1; k < n; k++)
        if (col[i][j] == col[j][k] && col[j][k] == col[i][k]) return true;
    return false;
}

Ramsey number	Value
$R(3,3)$	6
$R(3,4)$	9
$R(4,4)$	18
$R(5,5)$	between 43 and 46 (open)
general bound	$R(s,t)\le \left(\genfrac{}{}{0ex}{}{s+t-2}{s-1}\right)$

Proof: R(3, 3) = 6

Six suffice. Take any person $v$. Of the 5 others, by pigeonhole at least 3 have the same relation to $v$, say friends $x,y,z$. If any two of $x,y,z$ are friends, they form a friendly triangle with $v$; otherwise $x,y,z$ are mutual strangers. Five do not. Seat 5 people in a circle; neighbours are friends, others strangers. The friendship graph is a 5-cycle and the stranger graph is the complementary 5-cycle; neither contains a triangle. The general bound follows the same way: $R(s,t)\le R(s-1,t)+R(s,t-1)$. Checked by brute force over all $2^{10}$ colourings of $K_5$ (some avoid monochromatic triangles) and all $2^{15}$ colourings of $K_6$ (none do).