Đị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

1. mọi điểm đều thẳng hàng; hoặc
2. 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 Sylvester (1893). Kelly (1986) 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. Melchior (1940) 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, Erdős (1943) 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 RP² 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 RP² 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 ở Borwein & Moser (1990). 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 RP², biểu thức V − E + F phải bằng 1 (đặc trưng Euler của RP²) 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 RP² đề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ử t_k là số điểm nằm trên k đường thẳng. Khi đó

$\displaystyle \sum _{k\geq 2}(k-3)t_{k}\leq -3.\,\!$

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

$\displaystyle t_{2}\geqslant 3+\sum _{k\geq 4}(k-3)t_{k}.\,\!$

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

Chứng minh của Coxeter

Coxeter (1969) đư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. Pambuccian (2009) 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

Tham khảo

• Borwein, P.; Moser, W. O. J. (1990), “A survey of Sylvester's problem and its generalizations”, Aequationes Mathematicae, 40 (1): 111–135, doi:10.1007/BF02112289
• Brass, Peter; Moser, William; Pach, János (2005), Research problems in discrete geometry, Berlin: Springer, ISBN 0-387-23815-8
• de Bruijn, N. G.; Erdős, P. (1948), “A combinatioral [sic] problem” (PDF), Indagationes Mathematicae, 10: 421–423
• Coxeter, H. S. M. (1969), Introduction to Geometry, New York: John Wiley & Sons, tr. 181–182, ISBN 0471504580
• Crowe, D. W.; McKee, T. A. (1968), “Sylvester's problem on collinear points”, Mathematics Magazine, 41 (1): 30–34, doi:10.2307/2687957, JSTOR 2687957.
• Csima, J.; Sawyer, E. (1993), “There exist 6n/13 ordinary points”, Discrete & Computational Geometry, 9: 187–202, doi:10.1007/BF02189318
• Dirac, G. (1951), “Collinearity properties of sets of points”, Quart. J. Math., 2: 221–227, doi:10.1093/qmath/2.1.221
• Erdős, P.; Bellman, Richard; Wall, H. S; Singer, James; Thébault, V (1943), “Problems for solution: 4065–4069”, American Mathematical Monthly, 50 (1): 65–66, doi:10.2307/2304011, JSTOR 2304011
• Erdős, P. (1982), “Personal reminiscences and remarks on the mathematical work of Tibor Gallai” (PDF), Combinatorica, 2 (3): 207–212, doi:10.1007/BF02579228
• Kelly, L. M. (1986), “A resolution of the Sylvester–Gallai problem of J. P. Serre”, Discrete and Computational Geometry, 1 (1): 101–104, doi:10.1007/BF02187687
• Kelly, L. M.; Moser, W. O. J. (1958), “On the number of ordinary lines determined by n points”, Canad. J. Math., 10: 210–219, doi:10.4153/CJM-1958-024-6, Bản gốc lưu trữ ngày 7 tháng 8 năm 2011, truy cập ngày 15 tháng 10 năm 2011
• Melchior, E. (1940), “Über Vielseite der Projektive Ebene”, Deutsche Math., 5: 461–475
• Motzkin, Th. (1951), “The lines and planes connecting the points of a finite set”, Transactions of the American Mathematical Society., 70 (3): 451–464, doi:10.2307/1990609, JSTOR 1990609
• Mukhopadhyay, A.; Agrawal, A.; Hosabettu, R. M. (1997), “On the ordinary line problem in computational geometry”, Nordic Journal of Computing, 4 (4): 330–341
• Mukhopadhyay, A.; Greene, E. (2007), “The ordinary line problem revisited”, Proc. 19th Canadian Conference on Computational Geometry (PDF), tr. 61–64
• Pambuccian, V. (2009), “A reverse analysis of the Sylvester-Gallai theorem”, Notre Dame Journal of Formal Logic., 50 (3): 245–260, doi:10.1215/00294527-2009-010
• Steinberg, R.; Buck, R. C.; Grünwald, T.; Steenrod, N. E. (1944), “Three point collinearity (solution to problem 4065)”, American Mathematical Monthly, 51 (3): 169–171, doi:10.2307/2303021, JSTOR 2303021
• Sylvester, J. J. (1893), “Mathematical question 11851”, Educational Times, 59: 98

Liên kết ngoài

• Malkevitch, Joseph (2003). “A discrete geometrical gem”. Bản gốc lưu trữ ngày 10 tháng 10 năm 2006. Truy cập ngày 15 tháng 10 năm 2011.
• Weisstein, Eric W., "Ordinary Line", MathWorld.