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

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

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

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

Смотрите также

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

Рекомендации

• Юкна, Стасис (2011), Экстремальная комбинаторика с приложениями в компьютерных науках, Birkhäuser Verlag, ISBN  3-540-66313-4.

• Алон, Нога; Кривелевич Михаил (2006), Экстремальная и вероятностная комбинаторика. (PDF).

• Франкл, Питер; Рёдль, Войтех (1987), «Запрещенные пересечения», Труды Американского математического общества, 300 (1): 259–286, Дои:10.2307/2000598.