Grafik Teorisinde İleriye Doğru Çok Büyük Küçük Bir Sıçrama

15 Mart'ta ilgi çekici seminer duyuruları, saymanın matematiksel çalışması olan kombinatorik alanında gümbürtüler gönderdi. Üç işbirlikçi, ertesi gün koordineli görüşmeler yapmayı planladı. Julian Sahasrabudhe Cambridge, İngiltere'deki matematikçilere hitap ederken, Simon Griffiths haberleri Rio de Janeiro'da paylaşacaktı ve Marcelo Kampos Sao Paulo'da. Her üç konuşmada da aynı başlıklar ve "eski bir Erdős sorunuyla ilgili son gelişmelere" atıfta bulunan şifreli, iki cümlelik özetler vardı. 1996'da ölen Macar matematikçi Paul Erdős poz verirken yüzlerce sorun kariyeri boyunca kombinatoristler, üçlünün konuşmayı planladığı belirli konuyu çabucak tahmin ettiler. Tüm matematikte hesaplanması en zor niceliklerden biri olan Ramsey sayısı denen bir şey hakkında söylentiler dönüyordu.

Ramsey sayıları, çok çeşitli sistemlerde kaçınılmaz kalıpları arayan Ramsey teorisi adı verilen bütün bir disiplini doğurdu.

Örneğin, tüm tamsayıları bir dizi kümeye yaymaya çalıştığınızı ve kümelerin herhangi birine eşit aralıklı sayı dizileri yerleştirmekten kaçınmak istediğinizi varsayalım. Ramsey teorisi başarısız olacağınızı gösterir (sonsuz kovanız yoksa). Teori, sayabileceğiniz çoğu şeye uygulanabilir. Zürih İsviçre Federal Teknoloji Enstitüsü'nden matematikçi Benny Sudakov, bunun temel dersi, "tamamen kaotik bir sistem yaratamazsınız" dedi.

Ramsey sayısı, belirli kalıpların kaçınılmaz olarak ortaya çıkmasından önce paradigmatik bir örneğin ne kadar büyük olması gerektiğini ölçer. Ancak, merkezi olmasına rağmen, Ramsey sayısını kimse hariç herkes için hesaplayamadı. en basit örnekler. Yapabildikleri en iyi şey, ne olabileceğine dair sınırlar (veya sınırlar) bulmaktır. O zaman bile, ilk olarak yaklaşık bir asır önce Erdős ve bir işbirlikçi tarafından kurulan üst sınır zar zor hareket etmişti.

Ardından, 15 Mart seminerlerinde ve o akşam daha sonra yayınlanan bir makalede, araştırmacılar Ramsey sayısının üst sınırını üstel bir miktarda iyileştirdiklerini duyurdular.

"Döşendim" dedi Yuval Wigderson, Tel Aviv Üniversitesi'nde bir matematikçi, yeni sonucu duyunca. "Kelimenin tam anlamıyla yarım saatten bir saate kadar titriyordum."

Parti Hatları

Ramsey teorisi en çok ya tamsayılar ya da grafikler hakkında sorular sorar. Bu bağlamda bir grafik, uzunluk veya - Ramsey sayılarında olduğu gibi - renk gibi özelliklere sahip olabilen, kenarlar adı verilen çizgilerle birbirine bağlanan düğümler adı verilen nokta koleksiyonlarına atıfta bulunur.

Eksiksiz bir grafik hem karmaşık hem de basittir; her düğüm diğer tüm düğümlere bağlıdır. Ramsey sayısı, belirli bir yapıya sahip olmaya zorlanmak için tam bir grafiğin kaç tane düğüm içermesi gerektiğini açıklar. Tam bir grafiğin kenarlarına iki renkten birinin atandığını söyleyin: kırmızı veya mavi. Ve kenarları, aynı renkteki kenarlara sahip bir grup düğümü birbirine bağlamaktan kaçınacak şekilde renklendirmeye çalıştığınızı varsayalım. 1930'da Frank Ramsey, bir grafiğin yeterince büyük olması durumunda, matematikçilerin tek renkli bir grup dediği, ortak kenarları tamamen kırmızı veya tamamen mavi olan bir grup düğüm oluşturmaktan kaçınmanın imkansız hale geldiğini kanıtladı.

