Кіріспе

Ұшақтағы нүктелер мен сызықтар арасындағы оқиғалар санымен шектелген Шземереди-Троттер теоремасы – дискретті геометрия саласындағы математикалық нәтиже. Ол Евклид жазықтығында n нүкте және m сызық берілген жағдайда, оқиғалар саны (яғни, нүкте-сызық жұптарының саны, мұнда нүкте сызықта жатады) мынадай болады деп тұжырымдайды.

Бұл шекті, жасырын тұрақтыларды ескермегенде, жақсарту мүмкін емес. Жасырын тұрақтыларға қатысты, Янош Пах, Радош Радоичич, Габор Тардос және Геза Тот жоғары шектің сақталуын көрсетті. Содан бері, жақсы қиылысу леммасы тұрақтыларының арқасында жақсы тұрақтылар белгілі болды; қазіргі ең жақсы көрсеткіш – 2,44. Екінші жағынан, Пах және Тот 2,5 коэффициентін 0,42-ге алмастырғанда, бұл тұжырымның дұрыс еместігін көрсетті. Теореманың баламалы формулировкасы төмендегідей: n нүкте және k ≥ 2 бүтін саны берілгенде, кем дегенде k нүктеден өтетін сызықтардың саны:

Эндре Сземереди мен Уильям Т. Троттердің бастапқы дәлелі біршама күрделі болды, ол жасушалық декомпозиция деп аталатын комбинаторлық әдіс қолданды. Кейін Ласло Секели, графтар үшін қиылысу санының теңсіздігін пайдаланып, әлдеқайда қарапайым дәлел тапты. (Төменде қараңыз.) Шземереди-Троттер теоремасының көптеген салдары бар, оның ішінде инциденттік геометриядағы Бек теоремасы және қосымша комбинаторикадағы Эрдёш-Сземереди қосынды-көбейтінді мәселесі бар.

Бірінші сөзді дәлелдеу

Біз екі немесе одан аз нүктелерді қамтитын түзулерді жоюға болады, өйткені олар жалпы санына 2m-ге дейін ғана үлес қоса алады. Осылайша, әрбір түзу кем дегенде үш нүктеден тұрады деп есептеуге болады. Егер түзуде k нүкте болса, онда ол түзу бойымен екі тікелей жатқан нүктелерді қосатын k - 1 түзу кесіндісін қамтиды. Екі нүктелі түзулерді жоюдан кейін k ≥ 3 болғандықтан, k − 1 ≥ k/2 болады, сондықтан әрбір түзудегі осы түзу кесінділерінің саны сол түзудегі оқиғалардың санының кем дегенде жартысына тең. Барлық түзулер бойынша қосымша есептегенде, осы түзу кесінділерінің саны да жалпы оқиғалардың санының жартысына тең болады. Егер e осындай түзу кесінділерінің санын білдірсе, онда n нүктені төбелер ретінде және e түзу кесінділерін қабырғалар ретінде пайдаланып құрылған графты қарастырайық. Әрбір түзу кесіндісі m түзудің бірінде жатқандықтан және кез келген екі түзу ең көп дегенде бір нүктеде қиылысады, осы графтың қиылысу саны ең көп дегенде екі түзудің қиылысатын нүктелерінің санына тең, яғни ең көп дегенде m(m − 1)/2. Қиылысу санының теңсіздігі e ≤ 7.5n немесе m(m − 1)/2 ≥ e³/33.75n² дегенді білдіреді. Екі жағдайда да e ≤ 3.24(nm)^(2/3) + 7.5n, бұл қажетті шектемені береді.

Екінші формулировканың дәлелі

Әрбір екі нүкте ең көп дегенде бір түзумен қосыла алатындықтан, k немесе одан да көп нүктені байланыстыратын түзулердің саны n(n − 1)/2-ден аспауы мүмкін, себебі k ≥ 2. Бұл шектеу k кішкентай болғанда теореманы дәлелдейді (мысалы, егер k ≤ C болса, мұнда C – абсолютті тұрақты шама). Осылайша, біз тек k үлкен болған жағдайды қарастыруымыз керек, мысалы k ≥ C.

Кем дегенде k нүктесі бар m түзу бар деп есептейік. Бұл түзулер кем дегенде mk инциденттіліктерді тудырады, сондықтан Семереди-Троттер теоремасының бірінші формулировкасы бойынша бізде:

және кем дегенде бір мына мәлімдемелердің бірі дұрыс: немесе . Үшінші мүмкіндік жоққа шығарылды, өйткені k үлкен деп есептелді, сондықтан біз бірінші екісімен ғана қалдық. Бірақ осы екі жағдайдың екеуінде де қарапайым алгебралық амалдар арқылы қажетті шектеуді алуға болады.

Жалпылау

