Экстремальная комбинаторика

Экстремальная комбинаторика — область комбинаторики , которая сама является частью математики . Экстремальная комбинаторика изучает, насколько большой или маленькой может быть совокупность конечных объектов ( числ , графов , векторов , множеств и т. д.), если она должна удовлетворять определенным ограничениям.

Большая часть экстремальной комбинаторики касается классов множеств; это называется экстремальной теорией множеств . Например, в наборе из n элементов каково наибольшее число из k -элементов подмножеств , которые могут попарно пересекаться друг с другом? Каково наибольшее число подмножеств, из которых ни одно не содержит другого? На последний вопрос отвечает теорема Спернера , которая положила начало большей части экстремальной теории множеств.

Другой пример: сколько человек можно пригласить на вечеринку, где среди каждых трех человек двое знают друг друга, а двое не знают друг друга? Теория Рэмси показывает, что на такой вечеринке могут присутствовать не более пяти человек. Или предположим, что нам дан конечный набор ненулевых целых чисел и нас просят пометить как можно большее подмножество этого набора при условии, что сумма любых двух помеченных целых чисел не может быть помечена. Оказывается, (независимо от того, какими на самом деле являются данные целые числа) мы всегда можем отметить хотя бы одну треть из них.

См. также

• Экстремальная теория графов
• Лемма Зауэра – Шелы
• Теорема Эрдеша – Ко – Радо
• Теорема Краскала – Катона
• Неравенство Фишера
• Гипотеза о замкнутых множествах

Ссылки

• Юкна, Стасис (2011), Экстремальная комбинаторика, с приложениями в информатике , Springer Verlag, ISBN  978-3-642-17363-9 .
• Алон, Нога ; Кривелевич, Михаил (2006), Экстремальная и вероятностная комбинаторика (PDF) .
• Франкл, Питер ; Рёдль, Войтех (1987), «Запрещенные пересечения», Труды Американского математического общества , 300 (1): 259–286, doi : 10.2307/2000598 .