Định lý Radon

Trong hình học, định lý Radon về các tập hợp lồi, đặt tên theo Johann Radon, khẳng định rằng mọi tập hợp gồm d + 2 điểm trong R^d đều có thể chia thành hai tập hợp con không giao nhau có bao lồi giao nhau. Mỗi điểm nằm trong phần giao của hai bao lồi được gọi là một điểm Radon của tập hợp ban đầu.

Ví dụ, trong trường hợp d = 2, mọi tập hợp gồm 4 điểm trên mặt phẳng đều có thể được phân chia theo một trong hai cách sau:

• một tập chứa 3 điểm và một tập chứa đúng 1 điểm, bao lồi (hình tam giác) của tập thứ nhất chứa điểm trong tập còn lại
• hai cặp điểm sao cho các đoạn thẳng nối mỗi cặp cắt nhau.

Chứng minh và cách xây dựng

Hai ví dụ của tập hợp chứa 4 điểm trên mặt phẳng (các đỉnh của một hình vuông và các đỉnh của một tam giác đều cùng với trọng tâm của tam giác), các hệ số là lời giải cho hệ phương trình tuyến tính của tọa độ các điểm này, và phân chia Radon được xác định bởi dấu của các hệ số: các điểm có hệ số dương tạo thành một tập và các điểm còn lại tạo thành tập thứ hai.

Xét một tập ${\displaystyle \{x_{1},x_{2},\dots ,x_{d+2}\}\subset \mathbf {R} ^{d}}$ bất kì gồm d + 2 điểm trong không gian d chiều. Tồn tại các hệ số a₁, ..., a_d + 2, sao cho không phải tất cả đều bằng 0, và là lời giải cho hệ phương trình tuyến tính sau đây

${\displaystyle \sum _{i=1}^{d+2}a_{i}x_{i}=0,\quad \sum _{i=1}^{d+2}a_{i}=0,}$

do chỉ có d + 2 ẩn số (các hệ số) nhưng chỉ có d + 1 phương trình (một phương trình cho mỗi tọa độ cùng với một phương trình yêu cầu tổng các hệ số bằng 0). Chọn một lời giải bất kì a₁, ..., a_d + 2. Đặt I là tập hợp các điểm có hệ số dương, và J là tập hợp các điểm có hệ số nhỏ hơn hoặc bằng 0. Khi đó I và J tạo thành phân chia cần tìm với bao lồi giao nhau.

Bao lồi của I và J giao nhau do chúng cùng chứa điểm

${\displaystyle p=\sum _{i\in I}{\frac {a_{i}}{A}}x_{i}=\sum _{j\in J}{\frac {-a_{j}}{A}}x_{j},}$

trong đó

${\displaystyle A=\sum _{i\in I}a_{i}=-\sum _{j\in J}a_{j}.}$

Vế trái của công thức cho p được viết dưới dạng tổ hợp lồi của các điểm trong I, và vế phải viết nó dưới dạng tổ hợp lồi của các điểm trong J. Do đó p nằm trong cả hai bao lồi.

Chứng minh này cũng cho một thuật toán tìm điểm Radon trong thời gian đa thức của số chiều, bằng cách sử dụng phép khử Gauss hoặc các thuật toán hiệu quả khác để giải hệ phương trình tuyến tính.^[1]

Định lý Radon tô pô

Một tổng quát hóa của định lý Radon trong tô pô là: nếu ƒ là một hàm liên tục từ một đơn hình (d + 1) chiều đến một không gian d chiều, thì đơn hình có hai mặt không giao nhau nhưng ảnh của chúng theo ƒ lại giao nhau.^[2] Định lý Radon là một trường hợp riêng khi ƒ là biến đổi afin duy nhất ánh xạ các đỉnh của đơn hình tới một tập d + 2 điểm cho trước trong không gian d chiều.

Tổng quát hơn, nếu K là một tập hợp lồi compact trong không gian (d + 1) chiều, và ƒ là một hàm liên tục từ K tới không gian d chiều, thì tồn tại một hàm tuyến tính g sao cho tồn tại hai điểm có cùng một ảnh theo ƒ: tại một điểm g đạt giá trị lớn nhất và tại điểm kia g đạt giá trị nhỏ nhất. Trong trường hợp K là đơn hình, hai mặt tạo bởi các điểm cực trị theo g là hai mặt không giao nhau nhưng có ảnh giao nhau. Định lý này khi áp dụng cho hình cầu thay vì đơn hình, cho ta định lý Borsuk–Ulam, rằng tồn tại hai điểm đối nhau trên hình cầu được ƒ ánh xạ tới cùng một điểm.^[2]

Ứng dụng

Định lý Radon có thể dùng để chứng minh định lý Helly về giao của các tập hợp lồi.^[3] Chứng minh này là động lực ban đầu cho Radon tìm ra định lý Radon.

