Как доказать, что определенный математический объект существует, если вы не можете его построить или привести ни одного конкретного примера? Венгерский математик Пал Эрдёш, один из самых плодовитых ученых XX века, совершил революцию в комбинаторике, создав "Вероятностный метод". Он показал, что случайность можно использовать не только в алгоритмах, но и для получения строгих, абсолютно детерминированных математических доказательств.

Традиционная теория графов моделирует мир в виде парных отношений: дружба между двумя людьми, кабель между двумя серверами, дорога между двумя городами. Но что, если отношение связывает сразу три, четыре или сотню объектов одновременно? Например, несколько соавторов одной научной статьи или группа актеров в одном фильме. Для описания таких многомерных связей дискретная математика использует расширение классической теории — Гиперграфы.

Когда мы исследуем свойства графов, иногда нам мешают лишние детали: мелкие ответвления или промежуточные узлы на длинных путях. Чтобы увидеть фундаментальную "скелетную" структуру сети, математики ввели понятие минора графа. Теория миноров графов увенчалась одним из самых масштабных и сложных доказательств в истории математики — Теоремой Робертсона-Сеймура, которая перевернула наши представления об алгоритмической сложности.