Định lý Sylvester–Gallai
Định lý Sylvester–Gallai khẳng định rằng với mọi tập hợp hữu hạn điểm trên mặt phẳng, hoặc
 mọi điểm đều thẳng hàng; hoặc
 tồn tại một đường thẳng chứa đúng hai điểm.

Giả thuyết này được đặt ra bởi .  cho rằng Sylvester đặt câu hỏi này do một hiện tượng trong hình học đại số, trong đó các điểm uốn của một cung bậc ba trong mặt phẳng xạ ảnh phức tạo nên một cấu hình gồm chín điểm và mười hai đường thẳng trong đó mỗi đường thẳng đi qua hai điểm đều chứa một điểm thứ ba. Định lý Sylvester–Gallai khẳng định rằng không thể tất cả chín điểm đều có tọa độ thực.  chứng minh phiên bản đối ngẫu xạ ảnh của định lý này, (thực ra của một mệnh đề mạnh hơn một chút). Do không biết đến chứng minh của Melchior,  lại đưa ra giả thuyết này và Tibor Gallai, và sau đó nhiều tác giả khác, đã chứng minh được nó.

Một đường thẳng chứa đúng hai điểm được gọi là một đường thẳng tầm thường. Có thuật toán tìm mọi đường thẳng tầm thường của một tập n điểm trong thời gian O(n log n) trong trường hợp xấu nhất.

Định lý Sylvester–Gallai không đúng cho tập hợp vô hạn điểm: tập hợp tất cả các điểm trên mặt phẳng hoặc tập hợp tất cả các điểm trong một hình tròn đơn vị là các phản ví dụ hiển nhiên. Cũng có thể xây dựng các phản ví dụ đếm được, chẳng hạn như tập hợp tất cả các điểm có tọa độ nguyên hoặc tập hợp tất cả các điểm có tọa độ hữu tỉ trong hình tròn đơn vị. Như ví dụ ở trên về điểm uốn của cung bậc ba, định lý Sylvester–Gallai không đúng cho mặt phẳng xạ ảnh phức.

Phiên bản xạ ảnh và đối ngẫu 
Cũng có thể xem xét sự tồn tại của đường thẳng tầm thường cho các điểm trên mặt phẳng xạ ảnh thực RP2 thay vì mặt phẳng Euclid. Phiên bản này không phải là tổng quát hơn do mọi tập hữu hạn điểm xạ ảnh đều có thể được biến đổi thành một tập hợp điểm Euclid sao cho các đường thẳng tầm thường được giữ nguyên, tuy nhiên cách nhìn xạ ảnh giúp cho việc mô tả một số cấu hình dễ dàng hơn.

Theo đối ngẫu xạ ảnh, việc tồn tại đường thẳng tầm thường cho một tập n điểm không thẳng hàng trong RP2 là tương đương với việc tồn tại một điểm tầm thường trong một tập hợp hữu hạn các đường thẳng không đồng quy. Một điểm là tầm thường nếu nó là giao của đúng hai đường thẳng.

Chứng minh

Chứng minh của Kelly

Xem chứng minh của Gallai chẳng hạn ở . Sau đây là chứng minh của Kelly.

Giả sử phản chứng là tồn tại một tập hợp S gồm hữu hạn điểm không thẳng hàng nhưng mọi đường thẳng qua hai điểm trong S đều chứa ít nhất ba điểm. Một đường thẳng gọi là đường nối nếu nó đi qua ít nhất hai điểm trong S. Giả sử (P,l) là cặp điểm và đường nối có khoảng cách dương nhỏ nhất trong mọi cặp điểm-đường nối.

Theo giả thiết, l đi qua ít nhất ba điểm trong S, nên nếu hạ đường cao từ P xuống l thì tồn tại ít nhất hai điểm nằm cùng một phía của đường cao (một điểm có thể nằm ở ngay chân đường cao). Trong hai điểm này, gọi điểm ở gần chân đường cao hơn là B, và điểm kia là C. Xét đường thẳng m nối P và C. Khoảng cách từ B tới m nhỏ hơn khoảng cách từ P tới l, mâu thuẫn với giả thiết về P và l. Một cách để thấy điều này là tam giác vuông với cạnh huyền BC đồng dạng và nằm bên trong tam giác vuông với cạnh huyền PC.

Do đó, không thể tồn tại khoảng cách dương nhỏ nhất giữa các cặp điểm-đường nối. Nói cách khác, mọi điểm đều nằm trên đúng một đường thẳng nếu mọi đường nối đều chứa ít nhất ba điểm.

