De Bruijn – Erdősova věta (geometrie dopadu) - De Bruijn–Erdős theorem (incidence geometry)

v geometrie dopadu, De Bruijn – Erdősova věta, původně publikoval Nicolaas Govert de Bruijn a Paul Erdős  (1948 ), uvádí a dolní mez na počtu řádků určených n body v a projektivní rovina. Podle dualita, toto je také vázáno na počet průsečíků určený konfigurací čar.

Ačkoli důkaz, který předložili De Bruijn a Erdős, je kombinační, De Bruijn a Erdős ve svém příspěvku uvedli, že analogický (Euklidovský ) výsledek je důsledkem Věta Sylvester – Gallai tím, že indukce na počtu bodů.

Výrok věty

Téměř tužka na sedmi bodech

Nechat P být konfigurací n body v projektivní rovině, ne všechny na přímce. Nechat t je počet řádků určenýP. Pak,

• t ≥ n, a
• -li t = n, jakékoli dvě přímky mají přesně jeden bod P společné. V tomto případě, P je buď projektivní rovina nebo P je blízko tužky, což znamená přesně to n - 1 z bodů je kolineární.

Euklidovský důkaz

Věta jasně platí pro tři nekolineární body. Pokračujeme indukce.

Převzít n > 3 a věta platí pro n - 1. Pojďme P být soubor n body ne všechny kolineární Věta Sylvester – Gallai uvádí, že existuje přímka obsahující přesně dva body P. Takovým dvěma bodovým čarám se říká běžné řádky.Nechat A a b být dva body P na obyčejné lince.

Pokud je odstranění bodu A vytvoří sadu kolineárních bodů P generuje téměř tužku n řádky ( n - 1 obyčejný řádek A plus jeden řádek obsahující druhý n - 1 bod).

Jinak by odstranění A vyrábí sadu, P ' , z n - 1 body, které nejsou všechny kolineární. Indukční hypotézou, P ' určuje alespoň n - 1 řádek. Obyčejná čára určená A a b není mezi nimi, takže P určuje alespoň n řádky.

Důkaz J. H. Conwaye

John Horton Conway má čistě kombinatorický důkaz, který následně platí i pro body a čáry nad komplexní čísla, čtveřice a octonions.^[1]

Reference

Zdroje

• de Bruijn, N. G.; Erdős, P. (1948), „Na kombinovaný [sic] problém“ (PDF), Indagationes Mathematicae, 10: 421–423.
• Batten, Lynn Margaret (1997), „2.2 Věta de Bruijn – Erdős“, Kombinatorika konečných geometrií (2. vyd.), Cambridge University Press, s. 25–27, ISBN  0-521-59014-0