Định lý Carathéodory (bao lồi)

Xem thêm các định lý Carathéodory khác

Trong hình học lồi, định lý Carathéodory khẳng định nếu điểm x trong R^d nằm trong bao lồi của tập hợp P, thì tồn tại một tập hợp con P′ của P gồm tối đa d+1 điểm sao cho x nằm trong bao lồi của P′. Một cách phát biểu tương đương là x nằm trong một r-đơn hình với các đỉnh thuộc P, trong đó ${\displaystyle r\leq d}$. Kết quả này được đặt tên theo Constantin Carathéodory, người đã chứng minh định lý này năm 1911 cho trường hợp P compact.^[1] Năm 1913, Ernst Steinitz mở rộng định lý Carathéodory cho mọi tập P trong R^d.^[2]

Sau đây là một ví dụ. Ta xét tập hợp P = {(0,0), (0,1), (1,0), (1,1)} trong R². Bao lồi của tập này là một hình vuông. Xét điểm x = (1/4, 1/4) nằm trong bao lồi của P. Ta có thể chọn tập {(0,0),(0,1),(1,0)} = P ′, với bao lồi là một hình tam giác chứa x và do đó định lý là đúng trong trường hợp này do |P′| = 3.

Chứng minh

Giả sử x là một điểm trong bao lồi của P. Khi đó, x là tổ hợp lồi của một tập hợp hữu hạn các điểm trong P:

${\displaystyle \mathbf {x} =\sum _{j=1}^{k}\lambda _{j}\mathbf {x} _{j}}$

trong đó mọi x_j đều thuộc P, λ_j là số dương, và ${\displaystyle \sum _{j=1}^{k}\lambda _{j}=1}$.

Giả sử k > d + 1 (nếu không ta có ngay điều phải chứng minh). Khi đó, các điểm x₂ − x₁,..., x_k − x₁ là phụ thuộc tuyến tính, nên tồn tại μ₂,..., μ_k sao cho không phải tất cả chúng đều bằng 0 và

${\displaystyle \sum _{j=2}^{k}\mu _{j}(\mathbf {x} _{j}-\mathbf {x} _{1})=\mathbf {0} .}$

Nếu định nghĩa μ₁ như sau

${\displaystyle \mu _{1}:=-\sum _{j=2}^{k}\mu _{j}}$

thì

${\displaystyle \sum _{j=1}^{k}\mu _{j}\mathbf {x} _{j}=\mathbf {0} }$

${\displaystyle \sum _{j=1}^{k}\mu _{j}=0}$

và không phải tất cả μ_j đều bằng 0. Do đó tồn tại ít nhất một μ_j>0. Ta có,

${\displaystyle \mathbf {x} =\sum _{j=1}^{k}\lambda _{j}\mathbf {x} _{j}-\alpha \sum _{j=1}^{k}\mu _{j}\mathbf {x} _{j}=\sum _{j=1}^{k}(\lambda _{j}-\alpha \mu _{j})\mathbf {x} _{j}}$

cho mọi số thực α. Vì vậy đẳng thức trên là đúng khi chọn α như sau

${\displaystyle \alpha :=\min _{1\leq j\leq k}\left\{{\tfrac {\lambda _{j}}{\mu _{j}}}:\mu _{j}>0\right\}={\tfrac {\lambda _{i}}{\mu _{i}}}.}$

Ghi chú là α>0, và với mọi j từ 1 tới k,

${\displaystyle \lambda _{j}-\alpha \mu _{j}\geq 0.}$

Ta nhận thấy λ_i − αμ_i = 0 theo cách chọn α. Vì vậy,

${\displaystyle \mathbf {x} =\sum _{j=1}^{k}(\lambda _{j}-\alpha \mu _{j})\mathbf {x} _{j}}$

trong đó mọi ${\displaystyle \lambda _{j}-\alpha \mu _{j}}$ là không âm, tổng của chúng bằng 1, và thêm vào đó, ${\displaystyle \lambda _{i}-\alpha \mu _{i}=0}$. Nói cách khác, x là tổ hợp lồi của k-1 điểm trong P. Có thể lặp lại quá trình trên cho tới khi x là tổ hợp lồi của d + 1 điểm trong P.

Một cách chứng minh khác là sử dụng định lý Helly.

Xem thêm

• Bổ đề Shapley–Folkman
• Định lý Helly
• Định lý Krein–Milman
• Lý thuyết Choquet

Ghi chú

1. Carathéodory, C. (1911). "Über den Variabilitätsbereich der Fourierschen Konstanten von positiven harmonischen Funktionen". Rendiconti del Circolo Matematico di Palermo. Quyển 32. tr. 193–217.
2. Steinitz, Ernst (1913), "Bedingt konvergente Reihen und konvexe Systeme", J. Reine Angew. Math., 143: 128–176, doi:10.1515/crll.1913.143.128

Tham khảo

• Danzer, L.; Grünbaum, B.; Klee, V. (1963), "Helly's theorem and its relatives", Convexity, Proc. Symp. Pure Math., quyển 7, American Mathematical Society, tr. 101–179.
• Eckhoff, J. (1993), "Helly, Radon, and Carathéodory type theorems", Handbook of Convex Geometry, quyển A, B, Amsterdam: North-Holland, tr. 389–448.

Liên kết ngoài

• Một phát biểu ngắn gọn của định lý Lưu trữ ngày 7 tháng 8 năm 2004 tại Wayback Machine thông qua bao lồi (tại PlanetMath)