9 Radon ve Helly Teoremleri
Bu haftanın iki teoremi de aynı basit gözlemden beslenir: \(\mathbb{R}^n\) uzayında \(n\) taneden fazla vektör lineer bağımsız olamaz. Radon teoremi bunu bir nokta kümesini ikiye ayırmak, Helly teoremi ise konveks kümelerden oluşan bir ailenin ortak noktasının varlığını göstermek için kullanır. Haftanın sonunda konveks kümelerin köşe yapısına bakıyoruz: köşe noktaları, politoplar ve simpleksler.
9.1 Radon Teoremi
Radon teoremi, düzlemde dört noktanın — daha genel olarak \(\mathbb{R}^n\)’de \(n+2\) noktanın — hiçbir zaman “dağınık” duramayacağını söyler: nokta kümesi daima, konveks örtüleri kesişen iki parçaya bölünebilir.
Teorem 9.1 (Radon Teoremi) \(C = \{x_1, x_2, \dots, x_r\}\) kümesi \(\mathbb{R}^n\)’de sonlu noktalı herhangi bir küme olsun. Eğer \(r \ge n + 2\) ise \(C\) kümesi, \(\operatorname{conv}(C_1) \cap \operatorname{conv}(C_2) \ne \varnothing\) sağlanacak biçimde ayrık iki \(C_1\) ve \(C_2\) alt kümesine parçalanabilir.
İspat
\(r \ge n + 2\) olduğundan Teorem 5.3 gereği \(C\) kümesi afin bağımlıdır: \(r - 1 \ge n + 1\) tane fark vektörü \(\mathbb{R}^n\)’de lineer bağımsız olamaz. Bu durumda hepsi birden sıfır olmayan öyle \(\alpha_1, \dots, \alpha_r\) sayıları vardır ki
\[\sum_{i=1}^{r} \alpha_i x_i = 0 \qquad \text{ve} \qquad \sum_{i=1}^{r} \alpha_i = 0\]
eşitlikleri sağlanır. Toplamları sıfır olup hepsi birden sıfır olmadığından, bu \(\alpha_i\) sayılarının en az biri pozitif ve en az biri negatiftir. Dolayısıyla, genelliği bozmaksızın \(1 \le k < r\) sağlayan bir \(k\) için
\[\alpha_1, \dots, \alpha_k \ge 0, \qquad \alpha_{k+1}, \dots, \alpha_r < 0\]
gerçeklendiğini kabul edebiliriz. Öte yandan \(\alpha_i\)’lerin toplamı \(0\) olduğundan
\[\alpha := \alpha_1 + \dots + \alpha_k = -(\alpha_{k+1} + \dots + \alpha_r)\]
şeklinde tanımlanan \(\alpha\) sayısı pozitiftir. Şimdi aşağıdaki biçimde tanımlanmış \(x\) noktasını göz önüne alalım:
\[0 = \sum_{i=1}^{r} \alpha_i x_i = \sum_{i=1}^{k} \alpha_i x_i + \sum_{i=k+1}^{r} \alpha_i x_i \implies x := \sum_{i=1}^{k} \frac{\alpha_i}{\alpha} x_i = \sum_{i=k+1}^{r} \left( -\frac{\alpha_i}{\alpha} \right) x_i.\]
Sol taraftaki katsayılar negatif değildir ve toplamları \(1\)’dir; sağ taraftaki katsayılar da pozitiftir ve toplamları \(1\)’dir. Böylece \(x\) noktası hem \(x_1, \dots, x_k\) noktalarının hem de \(x_{k+1}, \dots, x_r\) noktalarının bir konveks kombinasyonudur; yani
\[x \in \operatorname{conv}\{x_1, \dots, x_k\} \cap \operatorname{conv}\{x_{k+1}, \dots, x_r\}.\]
\(C_1 := \{x_1, \dots, x_k\}\) ve \(C_2 := \{x_{k+1}, \dots, x_r\}\) kümeleri tanımlanırsa \(C_1 \cap C_2 = \varnothing\) ve \(\operatorname{conv}(C_1) \cap \operatorname{conv}(C_2) \ne \varnothing\) gerçeklenir.
\(\blacksquare\)
Örnek 9.1 (Düzlemde Dört Nokta) \(\mathbb{R}^2\) uzayında dört nokta verildiğinde (\(n = 2\), \(r = 4 = n + 2\)) Radon parçalanışının hangi biçimleri alabileceğini inceleyiniz.
Çözüm
İki durum vardır.
Dördü de dışbükey konumdaysa, yani hiçbiri diğer üçünün oluşturduğu üçgenin içinde değilse, noktalar bir dörtgenin köşeleridir. Parçalanış köşegenlere göre yapılır: \(C_1\) bir köşegenin iki ucu, \(C_2\) diğer köşegenin iki ucu alınır. Bu durumda \(\operatorname{conv}(C_1)\) ile \(\operatorname{conv}(C_2)\) kümeleri köşegenlerin kendisidir ve dışbükey bir dörtgenin köşegenleri kesiştiğinden
\[\operatorname{conv}(C_1) \cap \operatorname{conv}(C_2) \ne \varnothing\]
gerçeklenir.
Biri diğer üçünün üçgeninin içindeyse o nokta tek başına \(C_1\), kalan üç nokta \(C_2\) olarak alınır. Bu kez \(\operatorname{conv}(C_1)\) tek noktalı, \(\operatorname{conv}(C_2)\) ise üçgensel bölgedir; nokta üçgenin içinde bulunduğundan kesişim yine boş değildir.
Üç nokta ile aynısını yapmak mümkün değildir: bir üçgenin köşelerini iki gruba ayırdığımızda gruplardan biri tek nokta, diğeri bir kenar olur ve bir köşe karşı kenarın üzerinde bulunmaz. Radon teoremindeki \(r \ge n + 2\) koşulu bu nedenle keskindir.
9.2 Helly Teoremi
Radon teoreminin en ünlü sonucu, konveks kümelerden oluşan bir ailenin ortak noktasının varlığını yalnızca küçük alt ailelere bakarak garanti eden Helly teoremidir.
Teorem 9.2 (Helly Teoremi) \(C_1, \dots, C_r \subset \mathbb{R}^n\), \(r \ge n + 1\) ve her \(i = 1, \dots, r\) için \(C_i\) kümeleri konveks olsun. Eğer bu konveks kümelerden herhangi \(n + 1\) tanesinin kesişimi boş değil ise \(\bigcap_{i=1}^{r} C_i \ne \varnothing\) gerçeklenir.
İspat
İspatı \(r\) üzerinden tümevarım ile yapalım. Eğer \(r = n + 1\) ise kanıtlanacak bir şey yoktur. Şimdi \(r - 1 \ge n + 1\) olmak üzere hipotezin \(r - 1\) tane konveks küme için doğru olduğunu kabul edelim. Bu durumda her \(1 \le i \le r\) için, \(i\). kümeyi dışarıda bırakan \(r - 1\) tanelik aileye tümevarım hipotezi uygulanarak
\[x_i \in C_1 \cap \dots \cap C_{i-1} \cap C_{i+1} \cap \dots \cap C_r\]
gerçekleyen bir \(x_i\) noktası bulunur.
\(r \ge n + 2\) olduğundan \(S := \{x_1, \dots, x_r\}\) kümesine Radon teoremini uygulayarak \(S_1 \cap S_2 = \varnothing\) ve \(\operatorname{conv}(S_1) \cap \operatorname{conv}(S_2) \ne \varnothing\) sağlayan \(S_1\) ve \(S_2\) kümelerini elde edebiliriz. Genelliği kaybetmeksizin \(1 \le k < r\) olmak üzere \(S_1 := \{x_1, \dots, x_k\}\) ve \(S_2 := \{x_{k+1}, \dots, x_r\}\) varsayabiliriz.
\(\operatorname{conv}(S_1) \cap \operatorname{conv}(S_2) \ne \varnothing\) nedeniyle var olan
\[x \in \operatorname{conv}\{x_1, \dots, x_k\} \cap \operatorname{conv}\{x_{k+1}, \dots, x_r\}\]
noktasının her \(i = 1, \dots, r\) için \(x \in C_i\) olduğunu gösterelim. Gerçekten de \(i \le k\) olduğunda \(x_i \in C_{k+1} \cap \dots \cap C_r\) geçerlidir. \(C_i\)’ler konveks olduğundan konveks kombinasyonlar da bu kesişimde kalır:
\[x \in \operatorname{conv}\{x_1, \dots, x_k\} \subset C_{k+1} \cap \dots \cap C_r.\]
Benzer biçimde \(i \ge k + 1\) olduğunda \(x_i \in C_1 \cap \dots \cap C_k\) ve dolayısıyla
\[x \in \operatorname{conv}\{x_{k+1}, \dots, x_r\} \subset C_1 \cap \dots \cap C_k\]
gerçeklenir. Sonuçta \(x \in C_1 \cap \dots \cap C_r\) olur; bu ise istenendir.
\(\blacksquare\)
9.3 Köşe Noktaları, Politoplar ve Simpleksler
Tanım 9.1 (Köşe Noktası) \(M \subset \mathbb{R}^n\) konveks küme olmak üzere, eğer bir \(x \in M\) noktası için
\[x = \tfrac{1}{2}x_1 + \tfrac{1}{2}x_2, \qquad x_1, x_2 \in M,\ x_1 \ne x_2\]
olacak biçimde \(x_1, x_2\) noktaları bulunamıyor ise \(x\) noktasına \(M\) kümesinin bir köşe noktası (uç noktası) denir. Eşdeğer olarak: \(x\), \(M\)’nin içinde kalan hiçbir doğru parçasının iç noktası değildir.
Tanım 9.2 (Politop) Sonlu noktalı bir kümenin konveks örtüsüne bir politop denir.
Tanım 9.3 (Simpleks) \(x_1, \dots, x_{k+1} \in \mathbb{R}^n\) noktaları afin bağımsız (yani \(x_2 - x_1, \dots, x_{k+1} - x_1\) lineer bağımsız) olmak üzere
\[\operatorname{conv}\{x_1, \dots, x_{k+1}\} = \left\{ \sum_{i=1}^{k+1} \lambda_i x_i : \sum_{i=1}^{k+1} \lambda_i = 1,\ \lambda_i \ge 0,\ i = 1, \dots, k+1 \right\}\]
kümesine \(\mathbb{R}^n\)’de \(x_1, \dots, x_{k+1}\) köşe noktalı bir \(k\)-(boyutlu) simpleks denir.
Örnek 9.2 (Düşük Boyutlu Simpleksler) \(0\)-simpleks bir noktadır, \(1\)-simpleks bir doğru parçasıdır, \(2\)-simpleks bir üçgensel bölgedir, \(3\)-simpleks bir tetrahedrondur.
Buraya kadar konveks kümelere içeriden baktık. Bir sonraki hafta dışarıdan bakacağız: bir konveks kümeyi çevresinden bir hiperdüzlemle ayırmak.