De Bruijn-Erdős sætning

De Bruijn-Erdős sætning , et af de vigtige resultater inden for incidensgeometri , etablerer en skarp nedre grænse for antallet af linjer defineret af punkter på det projektive plan . Ved dualitet indebærer dette teorem en begrænsning på antallet af skæringspunkter mellem en konfiguration af linjer. $n$

Historie

Installeret af Nicholas de Bruijn og Pal Erdős i 1948 .

Ordlyd

Lad et sæt punkter på det projektive plan gives, som ikke alle ligger på den samme rette linje. Lad dette være antallet af alle linjer, der går gennem par af punkter fra : Så . Desuden, hvis , Så enhver to linjer skærer i et punkt fra . $P$ $n$ $t$ $P$ $t\geqslant n$ $t=n$ $P$

Bevis

Standardbeviset er ved induktion . Sætningen er bestemt sand for tre punkter, der ikke ligger på samme linje. Lad , udsagnet er sandt for og være et sæt punkter, som ikke alle ligger på den samme rette linje. Ved Sylvesters sætning går en af disse linjer gennem præcis to punkter fra . Lad os betegne disse to punkter og . $n>3$ $n-1$ $P$ $n$ $P$ $-en$ $b$

Hvis, når et punkt fjernes , er alle de resterende punkter på samme linje, så danner det et bundt af linjer ( enkle linjer passerer igennem , plus en linje, der går gennem de resterende punkter). Ellers danner fjernelsen et sæt fra et ikke-kollineært punkt. Ved induktionshypotesen går linjer igennem , hvilket er mindst én mindre end antallet af linjer, der går gennem sættets punkter . $-en$ $P$ $P$ $n-1$ $P$ $-en$ $P$ $n-1$ $P$ $n-1$ $P$

Litteratur

NG de Bruijn, P. Erdős. Et kombinatorisk [sic] problem // Indagationes Mathematicae. - 1948. - T. 10 . - S. 421-423 .
Lynn Margaret Batten. Kombinatorik af endelige geometrier . - Cambridge University Press, 1997. - S. 25-27 . - ISBN 0-521-59014-0 .