Теорема Семереди – Троттера

Теорема Семереди — Троттера — результат комбинаторной геометрии.Теорема утверждает, что если даны n точек и m прямых на плоскости, число инциденций (т.е. число пар точка/прямая, в которых точка лежит на прямой) равно и эта граница не может быть улучшена. Эквивалентная формулировка теоремы следующая. Если задано n точек и целое число k > 2, число прямых, проходящих по меньшей мере через k точек, равно Первоначальное доказательство Семереди и было сложным и использовало комбинаторную технику, известную как разделение ячеек. Позднее Секей обнаружил существенно более простое доказательство, использующее неравенство числа пересечений для графов (см. ниже). Теорема Семереди – Троттера имеет несколько следствий, включая в геометрии инцидентности.