Кіріспе
Жазықтықтағы нүктелер жиынымен анықталатын түзулер санының төменгі шектері, әртүрлі автордың дамытқан категориялар теориясы. Дискретті геометрияда Бек теоремасы – бірнеше түрлі нәтижелердің кез келгені, олардың екеуі төменде келтірілген. Екеуі де Йозеф Бектың белгілі мақаласында, басқа бірнеше маңызды теоремалармен бірге жарияланған. Бұл n нүктесінен тұратын конфигурацияларды қамтиды, олардың ең көп дегенде n – k-сы бір түзудің бойында жатады, мұнда 0 < k < O. Олар n саны k-ға қатысты жеткілікті үлкен болса, конфигурация кем дегенде kn – (1/2)(3k + 2)(k – 1) түзуді қамтитынын көрсетті. Элекс және Чаба Тот Ердос-Бек теоремасының жоғары өлшемдерге оңай кеңейтілмейтінін атап өтті. Мысалы, R3 кеңістігіндегі 2n нүктеден тұратын жиынды қарастырайық, барлығы екі қиылыспайтын түзуде жатыр. Егер осы екі түзудің әрқайсысы n нүктеге тиісті болса, онда мұндай нүктелер жиыны тек 2n жазықтықты қамтиды. Осылайша, Rd кеңістігіндегі нүктелер жиынына қатысты гипотезаны тривиалды түрде кеңейту қажетті нәтижеге қол жеткізу үшін жеткіліксіз. Бұл нәтижені алғашқыда Эрдос болжады, ал Бек дәлелдеді. (5.2 теореманы қараңыз.)
the category theory developed by a different author
In discrete geometry, Beck's theorem is any of several different results, two of which are given below. Both appeared, alongside several other important theorems, in a well known paper by József Beck. involving configurations of n points of which at most n − k are collinear, for some 0 < k < O They showed that if n is sufficiently large, relative to k, then the configuration spans at least kn − (1/2)(3k + 2)(k − 1) lines. Elekes and Csaba Toth noted that the Erdős–Beck theorem does not easily extend to higher dimensions. Take for example a set of 2n points in R3 all lying on two skew lines. Assume that these two lines are each incident to n points. Such a configuration of points spans only 2n planes. Thus, a trivial extension to the hypothesis for point sets in Rd is not sufficient to obtain the desired result. This result was first conjectured by Erdős, and proven by Beck. (See Theorem 5.2 in.)
Айтылым
S жазықтықтағы n нүктелер жиыны болсын. Егер кез келген түзуде 0 ≤ k < n - 2 шарты орындалса, n - k нүктеден артық нүкте жатпаса, онда S жиынының нүктелерімен анықталатын Ω(nk) түзу бар.
Бек теоремасы
Бек теоремасы жазықтықтағы шекті нүктелер жиынының екі ең шеткі жағдайдың біріне жататынын айтады: біріншісінде нүктелердің көп бөлігі бір түзу бойында орналасқан, ал екіншісінде барлық нүктелерді байланыстыру үшін көптеген түзулер қажет болады. Бұл нәтиже Бектің мақаласында тікелей айтылмаса да, Эрдос-Бек теоремасынан туындайды.
Дәлел
Бек теоремасының дәлелін келесідей беруге болады. Жазықтықтағы n нүктеден тұратын P жиынын қарастырайық. J оң бүтін сан болсын. P жиынындағы A, B нүктелерінің жұбы j-байланысты деп аталады, егер A мен B нүктелерін қосатын түзу P жиынындағы (A мен B нүктелерін қоса алғанда) арасындағы нүктелерді қамтитын болса. Szemerédi–Trotter теоремасы бойынша, мұндай түзулердің саны келесідей: P жиынындағы n нүкте және P жиынындағы нүктелер жұбымен анықталатын барлық түзулер жиыны L-ді қарастырайық. Екі нүкте екі түрлі түзуде жата алмайтынын ескере отырып, Szemerédi–Trotter теоремасын қолданғанда, P мен L арасындағы инциденттер саны ең көп дегенде болады. j-байланысқан нүктелерді қосатын барлық түзулер де L жиынына жатады, және әрқайсысы кем дегенде инциденттерді қамтамасыз етеді. Сондықтан, мұндай түзулердің жалпы саны: әр түзу нүктелер жұбын байланыстыратындықтан, ең көп дегенде нүктелер жұбы j-байланысқан болуы мүмкін. Енді C үлкен тұрақты сан болсын. Геометриялық прогрессияны қосу арқылы, j-байланысқан нүктелер жұбының саны, егер j шартты қанағаттандырса, ең көп дегенде болады. Екінші жағынан, жұптардың жалпы саны: Егер C-ді жеткілікті үлкен деп таңдасақ, кем дегенде жұпты таба аламыз (мысалы), олар кез келген j үшін j-байланысқан емес. Бұл жұптарды қосатын түзулер 2C-дан аз нүктелер арқылы өтеді немесе n/C-дан көп нүктелер арқылы өтеді. Егер соңғы жағдай осы жұптардың біреуі үшін орындалса, онда Бек теоремасының бірінші қорытындысы орындалады. Сондықтан, барлық жұптар 2C-дан аз нүктелер арқылы өтетін түзулермен байланысқан деп есептеуге болады. Бірақ әр түзу ең көп дегенде нүктелер жұбын байланыстыра алады. Демек, кем дегенде екі нүктені байланыстыратын кем дегенде бір түзу болуы керек, және талап орындалады.
Since each such line connects together pairs of points, we thus see that at most pairs of points can be j connected. Now, let C be a large constant. By summing the geometric series, we see that the number of pairs of points which are j connected for some j satisfying is at most
On the other hand, the total number of pairs is Thus if we choose C to be large enough, we can find at least pairs (for instance) which are not j connected for any The lines that connect these pairs either pass through fewer than 2C points, or pass through more than n/C points. If the latter case holds for even one of these pairs, then we have the first conclusion of Beck's theorem. Thus we may assume that all of the pairs are connected by lines which pass through fewer than 2C points. But each such line can connect at most pairs of points. Thus there must be at least lines connecting at least two points, and the claim follows by taking .