Tek renkli bir kliğin ortaya çıkmaya zorlanmadan önce bir grafiğin tam olarak ne kadar büyük olması gerekir? Cevap, kliğin boyutuna bağlıdır. Ramsey, kenarlar ne kadar renkli olursa olsun, belirli bir boyutta tek renkli bir kliğin var olması gereken minimum düğüm sayısını temsil eden, şimdi Ramsey sayısı olarak adlandırılan bir sayı olduğunu gösterdi.

Ancak Ramsey sayısının büyüklüğünü saptamak zordur. 1935'te, Ramsey'nin var olduğunu göstermesinden beş yıl sonra, Erdős ve George Szekeres, Ramsey sayısının belirli bir boyuttaki bir klik için ne kadar büyük olduğuna dair yeni ve daha sıkı bir üst sınır sağladı. Ancak o zamandan beri matematikçiler, Erdős ve Szekeres'in hesaplamalarını zar zor geliştirebildiler.

Bunun ne anlama geldiğine dair daha iyi bir sezgi elde etmek için, düğümlerin bir partideki konukları temsil ettiği klasik bir örneği ele alalım. Herhangi iki konuk arasındaki kenarı daha önce tanışmışlarsa kırmızıya, tanışmamışlarsa maviye boyayın. İstediğiniz büyüklükte bir klik seçebilirsiniz — partiye yeteri kadar insanı davet edin ve birbirini tanıyan bir grup insanı (kelimenin birçok anlamıyla bir klik) davet etmekten veya birbirini tanıyan bir grup insanı davet etmekten kaçınamazsınız. daha önce hiç tanışmadım

"Bir grafikte sahip olabileceğiniz en basit şey, tek renkli bir gruptur" dedi. Maria Çudnovski, Princeton Üniversitesi'nde bir matematikçi. “Her büyük grafikte bunlardan büyük bir tanesini bulabilmeniz biraz şaşırtıcı. Tamamen net değil.”

İlk birkaç Ramsey sayısının hesaplanması nispeten basittir. Diyelim ki, matematikçiler için kaçınılmaz olarak iki boyutlu bir kliği veya R(2) tutması gereken en küçük grafiğin boyutunu bilmek istiyorsunuz. İki düğümlü tam bir grafik, bir kenarla birbirine bağlı iki düğüm olduğundan ve bu kenarın ya kırmızı ya da mavi olması gerektiğinden, R(2) 2'dir. Daha genel olarak, R(k) veya Ramsey sayısı k, ötesinde bir grafiğin boyutta bir klik içermesinden kaçınamayacağı minimum düğüm sayısıdır k.

3 büyüklüğündeki bir klik veya R(3) için Ramsey sayısının 6 olduğunu göstermek o kadar da zor değil (grafiğe bakın). Ancak 1955 yılına kadar R(4)'ün 18'e sabitlenmesi mümkün değildi. R(5) hala bilinmiyor - en az 43 ve 48'den büyük değil. Bu sayılar küçük olsa da, tüm olası renklendirmeleri elemek mümkün değil California Teknoloji Enstitüsü'nden David Conlon sorunun cevabını verdi. 43 düğümlü tam bir grafikte renklendirme sayısını düşünün. “903 kenarınız var; bunların her biri iki şekilde renklendirilebilir” diye açıkladı. “Yani 2 tane aldın⁹⁰³, bu sadece astronomik olarak büyük.

