Экстремальная комбинаторика — область комбинаторики , которая сама является частью математики . Экстремальная комбинаторика изучает, насколько большим или маленьким может быть набор конечных объектов ( чисел , графиков , векторов , наборов и т. д.), если он должен удовлетворять определенным ограничениям.
Большая часть экстремальной комбинаторики касается классов множеств; это называется экстремальной теорией множеств . Например, в наборе из n элементов, каково наибольшее число подмножеств из k элементов , которые могут попарно пересекаться друг с другом? Каково наибольшее количество подмножеств, ни одно из которых не содержит другого? На последний вопрос отвечает теорема Шпернера , которая дала начало большей части экстремальной теории множеств.
Другой пример: сколько человек можно пригласить на вечеринку, где среди каждых трех человек есть двое знакомых и двое незнакомых друг с другом? Теория Рамсея показывает, что на такой вечеринке могут присутствовать не более пяти человек. Или предположим, что нам дан конечный набор ненулевых целых чисел, и нас просят отметить как можно большее подмножество этого набора с условием, что сумма любых двух отмеченных целых чисел не может быть отмечена. Оказывается, (независимо от того, каковы на самом деле заданные целые числа) мы всегда можем отметить по крайней мере одну треть из них.