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

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

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

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

Еквівалентне формулювання теореми таке. Якщо дано Шаблон:Mvar точок та ціле число Шаблон:Math, число прямих, що проходять принпаймні через Шаблон:Mvar точок, дорівнює

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

Початкове доведення Семереді та Шаблон:Не перекладеноШаблон:Sfn було складним і спиралось на комбінаторну техніку, відому як поділ комірок. Пізніше Секей виявив значно простіше доведення, що використовує нерівність числа схрещень для графівШаблон:Sfn (див. нижче).

Теорема Семереді — Троттера має кілька наслідків, серед яких Шаблон:Не перекладено в геометрії інцидентності.

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

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

Якщо пряма містить Шаблон:Mvar точок, то вона містить Шаблон:Math відрізків, що з'єднують дві з Шаблон:Mvar точок. Зокрема, пряма міститиме принаймні Шаблон:Math таких відрізків, оскільки ми припустили, що Шаблон:Math. Підрахувавши всі такі інциденції за всіма Шаблон:Mvar прямими, маємо, що число відрізків, отриманих у такий спосіб, принаймні дорівнює половині числа всіх інциденцій. Якщо позначити через Шаблон:Mvar число таких відрізків, достатньо показати, що

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

Розглянемо тепер граф, утворений Шаблон:Mvar точками як вершинами і e відрізками як реберами. Оскільки кожен відрізок лежить на якійсь із Шаблон:Mvar прямих і дві прямі перетинаються максимум в одній точці, число схрещень цього графа не перевищує Шаблон:Math. З нерівності числа схрещень робимо висновок, що або Шаблон:Math або Шаблон:Math. В будь-якому випадку Шаблон:Math і ми маємо необхідну межу

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

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

Оскільки будь-яку пару точок можна з'єднати максимум однією прямою, може бути максимум Шаблон:Math l прямих, які можуть з'єднувати Шаблон:Mvar або більше точок, оскільки Шаблон:Math. Ця межа доводить теорему за малих Шаблон:Mvar (наприклад, якщо Шаблон:Math для деякої абсолютної сталої Шаблон:Mvar). Таким чином, є сенс розглядати лише випадки, коли Шаблон:Mvar велике, скажімо, Шаблон:Math.

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

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

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

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

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

$P=\{(a,b)\in {𝐙}^2:1\le a\le N;1\le b\le 2N^2\},$

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

$L=\{(x,mx+b):m,b\in 𝐙;1\le m\le N;1\le b\le N^2\}.$

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

Узагальнення для Шаблон:Math

Узагальнення цього результату для довільної розмірності Шаблон:Math знайшли Агавал та АроновШаблон:Sfn. Якщо дано множину Шаблон:Mvar, що містить Шаблон:Mvar точок, і множину Шаблон:Mvar, що містить Шаблон:Mvar гіперплощин, число інциденцій точок із Шаблон:Mvar і гіперплощин із Шаблон:Mvar обмежено зверху числом

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

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

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

Побудова Едельбруннера показує, що межа асимптотично оптимальнаШаблон:Sfn.

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

Програми

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

Література

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Стаття

Додаткова література

• Шаблон:Стаття