Problem

Source: 2019 Polish MO Finals

Tags: combinatorics, clique, graph theory, Extremal Graph Theory



$n\ge 3$ guests met at a party. Some of them know each other but there is no quartet of different guests $a, b, c, d$ such that in pairs $\lbrace a, b \rbrace, \lbrace b, c \rbrace, \lbrace c, d \rbrace, \lbrace d, a \rbrace$ guests know each other but in pairs $\lbrace a, c \rbrace, \lbrace b, d \rbrace$ guests don't know each other. We say a nonempty set of guests $X$ is an ingroup, when guests from $X$ know each other pairwise and there are no guests not from $X$ knowing all guests from $X$. Prove that there are at most $\frac{n(n-1)}{2}$ different ingroups at that party.