Теорема Семереді — Троттера

Теорема Семереді — Троттера — результат комбінаторної геометрії. Теорема стверджує, що якщо дано n точок та m прямих на площині, кількість інциденцій (тобто, кількість пар точка/пряма, в яких точка лежить на прямій) дорівнює

${\displaystyle O\left(n^{\frac {2}{3}}m^{\frac {2}{3}}+n+m\right),}$

і цю межу неможливо покращити.

Еквівалентне формулювання теореми таке. Якщо дано n точок та ціле число k > 2, число прямих, що проходять принпаймні через k точок, дорівнює

${\displaystyle O\left({\frac {n^{2}}{k^{3}}}+{\frac {n}{k}}\right).}$

Початкове доведення Семереді та Троттера^[en][1] було складним і спиралось на комбінаторну техніку, відому як поділ комірок. Пізніше Секей виявив значно простіше доведення, що використовує нерівність числа схрещень для графів^[2] (див. нижче).

Теорема Семереді — Троттера має кілька наслідків, серед яких теорема Бека^[en] в геометрії інцидентності.

Доведення першого формулювання

Ми можемо відкинути прямі, що містять дві і менше точок, оскільки вони можуть дати максимум 2m інциденцій. Отже, можна вважати, що будь-яка пряма містить принаймні три точки.

Якщо пряма містить k точок, то вона містить k − 1 відрізків, що з'єднують дві з n точок. Зокрема, пряма міститиме принаймні k / 2 таких відрізків, оскільки ми припустили, що k ≥ 3. Підрахувавши всі такі інциденції за всіма m прямими, маємо, що число відрізків, отриманих у такий спосіб, принаймні дорівнює половині числа всіх інциденцій. Якщо позначити через e число таких відрізків, достатньо показати, що

${\displaystyle e=O\left(n^{\frac {2}{3}}m^{\frac {2}{3}}+n+m\right).}$

Розглянемо тепер граф, утворений n точками як вершинами і e відрізками як реберами. Оскільки кожен відрізок лежить на якійсь із m прямих і дві прямі перетинаються максимум в одній точці, число схрещень цього графа не перевищує m². З нерівності числа схрещень робимо висновок, що або e ≤ 7.5n або m² ≥ e³ / 33.75n². В будь-якому випадку e ≤ 3.24(nm)^2/3 + 7.5n і ми маємо необхідну межу

${\displaystyle e=O\left(n^{\frac {2}{3}}m^{\frac {2}{3}}+n+m\right).}$

Доведення другого формулювання

Оскільки будь-яку пару точок можна з'єднати максимум однією прямою, може бути максимум n(n − 1)/2 l прямих, які можуть з'єднувати k або більше точок, оскільки k ≥ 2. Ця межа доводить теорему за малих k (наприклад, якщо k ≤ C для деякої абсолютної сталої C). Таким чином, є сенс розглядати лише випадки, коли k велике, скажімо, k ≥ C.

Припустимо, що є m прямих, кожна з яких містить принаймні k точок. Ці прямі утворюють принаймніmk інциденцій, а тоді за першим варіантом теореми Семереді — Троттера маємо

${\displaystyle mk=O\left(n^{\frac {2}{3}}m^{\frac {2}{3}}+n+m\right),}$

і принаймні виконується одна рівність із ${\displaystyle mk=O(n^{2/3}m^{2/3}),mk=O(n)}$ або ${\displaystyle mk=O(m)}$. Третю можливість відкидаємо, оскільки ми припустили, що k велике, тому залишаються дві перші. Але в обох випадках після нескладних алгебричних викладок отримаємо ${\displaystyle m=O(n^{2}/k^{3}+n/k)}$ що й було потрібно.

Оптимальність

Якщо не зважати на сталі множники, межу числа інциденцій Семереді — Троттера не можна покращити. Щоб це побачити, розглянемо для будь-якого додатного цілого числа N ∈ Z⁺ множину точок цілісної ґрати

${\displaystyle P=\left\{(a,b)\in \mathbf {Z} ^{2}\$ :\ 1\leq a\leq N;1\leq b\leq 2N^{2}\right\},}

та набір прямих

${\displaystyle L=\left\{(x,mx+b)\$ :\ m,b\in \mathbf {Z} ;1\leq m\leq N;1\leq b\leq N^{2}\right\}.}

Зрозуміло, що ${\displaystyle |P|=2N^{3}}$ і ${\displaystyle |L|=N^{3}}$. Оскільки кожна пряма інцидентна N точкам (тобто один раз для кожного ${\displaystyle x\in \{1,\cdots ,N\}}$), число інциденцій дорівнює ${\displaystyle N^{4}}$, що відповідає верхній межі^[3].

Узагальнення для Rd

Узагальнення цього результату для довільної розмірності R^d знайшли Агавал та Аронов^[4]. Якщо дано множину S, що містить n точок, і множину H, що містить m гіперплощин, число інциденцій точок із S і гіперплощин із H обмежено зверху числом

${\displaystyle O\left(m^{\frac {2}{3}}n^{\frac {d}{3}}+n^{d-1}\right).}$

Еквівалентно, кількість гіперплощин із H, що містять k і більше точок, обмежена зверху числом

${\displaystyle O\left({\frac {n^{d}}{k^{3}}}+{\frac {n^{d-1}}{k}}\right).}$

Побудова Едельбруннера показує, що межа асимптотично оптимальна^[5].

Шоймоші та Тао отримали майже точну верхню межу для числа інциденцій між точками та алгебричними многовидами в просторах високої розмірності. У доведенні вони використали теорему про бутерброд^[6].

Програми

Теорема Семереді — Троттера знаходить багато застосувань у адитивній^[7][8][9] та арифметичній комбінаториці (наприклад, для доведення теореми сум-добутків^[10]).