Today.
Shower:

How many people do you need at a party to guarantee the existence of either k mutual stangers or k mutual friends?

Know:
k = 3 : 6.
k = 4 : 18.
k = 5 : 43 - 49.

Can we find an example of an arrangement of 43 people having no 5-stanger clique nor a 5-friend clique? The space of possibilities is large (say 2^( 43 choose 2 ), without reducing for symmetry). A brute force approach is uninteresting and unlikely to be successful. Need some better way to navigate.

Of course, I don't think about this in terms of friends/stangers, but rather in terms of a red/blue edge coloring of K_43. Since an example would be a delicate balancing act between red and blue, it stands to my reason that the number of red edges and blue edges would be close.

Game:

Two players : Red and Blue.
Red starts.
Players alternate coloring an uncolored edge of K_43 their color.
Red wins if a Red K_5 appears.
Blue wins if a Blue K-5 appears.
Game is drawn if there are no more moves to play and neither player has won.

A draw in this game would give the desired example.

If both players played perfectly, then it seems likely a draw could occur (assuming there are examples with [nearly] equal numbers of red/blue edges). Accepting that, it also seems reasonable that better players would be more likely to draw.

The goal then is to make good players. This game has quite a large branching factor (~ 43 choose 2), so brute force search is out of the question. Perhaps a 2-ply search. Select some parameters for the evaluation functon. Self play, evaluation function tuned by temporal difference learning. Will that explore the space well?

Only one way to find out. The code for the 2 ply search and everything else except the selection of evaluation parameters and learning has been implemented. Currently running with a randomized evaluation function with win detection -- Red is dominating.