HER NOKTAYI DİĞER HER NOKTAYA BAĞLAYIN: EN AZ KESİŞİM SAYISI KANITLANDI

Bir kâğıda beş nokta koyun ve her çifti bir eğriyle birleştirin: toplam on eğri. Eğriler istediğiniz gibi kıvrılabilir, ama hiçbiri üçüncü bir noktanın içinden geçemez. Her kesişimden kaçınmaya çalışın; başaramayacaksınız. Beş noktayla en az 1 kesişim kaçınılmazdır; altı noktayla en az 3; on noktayla en az 60.

Matematikçiler böyle bir resme tam graf Kₙ’nin — n nokta, her çift birbirine bağlı — bir çizimi, herhangi bir çizimin ulaşabileceği en az kesişim sayısına da grafın kesişim sayısı (crossing number) der. Çek Cumhuriyeti’ndeki Charles Üniversitesi’nden Martin Balko bu soruyu “topolojik graf teorisinin en ünlü problemlerinden biri” olarak niteliyor.

Bir sanatçının sayımı

1950’lerin sonunda İngiliz sanatçı Anthony Hill, Kₙ’nin tam olarak

Z(n) = ¼ ⌊n/2⌋ ⌊(n − 1)/2⌋ ⌊(n − 2)/2⌋ ⌊(n − 3)/2⌋

kesişime sahip çizimlerini oluşturdu; burada ⌊ ⌋ aşağı yuvarlama anlamına geliyor. Hiçbir çizimin daha iyisini yapamayacağı tahmini ilk kez Guy tarafından yayımlandı, daha sonra Harary ve Hill tarafından tartışıldı, Erdős ile Guy tarafından da yaygınlaştırıldı. Bu tahmin Harary–Hill sanısı ya da Guy sanısı olarak bilinir.

Formül hızla tırmanıyor:

4 ya da daha az nokta: 0 kesişim
5 nokta: 1
7 nokta: 9
10 nokta: 60
14 nokta: 315

Altmış yıllık kısmi yanıtlar

Tam olarak Z(n) kesişimli çizimler her nokta sayısı için vardı; zor olan, hiçbir çizimin daha iyisini yapamadığını göstermekti.

Altmış yılı aşkın bir süre boyunca bu yalnızca özel çizim türleri için kanıtlandı — örneğin tüm noktaların tek bir doğru üzerinde bulunduğu ve her eğrinin bu doğrunun tek bir tarafında tutulduğu çizimler ya da noktaların bir küre üzerinde bulunduğu ve her eğrinin en kısa yolu izlediği çizimler. Balko’nun kendisi de Fulek ve Kynčl ile birlikte bu sınıflardan birini çözmüştü. 2021’e gelindiğinde bilgisayarlar formülü 14 noktaya kadar doğrulamıştı. Çok büyük nokta sayıları için en iyi genel sonuçlar Z(n)’nin önce en az %98,5’ini, ardından %98,99’unu garanti ediyordu.

Bir kanıt, ardından daha anlaşılır bir kanıt

2026’da OpenAI her nokta sayısı için bir kanıt duyurdu; Balko’nun makalesi bunu bir “OpenAI Math Release preprint” olarak listeliyor ve teoremi ona atfediyor. Makale bu kanıtın nasıl bulunduğunu söylemiyor. Balko’nun sözleriyle orijinal kanıt “görece kısa”, ama “izlemesi oldukça zor”. Ön baskısı, yazdığına göre “yalnızca temel düzeyde doğrusal cebir ve graf teorisi bilgisi gerektiren”, sadeleştirilmiş bir varyant sunuyor. Bir başka matematikçi, Gelasio Salazar, ayrı ve ayrıntılı bir açıklama hazırlıyor.

Kesişimler yerine katsayıları saymak

Bilinen çizimler zaten Z(n)’ye ulaştığından, yalnızca alt sınırın kanıtlanması gerekiyor. Bu dört hamlede yapılıyor.

Tek sayılar yeterli. En iyi bir çizim, ortak bir noktayı paylaşan eğriler hiç kesişmeyecek biçimde yeniden çizilebilir; böylece her kesişim 4 farklı noktayı içerir. 6 noktanın her birini sırayla silin: geriye kalan her 5 noktalı resimde en az 1 kesişim vardır ve her kesişim 6 silmenin tam olarak 2’sinden sağ çıkar (kendi 4 noktasından biri silindiğinde kaybolur, diğer 2 silmede ise kalır). Dolayısıyla kesişim sayısının iki katı en az 6’dır: yani en az 3, bu da Z(6)’dır. Aynı sayım her çift sayı için işe yarar.
Bir polinom ailesi. Her noktaya kendi sayısını verin. Bir kesişim iki eğriyi, dolayısıyla dört noktayı, dolayısıyla dört sayıyı içerir. Balko, n tek olduğunda ailenin tam olarak Z(n) bağımsız katsayıya sahip olacağı biçimde seçilmiş dört değişkenli polinomlar kullanıyor — 7 nokta için 3 × 3 = 9.
Çok az kesişim boşluk bırakır. Bir polinomun bir kesişimde sıfır olmasını istemek bir denklemdir. Serbest katsayılardan daha az denklem olduğunda doğrusal cebir her zaman sıfır olmayan bir çözüm bırakır. Dolayısıyla Z(n)’den az kesişimi olan bir çizim, tüm kesişimlerinde sıfır olan, sıfırdan farklı bir polinomla birlikte gelirdi; bunların en düşük dereceli olanını alın.
Düzlem karşı koyar. Geometri işe klasik bir olgu aracılığıyla girer: düzlemdeki kapalı bir ilmek bir başkasını sağdan sola, tam olarak soldan sağa kestiği kadar sık keser. İyi seçilmiş ağırlıklarla bu, polinomun değerlerinin karelerinden oluşan, bazıları pozitif, bazıları negatif sayılan ve toplamı sıfır olan bir toplam verir. Pozitif terimlerin hepsi, polinomun sıfır olduğu kesişimlerde yer alır; dolayısıyla negatif olanlar da sıfır olmak zorundadır. İlmek olgusunun ikinci bir kullanımı polinomu sabit bir çarpana bölünebilir kılar; bölmek, aynı özelliğe sahip, daha düşük dereceli, sıfırdan farklı bir polinom verir — bu imkânsızdır, çünkü en düşük dereceliyi almıştık.

Bu işaret argümanı Balko’nun ana değişikliği: orijinaldeki “dejenere olmayan bir çift doğrusal form ve ortogonal tümleyenler içeren” argümanın yerini alıyor. Ayrıca ilmek olgusunu farklı biçimde kanıtlıyor ve her noktayı daha doğrudan yalıtıyor.

Başka ağlar da bir çırpıda çözüldü

Kesişimler yerine, en az bir kez kesişen eğri çiftleri ya da tek sayıda kesişen eğri çiftleri sayılsa da yanıt Z(n) olarak kalır — ortak bir noktayı paylaşan eğriler başka hiçbir yerde buluşmadığı sürece. Daha önceki indirgemelerle birleştirildiğinde teorem; bazı bağlantıları çıkarılmış tam graflar, bir yol boyunca ya da çift uzunluklu bir döngü çevresinde zincirlenmiş tam graf kopyaları ve genişletilmiş Sierpiński grafları adı verilen fraktal benzeri bir ağ ailesi için de kesin kesişim sayılarını veriyor.

6 noktalı tam graftan tek bir eğri çıkarın, en az kesişim sayısı 3’ten 2’ye düşer; 8 noktada ise 18’den 15’e.