Chứng minh Melchior
Năm 1940, trước chứng minh của Gallai, Melchior đã chứng minh mọi tập hợp hữu hạn các đường thẳng không đồng quy trong mặt phẳng xạ ảnh đều có ít nhất ba điểm tầm thường. Theo tính chất đối ngẫu, mọi tập hợp hữu hạn điểm không thẳng hàng đều có ít nhất ba đường thẳng tầm thường.

Melchior nhận xét thấy với mọi đồ thị trong RP2, biểu thức V − E + F phải bằng 1 (đặc trưng Euler của RP2) trong đó V, E, và F, là số đỉnh, cạnh, và mặt của đồ thị. Mọi tập hợp đường thẳng không đồng quy trên RP2 đều tạo ra một đồ thị trong đó mỗi mặt có ít nhất ba cạnh, và mỗi cạnh nằm trên hai mặt. Do đó ta có bất đẳng thức F ≤ 2E/3. Sử dụng bất đẳng thức này để khử F khỏi đặc trưng Euler, ta có bất đẳng thức E ≤ 3V − 3. Tuy nhiên nếu mọi đỉnh đồ thị đều là giao điểm của ít nhất ba đường thẳng thì số cạnh là ít nhất 3V, mâu thuẫn với bất đẳng thức trên. Do đó tồn tại ít nhất một điểm là giao của đúng hai đường thẳng, và nếu phân tích kĩ hơn như Melchior đã làm, thì có thể thấy cần ít nhất ba điểm tầm thường để thỏa mãn bất đẳng thức E ≤ 3V − 3.

Bất đẳng thức Melchior
Bằng một phương pháp tương tự, Melchior chứng minh kết quả tổng quát hơn như sau. Với mọi k ≥ 2, giả sử tk là số điểm nằm trên k đường thẳng. Khi đó

Một cách tương đương,

Đây thường được gọi là bất đẳng thức Melchior.

Chứng minh của Coxeter
 đưa ra một chứng minh khác của định lý Sylvester–Gallai trong hình học thứ tự, một cách tiên đề hóa hình học, bao hàm cả hình học Euclid và nhiều hình học khác.  liệt kê danh sách nhỏ nhất các tiên đề cần dùng để chứng minh định lý Sylvester–Gallai.

Xem thêm
Định lý Sylvester
Định lý De Bruijn–Erdős, một hệ quả của định lý Sylvester–Gallai, khẳng định rằng n điểm không thẳng hàng xác định ít nhất n đường thẳng.
Bài toán trồng cây

Ghi chú

Tham khảo

 

.

Liên kết ngoài 

