Тройки знакомых или незнакомых из шести Начну с одной популярной школьной задачи. В течение долгого времени я был убежден, что этот факт был известен чуть ли не древним грекам, тогда как на самом деле задача возникла лишь в 1947 году на математической олимпиаде Венгрии. В англоязычной Википедии она гордо именуется «Теоремой и знакомых (друзьях) и незнакомых» (Theorem on Friends and Strangers) а по-русски это просто задача о знакомствах среди шести человек: Среди шести человек всегда найдется либо трое попарно знакомых, либо трое попарно незнакомых...

Теории Рамсея — математическая задача, которая ставит математиков в тупик (хоть прогресс и есть) уже почти столетие. Это сложная область, занимающаяся вопросами порядка в кажущихся случайными структурах. Но исследователи из Калифорнийского университета в Сан-Диего разгадали давнюю проблему: r (4,t). Теория Рамсея сводится к поиску скрытой организации в графах — совокупностях точек, соединенных линиями. Теория утверждает, что если граф достаточно велик, то он будет содержать определенный вид порядка — либо группу точек, полностью соединенных линиями (клика), либо группу без связей...