Экстремальная комбинаторика - это область комбинаторики , которая сама по себе является частью математики . Экстремальная комбинаторика изучает, насколько велик или насколько мал может быть набор конечных объектов ( чисел , графов , векторов , множеств и т. Д.), Если он должен удовлетворять определенным ограничениям.
Большая часть экстремальной комбинаторики касается классов множеств; это называется экстремальной теорией множеств . Например, в п - элементного множества, что наибольшее число K - элементных подмножеств , которые могут попарно пересекаются друг с другом? Каково наибольшее количество подмножеств, из которых ни одно не содержит других? На последний вопрос отвечает теорема Спернера , которая дала начало большей части теории экстремальных множеств.
Другой пример: сколько людей мы можем пригласить на вечеринку, где среди каждых трех человек есть двое, которые знают друг друга, и двое, которые не знают друг друга? Теория Рамсея показывает, что на такой вечеринке могут присутствовать не более пяти человек. Или предположим, что нам дан конечный набор ненулевых целых чисел и просят пометить как можно большее подмножество этого набора с ограничением, что сумма любых двух отмеченных целых чисел не может быть помечена. Похоже, что (независимо от того, какими на самом деле являются данные целые числа!), Мы всегда можем отметить как минимум одну треть из них.
См. Также [ править ]
- Экстремальная теория графов
- Лемма Зауэра – Шелаха.
- Теорема Эрдеша – Ко – Радо.
- Теорема Крускала – Катоны
- Неравенство Фишера
- Гипотеза о замкнутых множествах
Ссылки [ править ]
- Юкна, Стасис (2011), Экстремальная комбинаторика, с приложениями в компьютерных науках , Birkhäuser Verlag, ISBN 3-540-66313-4.
- Алон, Нога ; Кривелевич, Майкл (2006), Экстремальная и вероятностная комбинаторика (PDF).
- Франкл, Питер ; Редль, Войтех (1987), "Запрещенные перекрестки", Труды Американского математического общества , 300 (1): 259-286, DOI : 10,2307 / 2000598.
