Теорема Семереді — Троттера — результат комбінаторної геометрії. Теорема стверджує, що якщо дано n точок та m прямих на площині, кількість інциденцій (тобто, кількість пар точка/пряма, в яких точка лежить на прямій) дорівнює
і цю межу неможливо покращити.
Еквівалентне формулювання теореми таке. Якщо дано n точок та ціле число k > 2, число прямих, що проходять принпаймні через k точок, дорівнює
Початкове доведення Семереді та [en] було складним і спиралось на комбінаторну техніку, відому як поділ комірок. Пізніше Секей виявив значно простіше доведення, що використовує нерівність числа схрещень для графів (див. нижче).
Теорема Семереді — Троттера має кілька наслідків, серед яких [en] в геометрії інцидентності.
Доведення першого формулювання
Ми можемо відкинути прямі, що містять дві і менше точок, оскільки вони можуть дати максимум 2m інциденцій. Отже, можна вважати, що будь-яка пряма містить принаймні три точки.
Якщо пряма містить k точок, то вона містить k − 1 відрізків, що з'єднують дві з n точок. Зокрема, пряма міститиме принаймні k / 2 таких відрізків, оскільки ми припустили, що k ≥ 3. Підрахувавши всі такі інциденції за всіма m прямими, маємо, що число відрізків, отриманих у такий спосіб, принаймні дорівнює половині числа всіх інциденцій. Якщо позначити через e число таких відрізків, достатньо показати, що
Розглянемо тепер граф, утворений n точками як вершинами і e відрізками як реберами. Оскільки кожен відрізок лежить на якійсь із m прямих і дві прямі перетинаються максимум в одній точці, число схрещень цього графа не перевищує m2. З нерівності числа схрещень робимо висновок, що або e ≤ 7.5n або m2 ≥ e3 / 33.75n2. В будь-якому випадку e ≤ 3.24(nm)2/3 + 7.5n і ми маємо необхідну межу
Доведення другого формулювання
Оскільки будь-яку пару точок можна з'єднати максимум однією прямою, може бути максимум n(n − 1)/2 l прямих, які можуть з'єднувати k або більше точок, оскільки k ≥ 2. Ця межа доводить теорему за малих k (наприклад, якщо k ≤ C для деякої абсолютної сталої C). Таким чином, є сенс розглядати лише випадки, коли k велике, скажімо, k ≥ C.
Припустимо, що є m прямих, кожна з яких містить принаймні k точок. Ці прямі утворюють принаймніmk інциденцій, а тоді за першим варіантом теореми Семереді — Троттера маємо
і принаймні виконується одна рівність із або . Третю можливість відкидаємо, оскільки ми припустили, що k велике, тому залишаються дві перші. Але в обох випадках після нескладних алгебричних викладок отримаємо що й було потрібно.
Оптимальність
Якщо не зважати на сталі множники, межу числа інциденцій Семереді — Троттера не можна покращити. Щоб це побачити, розглянемо для будь-якого додатного цілого числа N ∈ Z+ множину точок цілісної ґрати
та набір прямих
Зрозуміло, що і . Оскільки кожна пряма інцидентна N точкам (тобто один раз для кожного ), число інциденцій дорівнює , що відповідає верхній межі.
Узагальнення для Rd
Узагальнення цього результату для довільної розмірності Rd знайшли Агавал та Аронов. Якщо дано множину S, що містить n точок, і множину H, що містить m гіперплощин, число інциденцій точок із S і гіперплощин із H обмежено зверху числом
Еквівалентно, кількість гіперплощин із H, що містять k і більше точок, обмежена зверху числом
Побудова Едельбруннера показує, що межа асимптотично оптимальна.
Шоймоші та Тао отримали майже точну верхню межу для числа інциденцій між точками та алгебричними многовидами в просторах високої розмірності. У доведенні вони використали теорему про бутерброд.
Програми
Теорема Семереді — Троттера знаходить багато застосувань у адитивній та арифметичній комбінаториці (наприклад, для доведення теореми сум-добутків).
Примітки
- Szemerédi, Trotter, 1983, с. 381–392.
- Székely, 1997, с. 353–358.
- Tao, 2011.
- Agarwal, Aronov, 1992, с. 359–369.
- Edelsbrunner, 1987.
- Solymosi, Tao, 2012.
- Tomasz Schoen, Ilya Shkredov, «On Sumsets of Convex Sets»
- A. Iosevich, S. Konyagin, M. Rudnev, and V. Ten, «On combinatorial complexity of convex sequences», July 19, 2004
- (PDF). Архів оригіналу (PDF) за 12 червня 2018. Процитовано 19 листопада 2018.
- G. Elekes, On the number of sums and products, Acta Arith. 81 (1997), 365—367.
Література
- Endre Szemerédi, William T. Trotter. Extremal problems in discrete geometry // Combinatorica. — 1983. — Т. 3, вип. 3–4. — С. 381–392. — DOI: .
- László A. Székely. Crossing numbers and hard Erdős problems in discrete geometry // . — 1997. — Т. 6, вип. 3. — С. 353–358. — DOI: .
- Terence Tao. An incidence theorem in higher dimensions. — 2011. Процитовано 26 серпня 2012.
- Pankaj Agarwal, Boris Aronov. Counting facets and incidences // . — Springer, 1992. — Т. 7, вип. 1. — С. 359–369. — DOI: .
- Herbert Edelsbrunner. 6.5 Lower bounds for many cells // Algorithms in Combinatorial Geometry. — Springer-Verlag, 1987. — .
- J. Solymosi, Terence Tao. An incidence theorem in higher dimensions // . — 2012. — Т. 48, вип. 2. — DOI: .
Додаткова література
- Фёдор Нилов, Александр Полянский, Никита Полянский,. 26-я летняя конференция международного математического Турнира городов (02.08.2014-11.08.2014). — Калининград-Ушаково, 2014.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Teorema Semeredi Trottera rezultat kombinatornoyi geometriyi Teorema stverdzhuye sho yaksho dano n tochok ta m pryamih na ploshini kilkist incidencij tobto kilkist par tochka pryama v yakih tochka lezhit na pryamij dorivnyuye O n 2 3 m 2 3 n m displaystyle O left n frac 2 3 m frac 2 3 n m right i cyu mezhu nemozhlivo pokrashiti Ekvivalentne formulyuvannya teoremi take Yaksho dano n tochok ta cile chislo k gt 2 chislo pryamih sho prohodyat prinpajmni cherez k tochok dorivnyuye O n 2 k 3 n k displaystyle O left frac n 2 k 3 frac n k right Pochatkove dovedennya Semeredi ta en bulo skladnim i spiralos na kombinatornu tehniku vidomu yak podil komirok Piznishe Sekej viyaviv znachno prostishe dovedennya sho vikoristovuye nerivnist chisla shreshen dlya grafiv div nizhche Teorema Semeredi Trottera maye kilka naslidkiv sered yakih en v geometriyi incidentnosti Dovedennya pershogo formulyuvannyaMi mozhemo vidkinuti pryami sho mistyat dvi i menshe tochok oskilki voni mozhut dati maksimum 2m incidencij Otzhe mozhna vvazhati sho bud yaka pryama mistit prinajmni tri tochki Yaksho pryama mistit k tochok to vona mistit k 1 vidrizkiv sho z yednuyut dvi z n tochok Zokrema pryama mistitime prinajmni k 2 takih vidrizkiv oskilki mi pripustili sho k 3 Pidrahuvavshi vsi taki incidenciyi za vsima m pryamimi mayemo sho chislo vidrizkiv otrimanih u takij sposib prinajmni dorivnyuye polovini chisla vsih incidencij Yaksho poznachiti cherez e chislo takih vidrizkiv dostatno pokazati sho e O n 2 3 m 2 3 n m displaystyle e O left n frac 2 3 m frac 2 3 n m right Rozglyanemo teper graf utvorenij n tochkami yak vershinami i e vidrizkami yak reberami Oskilki kozhen vidrizok lezhit na yakijs iz m pryamih i dvi pryami peretinayutsya maksimum v odnij tochci chislo shreshen cogo grafa ne perevishuye m2 Z nerivnosti chisla shreshen robimo visnovok sho abo e 7 5n abo m2 e3 33 75n2 V bud yakomu vipadku e 3 24 nm 2 3 7 5n i mi mayemo neobhidnu mezhu e O n 2 3 m 2 3 n m displaystyle e O left n frac 2 3 m frac 2 3 n m right Dovedennya drugogo formulyuvannyaOskilki bud yaku paru tochok mozhna z yednati maksimum odniyeyu pryamoyu mozhe buti maksimum n n 1 2 l pryamih yaki mozhut z yednuvati k abo bilshe tochok oskilki k 2 Cya mezha dovodit teoremu za malih k napriklad yaksho k C dlya deyakoyi absolyutnoyi staloyi C Takim chinom ye sens rozglyadati lishe vipadki koli k velike skazhimo k C Pripustimo sho ye m pryamih kozhna z yakih mistit prinajmni k tochok Ci pryami utvoryuyut prinajmnimk incidencij a todi za pershim variantom teoremi Semeredi Trottera mayemo m k O n 2 3 m 2 3 n m displaystyle mk O left n frac 2 3 m frac 2 3 n m right i prinajmni vikonuyetsya odna rivnist iz m k O n 2 3 m 2 3 m k O n displaystyle mk O n 2 3 m 2 3 mk O n abo m k O m displaystyle mk O m Tretyu mozhlivist vidkidayemo oskilki mi pripustili sho k velike tomu zalishayutsya dvi pershi Ale v oboh vipadkah pislya neskladnih algebrichnih vikladok otrimayemo m O n 2 k 3 n k displaystyle m O n 2 k 3 n k sho j bulo potribno OptimalnistYaksho ne zvazhati na stali mnozhniki mezhu chisla incidencij Semeredi Trottera ne mozhna pokrashiti Shob ce pobachiti rozglyanemo dlya bud yakogo dodatnogo cilogo chisla N Z mnozhinu tochok cilisnoyi grati P a b Z 2 1 a N 1 b 2 N 2 displaystyle P left a b in mathbf Z 2 1 leq a leq N 1 leq b leq 2N 2 right ta nabir pryamih L x m x b m b Z 1 m N 1 b N 2 displaystyle L left x mx b m b in mathbf Z 1 leq m leq N 1 leq b leq N 2 right Zrozumilo sho P 2 N 3 displaystyle P 2N 3 i L N 3 displaystyle L N 3 Oskilki kozhna pryama incidentna N tochkam tobto odin raz dlya kozhnogo x 1 N displaystyle x in 1 cdots N chislo incidencij dorivnyuye N 4 displaystyle N 4 sho vidpovidaye verhnij mezhi Uzagalnennya dlya RdUzagalnennya cogo rezultatu dlya dovilnoyi rozmirnosti Rd znajshli Agaval ta Aronov Yaksho dano mnozhinu S sho mistit n tochok i mnozhinu H sho mistit m giperploshin chislo incidencij tochok iz S i giperploshin iz H obmezheno zverhu chislom O m 2 3 n d 3 n d 1 displaystyle O left m frac 2 3 n frac d 3 n d 1 right Ekvivalentno kilkist giperploshin iz H sho mistyat k i bilshe tochok obmezhena zverhu chislom O n d k 3 n d 1 k displaystyle O left frac n d k 3 frac n d 1 k right Pobudova Edelbrunnera pokazuye sho mezha asimptotichno optimalna Shojmoshi ta Tao otrimali majzhe tochnu verhnyu mezhu dlya chisla incidencij mizh tochkami ta algebrichnimi mnogovidami v prostorah visokoyi rozmirnosti U dovedenni voni vikoristali teoremu pro buterbrod ProgramiTeorema Semeredi Trottera znahodit bagato zastosuvan u aditivnij ta arifmetichnij kombinatorici napriklad dlya dovedennya teoremi sum dobutkiv PrimitkiSzemeredi Trotter 1983 s 381 392 Szekely 1997 s 353 358 Tao 2011 Agarwal Aronov 1992 s 359 369 Edelsbrunner 1987 Solymosi Tao 2012 Tomasz Schoen Ilya Shkredov On Sumsets of Convex Sets A Iosevich S Konyagin M Rudnev and V Ten On combinatorial complexity of convex sequences July 19 2004 PDF Arhiv originalu PDF za 12 chervnya 2018 Procitovano 19 listopada 2018 G Elekes On the number of sums and products Acta Arith 81 1997 365 367 LiteraturaEndre Szemeredi William T Trotter Extremal problems in discrete geometry Combinatorica 1983 T 3 vip 3 4 S 381 392 DOI 10 1007 BF02579194 Laszlo A Szekely Crossing numbers and hard Erdos problems in discrete geometry 1997 T 6 vip 3 S 353 358 DOI 10 1017 S0963548397002976 Terence Tao An incidence theorem in higher dimensions 2011 Procitovano 26 serpnya 2012 Pankaj Agarwal Boris Aronov Counting facets and incidences Springer 1992 T 7 vip 1 S 359 369 DOI 10 1007 BF02187848 Herbert Edelsbrunner 6 5 Lower bounds for many cells Algorithms in Combinatorial Geometry Springer Verlag 1987 ISBN 3 540 13722 X J Solymosi Terence Tao An incidence theorem in higher dimensions 2012 T 48 vip 2 DOI 10 1007 s00454 012 9420 x Dodatkova literaturaFyodor Nilov Aleksandr Polyanskij Nikita Polyanskij 26 ya letnyaya konferenciya mezhdunarodnogo matematicheskogo Turnira gorodov 02 08 2014 11 08 2014 Kaliningrad Ushakovo 2014