Kliğin boyutu arttıkça, Ramsey sayısını tutturma görevi daha da zorlaşıyor. Erdős, matematiksel olarak zorlu uzaylılarla topyekün savaşın, denemekten daha kolay olacağını söyledi. R(6)'yı bul102 ile 165 arasında bir yerde. Belirsizlik aralığı hızla büyüyor: Göre Stanisław Radziszowski tarafından derlenen tahminler, R(10) 798 kadar küçük ve 23,556 kadar büyük olabilir. Ancak matematikçilerin hedefleri, 10 olan Ramsey sayısının çok ötesine ulaşıyor. R('nin iyi bir tahminini verecek bir formül istiyorlar.k), hatta - veya özellikle - ne zaman k son derece büyüktür.

Wigderson, "Kombinatorik alanında bu sorunu en azından birazcık bile düşünmemiş birini tanımıyorum," dedi. "Bu sorun bence gerçekten özel."

Mahkemede Düzen

Frank Ramsey, 26 yaşındayken ölen eklektik, parlak bir şahsiyetti. Ölmeden sadece haftalar önce, Londra Matematik Derneği Tutanakları yayınlanan kağıt Ramsey sayılarını tanıttığı. O çalışma grafiklerle ilgili bile değildi, matematiksel mantıktaki bir problemle ilgiliydi. Ramsey, belirli koşulları karşılayan bir ifadenin en azından bazı zamanlar doğru olması gerektiğini kanıtladı. Bu koşullardan biri, ifadeyi test etmek için geniş bir senaryo "evreninin" olmasıydı. Ramsey, bu sonuca giden yolda bir atlama taşı olarak, Ramsey sayısının sonlu olduğunu gösterdi.

Beş yıl sonra Erdős ve Szekeres, Ramsey sayısının k 4'dan az^k. Ve bundan 12 yıl sonra, Erdős gösterdi yaklaşık $latex sqrt{2}^k$'dan daha büyük olduğunu. Bunu yapmak için, kenarları rastgele renklendirilmiş bir grafiğin tek renkli bir klik içerme olasılığını hesapladı. Bu "olasılığa dayalı" teknik, grafik teorisinde büyük ölçüde etkili oldu. Ayrıca R(k) katlanarak büyüyen iki kale direği arasında: $latex sqrt{2}^k$ ve $latex 4^k$.

On yıllar geçtikçe, çok sayıda matematikçi, Ramsey sayısının olası değerleri arasındaki boşluğu daraltmaya çalıştı. Bazıları başarılı oldu: 1975'te Joel Spencer Alt sınırı ikiye katladı. Ve bir dizi makale Conlon, Andrew Thomason ve Ashwin Şah üst sınırı aşağı itti 4'ye kadar yaklaşık $latex 2^{log(k)^2020}$ katsayı ile. Ancak Ramsey sayısındaki sınırların boyutlarıyla karşılaştırıldığında, bu ayarlamalar küçüktü. Buna karşılık, Erdős ve Szekeres'in R formülündeki 4'e herhangi bir azalma (k) < 4^k hızla büyüyen üstel bir gelişme olacaktır. k büyür.

"Sadece sevimli küçük bir soru gibi görünüyor," dedi Rob MorrisBrezilya'nın Rio de Janeiro'daki Saf ve Uygulamalı Matematik Enstitüsü IMPA'da bir matematikçi olan ve yeni sonucu Campos, Griffiths ve Sahasrabudhe ile birlikte yazan. “Takdir etmek biraz incelikli. Ama insanlar bunu gerçekten önemsiyor.” Bu muhtemelen yetersiz bir ifadedir. "Bunu 1936'da kanıtlamış olsalardı, insanlar, tamam, bu kadar önemli olan ne?" derdi. dedi Morris ve Sahasrabudhe'nin Memphis Üniversitesi'nde doktora danışmanı olan Béla Bollobás. "O zamandan beri bunun çok büyük bir sorun olduğu kanıtlandı, çünkü yıllar içinde Ramsey probleminin çeşitli varyantları üzerine birkaç bin makale yazıldı." Gibi Liana YepremyanEmory Üniversitesi'nden bir matematikçi, "Ramsey sayıları kombinatorik ile olasılık ve geometri arasındaki köprüyü oluşturuyor" dedi.