Định lý Radon cũng có thể dùng để tính chiều VC của tập các điểm d chiều đối với các phân chia bằng siêu phẳng. Tồn tại d + 1 điểm (chẳng hạn các đỉnh của một đơn hình đều) sao cho mọi tập con khác rỗng đều có thể được phân chia bởi một siêu phẳng. Tuy nhiên với bất kì một tập hợp d + 2 điểm nào, hai tập hợp trong phân chia Radon không thể được chia đôi bởi siêu phẳng nào. Do đó, chiều VC trong trường hợp này là d + 1.^[4]

Một thuật toán ngẫu nhiên lặp đi lặp lại việc thay d + 2 điểm bằng điểm Radon của chúng có thể dùng để tính xấp xỉ "tâm điểm" của mọi tập điểm, trong thời gian đa thức theo số điểm và số chiều.^[1]

Các khái niệm liên quan

Điểm Radon của ba điểm trong không gian một chiều chính là trung vị. Trung vị hình học của một tập điểm là điểm có tổng khoảng cách nhỏ nhất tới tất cả các điểm trong tập hợp.

Một tổng quát hóa cho việc chia thành r tập hợp được đưa ra bởi Tverberg (1966) và được gọi là định lý Tverberg. Nó khẳng định rằng với mọi tập hợp${\displaystyle (d+1)(r-1)+1\ }$ điểm trong không gian Euclide d chiều, tồn tại một cách phân chia nó thành r tập hợp con sao cho giao của bao lồi của tất cả các tập này là khác rỗng.

Định lý Carathéodory khẳng định rằng mọi điểm nằm trong bao lồi của một tập điểm d chiều cũng nằm trong bao lồi của một tập con gồm d + 1 điểm. Một chứng minh của định lý Carathéodory cũng sử dụng phương pháp xem xét nghiệm của một hệ phương trình tuyến tính, tương tự như trong chứng minh của định lý Radon, để giảm số điểm tạo bao lồi cho tới khi chỉ còn d + 1 điểm.

Ghi chú

1. Clarkson và đồng nghiệp (1996).
2. Bajmóczy & Bárány (1979); Matoušek (2003).
3. Matoušek (2002), tr. 11.
4. Epsilon-nets and VC-dimension Lưu trữ 2011-07-22 tại Wayback Machine, Bài giảng của Marco Pellegrini, 2004.

Tham khảo

• Bajmóczy, E. G.; Bárány, I. (1979), “A common generalization of Borsuk's and Radon's theorem”, Acta Mathematica Hungarica, 34 (3–4): 347–350, doi:10.1007/BF01896131.
• Bandelt, H.-J.; Pesch, E. (1989), “A Radon theorem for Helly graphs”, Archiv der Mathematik, 52 (1): 95–98, doi:10.1007/BF01197978.
• Chepoi, V. D. (1986), “Some properties of the d-convexity in triangulated graphs”, Mat. Issled. (bằng tiếng Nga), 87: 164–177. As cited by Bandelt & Pesch (1989).
• Clarkson, Kenneth L.; Eppstein, David; Miller, Gary L.; Sturtivant, Carl; Teng, Shang-Hua (1996), “Approximating center points with iterated Radon points” (PDF), International Journal of Computational Geometry & Applications, 6 (3): 357–377, doi:10.1142/s021819599600023x, MR 1409651, Bản gốc (PDF) lưu trữ ngày 22 tháng 2 năm 2012, truy cập ngày 11 tháng 10 năm 2011.
• Danzer, L.; Grünbaum, B.; Klee, V. (1963), “Helly's theorem and its relatives”, Convexity, Proc. Symp. Pure Math., 7, American Mathematical Society, tr. 101–179.
• Duchet, Pierre (1987), “Convex sets in graphs. II. Minimal path convexity”, Journal of Combinatorial Theory, Series A, 44 (3): 307–316, doi:10.1016/0095-8956(88)90039-1. As cited by Bandelt & Pesch (1989).
• Eckhoff, J. (1993), “Helly, Radon, and Carathéodory type theorems”, Handbook of Convex Geometry, A, B, Amsterdam: North-Holland, tr. 389–448.
• Kay, David C.; Womble, Eugene W. (1971), “Axiomatic convexity theory and relationships between the Carathéodory, Helly, and Radon numbers”, Pacific Journal of Mathematics, 38 (2): 471–485, doi:10.2140/pjm.1971.38.471, MR 0310766.
• Matoušek, J. (2002), “1.3 Radon's Lemma and Helly's Theorem”, Lectures on Discrete Geometry, Graduate Texts in Mathematics, 212, Springer-Verlag, tr. 9–12, ISBN 978-0-387-95373-1.
• Matoušek, J. (2003), “5.1 Nonembeddability Theorems: An Introduction”, Using the Borsuk–Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry, Springer-Verlag, tr. 88–92.
• Radon, J. (1921), “Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten”, Mathematische Annalen, 83 (1–2): 113–115, doi:10.1007/BF01464231
• Tverberg, H. (1966), “A generalization of Radon's theorem” (PDF), Journal of the London Mathematical Society, 41: 123–128, doi:10.1112/jlms/s1-41.1.123