Becks sats (geometri)

För kategoriteorin som utvecklats av en annan författare, se Becks monadicitetsteorem .

I diskret geometri är Becks teorem något av flera olika resultat , varav två ges nedan. Båda dök upp, tillsammans med flera andra viktiga teorem, i en välkänd artikel av József Beck . De två resultat som beskrivs nedan avser främst nedre gränser för antalet linjer som bestäms av en uppsättning punkter i planet. (Varje linje som helst som innehåller minst två punkter med punktuppsättning sägs vara bestämd av den punktuppsättningen.)

Erdős–Becks sats

Erdős –Beck-satsen är en variant av ett klassiskt resultat av LM Kelly och WOJ Moser som involverar konfigurationer av n punkter varav högst n − k är kolinjära, för ungefär 0 < k < O ( √ n ). De visade att om n är tillräckligt stor, i förhållande till k , så spänner konfigurationen över åtminstone kn − (1/2)(3 k + 2)( k − 1) linjer.

Elekes och Csaba Toth noterade att Erdős-Beck-satsen inte lätt sträcker sig till högre dimensioner. Ta till exempel en uppsättning av 2 n punkter i R ³ som alla ligger på två sneda linjer . Antag att dessa två linjer var och en är infallande till n punkter. En sådan konfiguration av punkter spänner över endast 2 n plan. En trivial förlängning av hypotesen för punktmängder i R ^d är alltså inte tillräcklig för att erhålla det önskade resultatet.

Detta resultat antogs först av Erdős och bevisades av Beck. (Se sats 5,2 tum.)

Påstående

Låt S vara en uppsättning av n punkter i planet. Om inte fler än n − k punkter ligger på någon linje under några 0 ≤ k < n − 2, så finns det Ω( nk ) linjer som bestäms av punkterna för S .

Becks teorem

Becks sats säger att ändliga samlingar av punkter i planet hamnar i en av två ytterligheter; en där en stor del av punkter ligger på en enda linje, och en där ett stort antal linjer behövs för att ansluta alla punkter.

Även om det inte nämns i Becks papper, antyds detta resultat av Erdős-Beck-satsen .

Påstående

Satsen hävdar att det finns positiva konstanter C , K så att givet några n punkter i planet, är minst ett av följande påståenden sant:

1. Det finns en linje som innehåller minst n / C av punkterna.
2. Det finns minst $n^{2}/K$ linjer, som var och en innehåller minst två av punkterna.

I Becks ursprungliga argument är C 100 och K är en ospecificerad konstant; det är inte känt vad de optimala värdena för C och K är.

Bevis

Ett bevis för Becks sats kan ges enligt följande. Betrakta en uppsättning P med n punkter i planet. Låt j vara ett positivt heltal. Låt oss säga att ett par punkter A , B i mängden P är j-anslutna om linjen som förbinder A och B innehåller mellan $2^{j}$ och $2 ^{j+1}-1$ punkter av P (inklusive A och B ).

Från Szemerédi–Trotter-satsen är antalet sådana linjer $O(n^{2}/2^{3j}+n/2^{j })$ , enligt följande: Betrakta mängden P av n punkter och mängden L för alla de linjer som spänns över av par av punkter av P som innehåller minst $2^{j}$ punkter av P . Eftersom inga två punkter kan ligga på två distinkta linjer $|L|\cdot {2^{j} \choose 2}\leq {n \choose 2}$ . Nu genom att använda Szemerédi–Trotter-satsen följer det att antalet incidenser mellan P och L är som mest $O(n^{2}/2^{2j}+n )$ . Alla linjer som förbinder j-anslutna punkter ligger också i L , och var och en bidrar med minst $2^{j}$ incidenser. Därför är det totala antalet sådana linjer $O(n^{2}/2^{3j}+n/2^{j})$ .

Eftersom varje sådan linje förbinder $\Omega (2^{2j})$ punkterpar, ser vi alltså att som mest $O(n^{2}/2^{j}+2^{j}n)$ par av punkter kan vara j -anslutna.

Låt nu C vara en stor konstant. Genom att summera den geometriska serien ser vi att antalet par av punkter som är j -anslutna för vissa j som uppfyller $C\leq 2^{j}\leq n/C$ är som mest $O(n^{2}/C)$ .

Å andra sidan är det totala antalet par ${\frac {n(n-1)}{2}}$ . Om vi ​​alltså väljer att C ska vara tillräckligt stor, kan vi hitta åtminstone $n^{2}/4$ par (till exempel) som inte är j -anslutna för någon $C\leq 2^{j}\leq n/C$ . Linjerna som förbinder dessa par passerar antingen genom färre än 2 C -punkter eller passerar genom mer än n / C -punkter. Om det senare fallet gäller även för ett av dessa par, så har vi den första slutsatsen av Becks sats. Så vi kan anta att alla $n^{2}/4$ -paren är förbundna med linjer som passerar genom färre än 2 C -punkter. Men varje sådan linje kan som mest ansluta $C(2C-1)$ punkterpar. Det måste alltså finnas minst $n^{2}/4C(2C-1)$ linjer som förbinder minst två punkter, och påståendet följer genom att ta $K=4C(2C-1)$ .