Oyun Teorisi

 Ağustos 2018'de Sahasrabudhe, IMPA'da Morris altında doktora sonrası araştırmacıydı. İkili, yakınlardaki Papalık Katolik Üniversitesi'nde ders veren Griffiths ile yeni bir proje başlatmayı umuyordu. Conlon'dan bir makale dikkatlerini çekti. Makale, Ramsey sayısında üstel bir iyileşme elde etmek için olası bir stratejinin ana hatlarını çizdi. Griffiths, Morris ve Sahasrabudhe bu fikirle oynamaya başladılar.

Sahasrabudhe, "Başlangıçta gerçekten heyecan vericiydi," diye hatırladı. Tartışmalarının bir taslağını çıkarmalarının sadece bir ay sürdüğünü söyledi.

Planları, Erdős ve Szekeres'in $lateks R(k) < 4^k$ olduğuna dair orijinal ispatında kullanılan fikirler üzerine inşa etmekti. Ramsey sayısının en fazla $latex 4^k$ olduğunu kanıtlamak için, $latex 4^k$ düğümleriyle tam bir grafik üzerinde bir oyun oynadığınızı hayal edin. Oyunda iki oyuncu vardır. Birincisi, rakibiniz her bir kenarı ya kırmızı ya da maviye boyar, kenarları tek renkli bir grup oluşturmaktan kaçınacak şekilde renklendirmeyi umar. k düğümleri.

Rakibinizin boyaması bittiğinde, tek renkli bir grup aramak sizin işiniz. Birini bulursan kazanırsın.

Bu oyunu kazanmak için basit bir strateji takip edebilirsiniz. Düğümlerinizi iki kovaya ayırmayı (mecazi olarak) düşünmek yardımcı olur. Bir kovadaki düğümler mavi bir klik oluşturacak ve diğerindeki düğümler kırmızı bir klik oluşturacak. Bazı düğümler silinecek ve bir daha onlardan haber alınamayacak. Başlangıçta her iki kova da boştur ve her düğüm bir tanesine girmeye adaydır.

Hoşunuza giden herhangi bir düğümle başlayın. Ardından bağlantı kenarlarına bakın. Kenarların yarısı veya daha fazlası kırmızıysa, tüm mavi kenarları ve bağlı oldukları düğümleri silin. Ardından, orijinal seçiminizi "kırmızı" kovaya koyun. Bu düğümün tüm kırmızı kenarları, kovanın içinden grafiğin geri kalanına yapışarak hala canlı ve iyi durumdadır. Kenarların yarısından fazlası maviyse, benzer şekilde kırmızı kenarları ve düğümleri silip mavi kovaya koyarsınız.

Düğüm kalmayıncaya kadar tekrarlayın. (Grafik tamamlandığından, herhangi bir noktada kalan her düğüm, bunlardan birine yerleştirilene kadar her iki kovaya da bağlanır.)

İşiniz bittiğinde kovaların içine bakın. Bir düğüm ancak mavi komşuları elendikten sonra kırmızı kovaya girdiğinden, kırmızı kovadaki tüm düğümler kırmızı kenarlarla birbirine bağlanır - kırmızı bir klik oluştururlar. Aynı şekilde, mavi kova da mavi bir klik oluşturur. Orijinal grafiğinizde en az $latex 4^k$ düğüm varsa, bu gruplardan birinin en az $latex içermesi gerektiğini kanıtlamak mümkündür. k orijinal grafikte tek renkli bir kliği garanti eden düğümler.

