De Bruijn-Erdős sats

De Bruijn-Erdős teorem , ett av de viktiga resultaten inom infallsgeometri , fastställer en skarp nedre gräns för antalet linjer som definieras av punkter på det projektiva planet . Genom dualitet innebär detta teorem en begränsning av antalet skärningar av en konfiguration av linjer. $n$

Historik

Installerad av Nicholas de Bruijn och Pal Erdős 1948 .

Formulering

Låt en uppsättning punkter på det projektiva planet ges, som inte alla ligger på samma räta linje. Låt detta vara antalet av alla linjer som går genom par av punkter från : Sedan . Dessutom, om , Då alla två linjer skär vid en punkt från . $P$ $n$ $t$ $P$ $t\geqslant n$ $t=n$ $P$

Bevis

Standardbeviset är genom induktion . Teoremet är definitivt sant för tre punkter som inte ligger på samma linje. Låt , påståendet är sant för och vara en uppsättning punkter, som inte alla ligger på samma räta linje. Enligt Sylvesters teorem går en av dessa linjer genom exakt två punkter från . Låt oss beteckna dessa två punkter och . $n>3$ $n-1$ $P$ $n$ $P$ $a$ $b$

Om, när en punkt tas bort , alla återstående punkter är på samma linje, bildar den en bunt av linjer ( enkla linjer passerar genom , plus en linje som går genom de återstående punkterna). Annars bildar borttagningen en uppsättning från en icke-kolinjär punkt. Enligt induktionshypotesen passerar linjer genom , vilket är minst en mindre än antalet linjer som passerar genom uppsättningens punkter . $a$ $P$ $P$ $n-1$ $P$ $a$ $P$ $n-1$ $P$ $n-1$ $P$

Litteratur

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