Агарвал мен Ароновтың тағайындалған өлшемге, *d*, қатысты осы нәтиженің жалпылама түрін табуға қол жеткізді. *n* нүктелер жиыны *S* және *S* арқылы анықталатын *m* гипержазықтықтар жиыны *H* берілгенде, *S* мен *H* арасындағы инциденттер саны келесімен шектеледі:

, егер . Балама ретінде, *H* жиынында *k* немесе одан көп нүктелерді қамтитын гипержазықтықтар саны келесімен шектеледі:

Эдельсбруннердің құрастыруы осы шектің асимптотикалық жағынан ең жақсы екенін көрсетеді. Жозеф Солимоси мен Теренс Тао нүктелер мен алгебралық қисықтар арасындағы жоғары өлшемдердегі инциденттер саны үшін жақын оптимал жоғарғы шектерге қол жеткізді, егер нүктелер мен қисықтар "белгілі бір псевдо-сызықтық аксиомаларды" қанағаттандырса. Олардың дәлелі Полиномдық Хам сэндвич теоремасын пайдаланады.

Ішінде

Szemerédi–Trotter теоремасының көптеген дәлелдемелері Евклид кеңістігінің топологиясына маңызды дәрежеде сүйенеді, сондықтан басқа өрістерге оңай көшпейді. Мысалы, Szemerédi және Trotter-дің бастапқы дәлелі; полиномдық бөлу дәлелі және қиылысу саны дәлелі кешенді жазықтыққа дейін кеңейтілмейді. Тот қосымша идеяларды енгізу арқылы Szemerédi мен Trotter-дің кешенді жазықтықтағы бастапқы дәлелін сәтті жалпылады. Бұл нәтиже де Zahl тәуелсіз түрде және басқа әдіспен алынған. Шектеудегі тұрақты комплекс сандардағыдан өзгеше: Тоттың дәлелінде тұрақтыны алуға болады; ал Zahl-дың дәлелінде тұрақты нақты көрсетілмеген. Егер нүктелер жиыны Декарт көбейтіндісі болса, Соломоси мен Тардос Szemerédi–Trotter шегінің әлдеқайда қарапайым аргументпен сақталады екенін көрсетеді.

Шекті өрістерде

Дала болсын. Szemerédi-Троттер шегі жалпы жағдайда келесі мысалға байланысты мүмкін емес, ол мына жерде келтірілген: болсын – барлық нүктелер жиыны, ал – жазықтықтағы барлық түзулер жиыны. Әрбір түзу нүктелерді қамтитындықтан, оқиғалар саны болады. Ал Szemerédi-Троттер шегі оқиғалар саны береді. Бұл мысал тривиальді, комбинаторлық оқиғалар шегінің дұрыс екенін көрсетеді. Бургейн, Кац және Тао бұл мысал ескерілмесе, тривиальді шектен жақсырақ оқиғалар шегіне қол жеткізуге болатынын көрсетті. Шекті өрістердегі оқиғалар шектері екі түрлі болады: (i) нүктелер немесе түзулер жиынының кем дегенде біреуі өрістің сипаттамасына қатысты «үлкен» болса; (ii) нүктелер және түзулер жиындары екеуі де сипаттамаға қатысты «кішкентай» болса.

Үлкен шекті жиілік

Келіңіз, p – тақ санның қуаты болсын. Содан кейін Винх p жазықтығындағы n нүкте мен m түзу арасындағы кездесулер санының ең көп саны екенін көрсетті.

Бұл шекте жасырын тұрақты жоқ екенін ескеріңіз.

Кішігірім белгіленетін жиілік шегі

Болсын – сипаттамасы бар өріс. Стивенс пен де Зеуу көрсеткендей, оң сипаттама жағдайында, нүкте және сызық арасындағы оқиғалар саны:

. (Сипаттамасы нөлдік өрісте бұл шарт қажет емес.) Бұл шектеу тривиальды оқиғалар бағалауынан жақсырақ, егер . Егер нүктелер жиыны Картезиандық көбейту болса, онда олар оқиғалар шегін жақсартады: нүктелердің шекті жиыны және жазықтықтағы сызықтар жиыны болсын. Егер және оң сипаттамада болса, онда және арасындағы оқиғалар саны:

Бұл шектеу оңтайлы. Жазықтықтағы нүкте-сызық дуалдылығы бойынша, бұл оқиғалар шегін кез келген нүктелер жиыны және Картезиандық көбейту құрылымына ие сызықтар жиыны үшін қайта формулировать етіп беруге болады. Нақты және кез келген өрістерде Руднев пен Шкредов нүктелер және сызықтар жиынының екеуі де Картезиандық көбейту құрылымына ие болғандағы оқиғалар шегін көрсетеді. Бұл кейде жоғарыдағы шектерден жақсырақ.