Bu argüman zekice ve zariftir, ancak yalnızca bir tanesine gerçekten ihtiyacınız olmasına rağmen, biri mavi diğeri kırmızı olmak üzere iki grup oluşturmanızı sağlar. Conlon, her zaman kırmızıya dönmenin daha verimli olacağını açıkladı. Bu strateji altında, her adımda bir düğüm seçer, mavi kenarlarını siler ve onu kırmızı kovaya atarsınız. Kırmızı kova daha sonra hızla dolacak ve siz de kırmızı bir klik oluşturacaksınız. k zamanın yarısında düğümler.

Ancak stratejiniz herhangi bir kırmızı-mavi renklendirme için çalışmalıdır ve her zaman çok sayıda kırmızı kenarlı bir düğüm bulup bulamayacağınızı bilmek zordur. Dolayısıyla, Conlon'un önerisini takip etmek, kendisine bağlı neredeyse hiç kırmızı kenarı olmayan bir düğüme girme riskini taşır. Bu, sizi grafiğin büyük bir bölümünü bir kerede silmeye zorlar ve düğümleriniz bitmeden kliğinizi oluşturmak için çabalamanıza neden olur. Conlon'un önerisini gerçekleştirmek için Griffiths, Morris ve Sahasrabudhe'nin bu riskin önlenebilir olduğunu kanıtlaması gerekiyordu.

Açık Kitap Sınavı

Griffiths, Morris ve Sahasrabudhe oynanışlarını güncellerken biraz daha dolambaçlı bir yol izlediler. Doğrudan kırmızı ve mavi kovalarına düğüm atarak tek renkli bir klik oluşturmak yerine, önce kırmızı kitap adı verilen bir yapı oluşturmaya odaklandılar.

Grafik teorisinde bir kitap iki bölümden oluşur: "omurga" adı verilen tek renkli bir grup ve "sayfalar" adı verilen ikinci, farklı düğüm kümesi vardır. Kırmızı bir kitapta, sırttaki düğümleri birleştiren tüm kenarlar, sırtı sayfalara bağlayan kenarlar gibi kırmızıdır. Bununla birlikte, sayfalardaki düğümleri birleştiren kenarlar, herhangi bir renk kombinasyonu olabilir. Conlon, 2018 tarihli makalesinde, bir kitabın sayfalarında kırmızı bir grup bulabilirseniz, daha büyük bir kırmızı grup elde etmek için bunu omurgayla birleştirebileceğinizi belirtmişti. Bu, büyük bir kırmızı klik aramasını daha kolay iki aramaya ayrıştırmanıza olanak tanır. İlk olarak, kırmızı bir kitap arayın. Sonra kitabın sayfalarında bir klik arayın.

Griffiths, Morris ve Sahasrabudhe, oyun kazandıran algoritmayı kırmızı bir klik yerine kırmızı bir kitap oluşturacak şekilde ayarlamak istediler. Projelerine sadece birkaç hafta kala bu plana karar vermiş olsalar da, işe yaraması yıllar alacaktı. Hala tüm kırmızı kenarlarını kaybetme tehdidini savuşturmaları gerekiyordu.

2021'de projeye katılan Campos, "Çok uzun süre sıkışıp kaldık" dedi.

Bu Ocak ayında, dört matematikçi problemin başka bir versiyonuna geçme konusunda anlaştılar. Bu sürüm kulağa daha karmaşık geliyor, ancak daha kolay olduğu ortaya çıktı.

Ekip başından beri Ramsey numarası R(k), "köşegen" Ramsey sayısı olarak da bilinir. R boyutunda bir grafik(k) içermek zorundadır k Hepsi aynı renkteki kenarlarla birbirine bağlı düğümler, ancak bu rengin kırmızı veya mavi olması önemli değil. Öte yandan, “köşegen dışı” Ramsey sayısı R(k, l) ile kırmızı bir klik içermeden önce bir grafiğin ne kadar büyük olması gerektiğini ölçer. k düğümler veya mavi bir klik l düğümler. Grup, diyagonal sorunu çözmeye devam etmek yerine diyagonal olmayan versiyonu denemeye karar verdi. Bu aydınlatıcı oldu.

