Định lý De Bruijn–Erdős (hình học)

Trong hình học, định lý De Bruijn–Erdős, chứng minh bởi Nicolaas Govert de Bruijn và Paul Erdős (1948), đưa ra một chặn dưới cho số đường thẳng xác định bởi n điểm trong mặt phẳng xạ ảnh. Theo tính chất đối ngẫu, đây cũng là chặn dưới cho số giao điểm xác định bởi n đường thẳng.

Tuy chứng minh của De Bruijn và Erdős là chứng minh tổ hợp, De Bruijn và Erdős cũng nhận xét trong bài báo của họ là kết quả tương tự trong hình học Euclid là hệ quả của định lý Sylvester–Gallai, bằng quy nạp theo số điểm.

Phát biểu định lý

Giả sử P là một cấu hình gồm n điểm không thẳng hàng trên mặt phẳng xạ ảnh. Đặt t là số đường thẳng xác định bởi P. Khi đó,

t ≥ n,
Nếu t = n, thì hai đường thẳng bất kì giao nhau tại một điểm trong P.

Chứng minh

Ta chứng minh bằng phương pháp quy nạp. Định lý rõ ràng đúng cho ba điểm không thẳng hàng.

Giả sử n > 3 và định lý đúng cho n − 1. Giả sử P là một tập hợp n điểm không thẳng hàng. Theo định lý Sylvester–Gallai, tồn tại một đường thẳng đi qua đúng hai điểm trong P. Đặt a và b là hai điểm trong P nằm trên một đường thẳng như vậy.

Nếu khi xóa a, tất cả các điểm còn lại thẳng hàng thì n − 1 > 2 điểm khác a trong P nằm trên cùng một đường thẳng đi qua b, và không đi qua a. Trong trường hợp đó nếu ta xóa b thì sẽ thu được tập hợp P' gồm n − 1 điểm không thẳng hàng. Theo giả thiết, P' xác định n − 1 đường thẳng, ít hơn số đường thẳng xác định bởi P đúng 1 (do không có đường thẳng nối a và b).

Trong trường hợp còn lại, khi xóa a còn lại tập hợp P' gồm n − 1 điểm không thẳng hàng. Tương tự như trường hợp trên, theo giả thiết quy nạp, P' xác định n − 1 đường thẳng và ít hơn số đường thẳng xác định bởi P ít nhất 1.

Tham khảo

de Bruijn, N. G.; Erdős, P. (1948), "A combinatioral [sic] problem" (PDF), Indagationes Mathematicae, 10: 421–423.
Batten, Lynn Margaret (1997), "2.2 The de Bruijn–Erdős theorem", Combinatorics of finite geometries (ấn bản thứ 2), Cambridge University Press, tr. 25–27, ISBN 0521590140