De Bruijn-Erdős tétel

A de Bruijn-Erdős tétel , a beesési geometria egyik fontos eredménye, éles alsó korlátot állapít meg a projektív sík pontjai által meghatározott egyenesek számára . A kettősség szerint ez a tétel korlátozza a vonalak metszéspontjainak számát. $n$

Történelem

Nicholas de Bruijn és Erdős Pal telepítette 1948 - ban .

Megfogalmazás

Legyen adott a projektív síkon olyan pontok halmaza, amelyek nem mindegyike esik ugyanazon az egyenesen. Legyen ez a pontpárokon átmenő összes egyenes száma a következőtől : Akkor . Sőt, ha , akkor tetszőleges két egyenes metszi egymást a -tól induló pontban . $P$ $n$ $t$ $P$ $t\geqslant n$ $t=n$ $P$

Bizonyítás

A standard bizonyítás indukciós . A tétel határozottan igaz három olyan pontra, amelyek nem esnek ugyanazon az egyenesen. Legyen az állítás igaz és olyan pontok halmaza , amelyek nem mindegyike esik ugyanazon az egyenesen. Sylvester tétele szerint ezen egyenesek egyike pontosan két ponton halad át -ból . Jelöljük ezt a két pontot és . $n>3$ $n-1$ $P$ $n$ $P$ $a$ $b$

Ha egy pont eltávolításakor az összes többi pont ugyanazon a vonalon van, akkor az egy vonalköteget alkot ( egyszerű vonalak haladnak át -on , plusz egy vonal a fennmaradó pontokon). Ellenkező esetben az eltávolítás egy halmazt alkot egy nem kollineáris pontból. Az indukciós hipotézis szerint az egyenesek átmennek , ami legalább eggyel kevesebb, mint a halmaz pontjain áthaladó egyenesek száma . $a$ $P$ $P$ $n-1$ $P$ $a$ $P$ $n-1$ $P$ $n-1$ $P$

Irodalom

NG de Bruijn, P. Erdős. Kombinációs [sic] probléma // Indagationes Mathematicae. - 1948. - T. 10 . - S. 421-423 .
Lynn Margaret Batten. Véges geometriák kombinatorikája . - Cambridge University Press, 1997. - S. 25-27 . - ISBN 0-521-59014-0 .