Griffiths, "Uzun bir süre boyunca, ittiğiniz her kapı ya sürgülenmiş ya da en azından içinden geçilmesi oldukça zormuş gibi geldi" dedi. "Ve bu değişiklikten sonra, her kapının açık olduğunu hissettin. Her nasılsa, her şey çalışıyor gibiydi. Köşegen dışı sürümde, belirli bir protokolü izleyerek bir grup mavi kenarı bir kerede silmenin bir yolunu buldular, bu da kırmızı kenarların yoğunluğunu artırdı ve köşegen dışı Ramsey sayısında gelişmiş bir sınıra yol açtı. "Yoğunluk artışı" argümanı olarak adlandırılan bu yöntem, daha önce çözmek için kullanılmıştı. kombinatorikteki diğer önemli problemler, ancak Ramsey sayısı probleminde kullanılmamıştı.

Dört matematikçi daha sonra köşegen sonucunun yolunu açmak için köşegen dışı Ramsey sayısındaki yeni sınırı kullandı. Şubat ayının başında, nihayet, matematikçilerin yaklaşık bir asırdır peşinde oldukları bir başarı olan, Ramsey sayısının sınırını üstel bir faktör kadar indirmişlerdi. Ve bunu, Erdős ve Szekeres'in 1935'te ortaya koydukları aynı argüman çizgisini modernize ederek yaptılar.

Epsilon, Epsilon

16 Mart'taki görüşmelerin ardından katılımcılar söylentileri doğrulamaya başladı. Sahasrabudhe'nin konuşmasından fotoğraflar, telefon görüşmeleri ve özel mesajlarda yayıldı - hatta bir belirsiz ama müstehcen yazı matematikçi Gil Kalai'nin blogunda. Campos, Griffiths, Sahasrabudhe ve Morris $lateks R(k) < 3.993^k$ olduğunu gösterdiklerini iddia ettiler. O gece, dört yazar makalelerini çevrimiçi yayınladılar, matematikçilerin yeni kanıtı kendileri görmelerine izin veriyor.

"Aslında çoğumuz hayatımızda böyle bir gelişme görmeyi beklemiyorduk" dedi. Matija Buciç, Princeton Üniversitesi'nde ve İleri Araştırma Enstitüsü'nde bir matematikçi. "Bence kesinlikle harika bir sonuç."

Birçok uzman, üstel engelin ortadan kalkmasıyla daha fazla ilerlemenin hızla geleceğinden umutlu. Yeni makalenin yazarları, argümanlarını gereksiz ayrıntılarla bulandırmamak için kasıtlı olarak yöntemlerinin sınırlarını zorlamadılar. Campos, "Metodun gerçekte ne kadar ileri gidebileceğiyle çok ilgileniyorum, çünkü hiçbir fikrim yok," dedi.

“Son derece dahiyane, kesinlikle harika bir kanıt ve gerçek bir buluş. Bollobás, "Bu yüzden artık bent kapaklarının açılmasını bekliyorum" dedi. “Üç yıl içinde tartışmanın olası iyileştirmeler hakkında olacağına inanıyorum. 3.993'ü 3.9'a yükseltebilir miyiz? Belki 3.4'e? Peki ya 3?

Yeni kanıt 56 sayfada geliyor ve kombinatorik topluluğu tarafından her ayrıntının tam olarak doğrulanması haftalar alacak. Ancak meslektaşları iyimser. “Bu yazar grubu, çok ciddi insanlar. Ve çok teknik şeylerde gerçekten çok iyi olan insanlar," dedi.

İş ortaklarına gelince, Griffiths aynı fikirde. “Zeki insanlarla çalışmak bir ayrıcalık, değil mi? Ve bunun için çok minnettar olduğumu düşünüyorum” dedi. "Bana bıraksalardı, ayrıntıları doğru bir şekilde öğrenmem beş yıl daha alabilirdi."