✨Định lý Helly

Định lý Helly cho hình học phẳng: nếu trong một gia đình các tập hợp lồi, giao của mọi bộ ba tập đều khác rỗng, thì giao của tất cả các tập hợp đó là khác rỗng Định lý Helly là một kết quả cơ bản trong hình học rời rạc về giao của các tập hợp lồi. Nó được phát hiện bởi Eduard Helly năm 1913, nhưng chỉ được xuất bản năm 1923, khi các chứng minh khác của và đã được đăng. Định lý Helly đưa ra khái niệm gia đình Helly.

Phát biểu

Giả sử :$X\_1,X\_2,\backslash dots,X$n là các tập hợp lồi trong $\backslash mathbb\{R\}^d$, trong đó $n\; >\; d$. Nếu giao của mọi bộ $d+1$ tập là khác rỗng, thì giao của tất cả các tập hợp đó là khác rỗng, nghĩa là :$\backslash bigcap${j=1}^n X_j\ne\varnothing.

Để áp dụng cho một số vô hạn các tập hợp cần có thêm tính chất compact: Nếu $\{X\_\backslash alpha\}$ là các tập hợp lồi compact trong $R^d$ và giao của mọi bộ không quá $d+1$ tập là khác rỗng thì giao của tất cả các tập hợp đó là khác rỗng.

Chứng minh

Ta chứng minh phiên bản hữu hạn của định lý thông qua định lý Radon như trong chứng minh của . Từ đó ta có phiên bản vô hạn thông qua tính chất giao hữu hạn của không gian compact: giao của một gia đình các tập hợp là khác rỗng khi và chỉ khi mọi bộ hữu hạn các tập trong gia đình đó có giao khác rỗng.

Trước hết giả sử $n=d+2$. Theo giả thuyết của định lý, tồn tại điểm

:$j=2,3,\backslash dots,n$

tồn tại điểm $x\_j$ nằm trong giao của mọi $X\_i$ ngoại trừ $X\_j$. Ta áp dụng định lý Radon cho tập

:$A=\{x\_1,x\_2,\backslash dots,x\_n\}.$

Theo định lý Radon, tồn tại hai tập hợp không giao nhau $A\_1,A\_2\backslash subset\; A$ sao cho bao lồi của $A\_1$ giao với bao lồi của $A\_2$. Giả sử $p$ là điểm nằm trong phần giao của hai bao lồi. Ta sẽ chứng minh

:$p\backslash in\backslash bigcap\_\{j=1\}^n\; X\_j.$

Thật vậy, xét $j\backslash in\{1,2,...,n\}$ bất kì. Phần tử duy nhất trong $A$ có thể không nằm trong $X\_j$ là $x\_j$. Nếu $x\_j\backslash in\; A\_1$, thì $x\_j\backslash notin\; A\_2$, và do đó $X\_j\backslash supset\; A\_2$. Do $X\_j$ lồi, nó cũng chứa bao lồi của $A\_2$ và do đó $p\backslash in\; X\_j$. Tương tự như vậy, nếu $x\_j\backslash notin\; A\_1$, thì $X\_j\backslash supset\; A\_1$, và lập luận tương tự như trên, ta có $p\backslash in\; X\_j$. Do $p$ nằm trong mọi $X\_j$, nó nằm trong giao của chúng.

Ở trên ta giả sử $x\_1,x\_2,\backslash dots,x\_n$ là các điểm khác nhau. Nếu điều này không đúng, chẳng hạn $x\_i=x\_k$ cho hai số $i\backslash ne\; k$ nào đó, thì $x\_i$ nằm trong mọi tập $X\_j$, và ta cũng kết luận giao của tất cả các tập hợp là khác rỗng. Như vậy ta đã chứng minh được định lý cho trường hợp $n=d+2$.

Giả sử $n>d+2$ và ta có giả thiết quy nạp là định lý đúng cho $n-1$. Chứng minh trên cho thấy mọi bộ $d+2$ tập có giao khác rỗng. Ta xét một gia đình các tập hợp mới trong đó $X\_\{n-1\}$ và $X\_n$ được thay bằng

:$X\_\{n-1\}\backslash cap\; X\_n.$

Trong gia đình mới này, giao của mọi bộ $d+1$ tập là khác rỗng. Theo giả thiết quy nạp, giao của tất cả các tập hợp mới là khác rỗng. Do đó, giao của tất cả các tập hợp ban đầu cũng khác rỗng.