Экстремальная теория графов: различия между версиями

Экстремальная теория графов возникла в 1941, когда Туран доказал [[Теорема Турана|свою теорему]], определяющую графы порядка ''n'', не содержащие полного графа ''K''_''k'' порядка k, и экстремальные относительно размера (то есть, с как можно меньшим числом рёбер) {{sfn|Bollobás|1998|с=104}}. Следующим ключевым годом стал 1975, когда Семереди доказал [[Теорема Семереди|свою теорему]], важный инструмент для атаки на экстремальные задачи {{sfn|Bollobás|1998|с=104}}.