Давайте я вот к этому добавлю небольшой комментарий. Вот есть числа Рамсея R(k,l): сколько человек нужно взять, чтобы среди них обязательно нашлось или k попарно знакомых, или l попарно незнакомых. И есть стандартная оценка
R(k,l) < 2^{k+l},
доказываемая просто по индукции (ибо R(k,l) <= R(k-1,l)+R(k,l-1) ).

Так вот — более простая версия конструкции из той работы позволяет легко получить эту же оценку. Авторы следят за четырьмя множествами — A, B, X и Y. Давайте вместо этого следить только за тремя: A, B и X. Потребуем, чтобы в любой момент выполнялись « свойства книг »:
- все люди из A попарно знакомы и знакомы во всеми из X;
- все люди из B попарно незнакомы и незнакомы во всеми из X.

Начнём с пустых A и B, а в X поместим всю компанию из 2^{k+l} человек.
И шаг за шагом делаем следующее:
- берём произвольного человека x из X;
- смотрим, кого у него больше в X, знакомых или незнакомых;
- если знакомых — добавляем его в A и оставляем в X только его знакомых (остальных убираем)
- если незнакомых — добавляем его в B и оставляем в X только его незнакомых (остальных убираем).

Каждый шаг уменьшает количество человек в X не больше, чем вдвое. А пока в X есть хоть кто-нибудь, мы можем продолжать.
За k+l-1 шаг или в A соберутся k человек, или в B — l человек. Вот и всё.

Так что — уже такая « детская версия » конструкции авторов с тремя множествами позволяет получить оценку в 2^{k+l}. После чего то, что более аккуратный подход позволит от экспоненты « чуть-чуть » откусить, уже не кажется невероятным (но и обещать заранее такого нельзя, конечно; то, что я тут написал, это скорее первые 5-10% процентов понимания).