Hình học rời rạc
Hình học phẳng Euclid
S
Định lý Sylvester–Gallai khẳng định rằng với mọi tập hợp hữu hạn điểm trên mặt phẳng , hoặc mọi điểm đều thẳng hàng ; hoặc tồn tại một đường thẳng chứa đúng hai điểm . Giả thuyết này được đặt ra bởi \. cho rằng Sylvester đặt câu hỏi này do một hiện tượng trong hình học đại số , trong đó các điểm uốn của một cung bậc ba trong mặt phẳng xạ ảnh phức tạo nên một cấu hình gồm chín điểm và mười hai đường thẳng trong đó mỗi đường thẳng đi qua hai điểm đều chứa một điểm thứ ba . Định lý Sylvester–Gallai khẳng định rằng không thể tất cả chín điểm đều có tọa độ thực . chứng minh phiên bản đối ngẫu xạ ảnh của định lý này , (thực ra của một mệnh đề mạnh hơn một chút) . Do không biết đến chứng minh của Melchior , lại đưa ra giả thuyết này và Tibor Gallai , và sau đó nhiều tác giả khác , đã chứng minh được nó . Một đường thẳng chứa đúng hai điểm được gọi là một đường thẳng tầm thường . Có thuật toán tìm mọi đường thẳng tầm thường của một tập n điểm trong thời gian O(n log n) trong trường hợp xấu nhất . Định lý Sylvester–Gallai không đúng cho tập hợp vô hạn điểm : tập hợp tất cả các điểm trên mặt phẳng hoặc tập hợp tất cả các điểm trong một hình tròn đơn vị là các phản ví dụ hiển nhiên . Cũng có thể xây dựng các phản ví dụ đếm được , chẳng hạn như tập hợp tất cả các điểm có tọa độ nguyên hoặc tập hợp tất cả các điểm có tọa độ hữu tỉ trong hình tròn đơn vị . Như ví dụ ở trên về điểm uốn của cung bậc ba , định lý Sylvester–Gallai không đúng cho mặt phẳng xạ ảnh phức . Phiên bản xạ ảnh và đối ngẫu Cũng có thể xem xét sự tồn tại của đường thẳng tầm thường cho các điểm trên mặt phẳng xạ ảnh thực RP2 thay vì mặt phẳng E uclid . Phiên bản này không phải là tổng quát hơn do mọi tập hữu hạn điểm xạ ảnh đều có thể được biến đổi thành một tập hợp điểm Euclid sao cho các đường thẳng tầm thường được giữ nguyên , tuy nhiên cách nhìn xạ ảnh giúp cho việc mô tả một số cấu hình dễ dàng hơn . Theo đối ngẫu xạ ảnh , việc tồn tại đường thẳng tầm thường cho một tập n điểm không thẳng hàng trong RP2 là tương đương với việc tồn tại một điểm tầm thường trong một tập hợp hữu hạn các đường thẳng không đồng quy . Một điểm là tầm thường nếu nó là giao của đúng hai đường thẳng . Chứng minh Chứng minh của Kelly Xem chứng minh của Gallai chẳng hạn ở \. Sau đây là chứng minh của Kelly . Giả sử phản chứng là tồn tại một tập hợp S gồm hữu hạn điểm không thẳng hàng nhưng mọi đường thẳng qua hai điểm trong S đều chứa ít nhất ba điểm . Một đường thẳng gọi là đường nối nếu nó đi qua ít nhất hai điểm trong S . Giả sử (P, l) là cặp điểm và đường nối có khoảng cách dương nhỏ nhất trong mọi cặp điểm - đường nối . Theo giả thiết , l đi qua ít nhất ba điểm trong S , nên nếu hạ đường cao từ P xuống l thì tồn tại ít nhất hai điểm nằm cùng một phía của đường cao (một điểm có thể nằm ở ngay chân đường cao) . Trong hai điểm này , gọi điểm ở gần chân đường cao hơn là B , và điểm kia là C . Xét đường thẳng m nối P và C . Khoảng cách từ B tới m nhỏ hơn khoảng cách từ P tới l , mâu thuẫn với giả thiết về P và l . Một cách để thấy điều này là tam giác vuông với cạnh huyền BC đồng dạng và nằm bên trong tam giác vuông với cạnh huyền PC . Do đó , không thể tồn tại khoảng cách dương nhỏ nhất giữa các cặp điểm-đường nối . Nói cách khác , mọi điểm đều nằm trên đúng một đường thẳng nếu mọi đường nối đều chứa ít nhất ba điểm . Chứng minh Melchior Năm trước chứng minh của Gallai , Melchior đã chứng minh mọi tập hợp hữu hạn các đường thẳng không đồng quy trong mặt phẳng xạ ảnh đều có ít nhất ba điểm tầm thường . Theo tính chất đối ngẫu , mọi tập hợp hữu hạn điểm không thẳng hàng đều có ít nhất ba đường thẳng tầm thường . Melchior nhận xét thấy với mọi đồ thị trong RP2 , biểu thức V − E + F phải bằng(đặc trưng Euler của RP2) trong đó V , E , và F , là số đỉnh , cạnh , và mặt của đồ thị . Mọi tập hợp đường thẳng không đồng quy trên RP2 đều tạo ra một đồ thị trong đó mỗi mặt có ít nhất ba cạnh , và mỗi cạnh nằm trên hai mặt . Do đó ta có bất đẳng thức F ≤ 2E/3 . Sử dụng bất đẳng thức này để khử F khỏi đặc trưng Euler , ta có bất đẳng thức E ≤ 3V − 3 . Tuy nhiên nếu mọi đỉnh đồ thị đều là giao điểm của ít nhất ba đường thẳng thì số cạnh là ít nhất , mâu thuẫn với bất đẳng thức trên . Do đó tồn tại ít nhất một điểm là giao của đúng hai đường thẳng , và nếu phân tích kĩ hơn như Melchior đã làm , thì có thể thấy cần ít nhất ba điểm tầm thường để thỏa mãn bất đẳng thức E ≤ 3V − 3 . Bất đẳng thức Melchior Bằng một phương pháp tương tự , Melchior chứng minh kết quả tổng quát hơn như sau . Với mọi k ≥ 2 , giả sử tk là số điểm nằm trên k đường thẳng . Khi đó Một cách tương đương , Đây thường được gọi là bất đẳng thức Melchior . Chứng minh của Coxeter đưa ra một chứng minh khác của định lý Sylvester–Gallai trong hình học thứ tự , một cách tiên đề hóa hình học , bao hàm cả hình học Euclid và nhiều hình học khác . liệt kê danh sách nhỏ nhất các tiên đề cần dùng để chứng minh định lý Sylvester–Gallai . Xem thêm Định lý Sylvester Định lý De Bruijn–Erdős , một hệ quả của định lý Sylvester–Gallai , khẳng định rằng n điểm không thẳng hàng xác định ít nhất n đường thẳng . Bài toán trồng cây Ghi chú Tham khảo . Liên kết ngoài Hình học rời rạc Hình học phẳng Euclid S