Twierdzenie De Bruijna – Erdősa ( geometria incydentów )

Ten artykuł dotyczy liczby linii określonych przez skończony zbiór punktów. Kolorowanie grafów nieskończonych można znaleźć w twierdzeniu De Bruijna – Erdősa (teoria grafów) .

W geometrii padania twierdzenie De Bruijna – Erdősa , pierwotnie opublikowane przez Nicolaasa Goverta de Bruijna i Paula Erdősa ( 1948 ), określa dolną granicę liczby linii określonych przez n punktów na płaszczyźnie rzutowej . Przez dualność jest to również ograniczenie liczby punktów przecięcia określonych przez konfigurację linii.

Chociaż dowód podany przez De Bruijna i Erdősa jest kombinatoryczny , De Bruijn i Erdős zauważyli w swoim artykule, że analogiczny ( euklidesowy ) wynik jest konsekwencją twierdzenia Sylwestra-Gallai poprzez indukcję liczby punktów.

Stwierdzenie twierdzenia

Prawie ołówek w siedmiu punktach

Niech P będzie konfiguracją n punktów na płaszczyźnie rzutowej, a nie wszystkich na prostej. Niech t będzie liczbą linii określoną przez P . Następnie,

• t ≥ n , i
• jeśli t = n , dowolne dwie proste mają dokładnie jeden punkt wspólny z P. W tym przypadku P jest albo płaszczyzną rzutową, albo P jest bliską ołówkiem , co oznacza, że ​​dokładnie n - 1 punktów jest współliniowych .

Dowód euklidesowy

Twierdzenie jest oczywiście prawdziwe dla trzech niewspółliniowych punktów. Postępujemy przez indukcję .

Załóżmy, że n > 3 i twierdzenie jest prawdziwe dla n - 1. Niech P będzie zbiorem n punktów, które nie są współliniowe. Twierdzenie Sylwestra -Gallaja stwierdza, że ​​istnieje prosta zawierająca dokładnie dwa punkty P . Takie dwie linie punktowe nazywane są liniami zwykłymi . Niech a i b będą dwoma punktami P na zwykłej prostej.

Jeśli usunięcie punktu a tworzy zbiór punktów współliniowych, to P generuje prawie ołówek złożony z n linii ( n - 1 zwykłych linii przechodzących przez a plus jedna linia zawierająca pozostałe n - 1 punktów).

W przeciwnym razie usunięcie a daje zbiór P' n - 1 punktów, z których nie wszystkie są współliniowe. Zgodnie z hipotezą indukcyjną P' wyznacza co najmniej n − 1 linii. Zwykła linia wyznaczona przez aib nie jest wśród nich, więc P wyznacza co najmniej n linii.

Dowód JH Conwaya

John Horton Conway ma czysto kombinatoryczny dowód, który w konsekwencji odnosi się również do punktów i prostych na liczbach zespolonych , kwaternionach i oktonionach .

Źródła

• De Bruijn, NG ; Erdős, P. (1948), „O problemie kombinatorowym [ sic ]” (PDF) , Indagationes Mathematicae , 10 : 421–423 .
•   Batten, Lynn Margaret (1997), „2.2 Twierdzenie De Bruijna – Erdősa”, Combinatorics of Finite Geometries (wyd. 2), Cambridge University Press, s. 25–27, ISBN 0-521-59014-0