Đị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. 32: 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., 7, American Mathematical Society, tr. 101–179.
• Eckhoff, J. (1993), “Helly, Radon, and Carathéodory type theorems”, Handbook of Convex Geometry, 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ữ 2004-08-07 tại Wayback Machine thông qua bao lồi (tại PlanetMath)