De Bruijn-Erdősova věta

De Bruijn-Erdős teorém , jeden z důležitých výsledků v geometrii dopadu , založí ostrou dolní hranici na množství linek definovaných body na projective letadle . Dualitou tento teorém implikuje omezení počtu průsečíků konfigurace čar. $n$

Historie

Instalovali Nicholas de Bruijn a Pal Erdős v roce 1948 .

Formulace

Nechť je dána množina bodů na projektivní rovině, z nichž ne všechny leží na stejné přímce. Nechť toto je počet všech čar procházejících dvojicemi bodů z : Potom . Navíc, jestliže , pak se jakékoli dvě čáry protínají v bodě od . $P$ $n$ $t$ $P$ $t\geqslant n$ $t=n$ $P$

Důkaz

Standardní důkaz je indukcí . Věta rozhodně platí pro tři body, které neleží na stejné přímce. Nechť , tvrzení je pravdivé pro a je množina bodů, z nichž ne všechny leží na stejné přímce. Podle Sylvesterovy věty jedna z těchto přímek prochází právě dvěma body z . Označme tyto dva body a . $n>3$ $n-1$ $P$ $n$ $P$ $A$ $b$

Pokud jsou po odstranění bodu všechny zbývající body na stejné čáře, pak tvoří svazek čar ( jednoduché čáry procházejí , plus jedna čára procházející zbývajícími body). Jinak odstranění vytvoří množinu z nekolineárního bodu. Podle indukční hypotézy procházejí přímky , což je alespoň o jednu méně než počet přímek procházejících body množiny . $A$ $P$ $P$ $n-1$ $P$ $A$ $P$ $n-1$ $P$ $n-1$ $P$

Literatura

NG de Bruijn, P. Erdős. Kombinační [sic] problém // Indagationes Mathematicae. - 1948. - T. 10 . - S. 421-423 .
Lynn Margaret Batten. Kombinatorika konečných geometrií . - Cambridge University Press, 1997. - S. 25-27 . - ISBN 0-521-59014-0 .