1850 olarak, Thomas Penyington Kirkmanİngiltere Kilisesi'nde papaz olarak asıl sorumluluğunu yerine getirmediği zaman bir matematikçi olan "öğrenci kız sorununu" şöyle tanımladı: Hiçbiri iki kez yan yana yürümesin diye her gün onları.”
Modern bir matematikçi için, bu tür bir problem en iyi hipergraf olarak hayal edilebilir - üç veya daha fazla grup halinde toplanan bir dizi düğüm. 15 kız öğrenci düğümdür ve “yan yana üç” her grup, üç düğümü birbirine bağlayan üç çizgili veya kenarlı bir üçgen olarak düşünülebilir.
Kirkman'ın sorunu, esasen, tüm kız öğrencileri birbirine bağlayan bu üçgenlerin bir düzenlemesi olup olmadığını, ancak iki üçgenin bir kenarı paylaşmaması gibi ek bir kısıtlama olup olmadığını soruyor. Kenar paylaşımı, iki kız öğrencinin birden fazla kez birlikte yürümesi gerektiği anlamına gelir. Bu kısıtlama, her kızın bir hafta boyunca her gün iki yeni arkadaşıyla birlikte yürüdüğü anlamına gelir, böylece olası her çift tam olarak bir kez bir araya gelir.
Bu problem ve benzeri problemler, Kirkman'ın sorusunu sormasından bu yana yaklaşık iki yüzyıl boyunca matematikçileri şaşırttı. 1973'te efsanevi matematikçi Paul Erdős benzer bir poz verdi. Görünüşte uyumsuz iki özelliğe sahip bir hipergraf oluşturmanın mümkün olup olmadığını sordu. İlk olarak, her düğüm çifti, kız öğrencilerde olduğu gibi tam olarak bir üçgenle bağlanmalıdır. Bu özellik grafiği üçgenlerle yoğunlaştırır. İkinci gereklilik, üçgenleri çok hassas bir şekilde yayılmaya zorlar. (Özellikle, herhangi bir küçük üçgen grubu için, üçgenlerden en az üç düğüm daha olmasını gerektirir.) "Yoğun parçaları olmayan yoğun bir genel nesneye sahip olduğunuz bu biraz çelişkili davranışa sahipsiniz," dedi. David Conlon, California Teknoloji Enstitüsü'nde bir matematikçi.
Bu Ocak ayında 50 sayfalık karmaşık bir kanıt, dört matematikçi, yeterli düğümünüz olduğu sürece böyle bir hipergraf oluşturmanın her zaman mümkün olduğunu kanıtladı. “Sadece bunu elde etmek için [onların] yaşadıkları teknik detay inanılmazdı” dedi. Alan Lo, Birmingham Üniversitesi'nde bir matematikçi. Conlon da aynı fikirde: "Gerçekten etkileyici bir çalışma."
Araştırma ekibi, üçgenleri seçmek için rastgele bir süreçle başlayıp, ihtiyaçlarını karşılamak için son derece dikkatli bir şekilde tasarlayarak Erdös'ün şeytani gereksinimlerini karşılayan bir sistem kurdu. Conlon, “İspatlamaya giren zor değişikliklerin sayısı aslında biraz şaşırtıcı” dedi.
Stratejileri, hipergrafı tek tek üçgenlerden dikkatli bir şekilde oluşturmaktı. Örneğin, 15 kız öğrencimizi hayal edin. Her çiftin arasına bir çizgi çizin.
Buradaki amaç, üçgenlerin iki gereksinimi karşılayacak şekilde bu çizgilerin üzerindeki üçgenleri bulmaktır: Birincisi, hiçbir iki üçgenin bir kenarı yoktur. (Bu gereksinimi karşılayan sistemlere Steiner üçlü sistemleri denir.) İkinci olarak, üçgenlerin her küçük alt kümesinin yeterince fazla sayıda düğüm kullanmasını sağlayın.
Araştırmacıların bunu yapma şekli belki de en iyi şekilde bir benzetme ile anlaşılır.
Kenarlardan üçgenler yapmak yerine Lego tuğlalarından evler inşa ettiğinizi söyleyin. Yaptığınız ilk birkaç bina, yapısal güçlendirmeler ve ayrıntılı süslemelerle abartılı. Bunlarla işiniz bittiğinde, bir kenara koyun. Bir "emici" olarak hizmet edecekler - bir tür yapılandırılmış stok.
Şimdi fazla planlama yapmadan kalan tuğlalarınızdan binalar yapmaya başlayın. Lego arzınız azaldığında, kendinizi bazı başıboş tuğlalar veya yapısal olarak sağlam olmayan evler ile bulabilirsiniz. Ancak yutucu binalar çok abartılı ve güçlendirilmiş olduğu için, şuradan burada birkaç tuğla koparabilir ve onları felakete yol açmadan kullanabilirsiniz.
Steiner üçlü sistemi durumunda, üçgenler oluşturmaya çalışıyorsunuz. Bu durumda emiciniz, özenle seçilmiş bir kenar koleksiyonudur. Sistemin geri kalanını üçgenlere ayıramıyorsanız, emiciye giden kenarlardan bazılarını kullanabilirsiniz. Ardından, bunu yapmayı bitirdiğinizde, emicinin kendisini üçgenlere bölersiniz.
Absorpsiyon her zaman işe yaramaz. Ancak matematikçiler, engelleri aşmanın yeni yollarını bularak süreçle uğraştılar. Örneğin, yinelemeli absorpsiyon adı verilen güçlü bir değişken, kenarları iç içe bir dizi dizisine böler, böylece her biri bir sonraki en büyük için bir emici görevi görür.
Conlon, “Son on yılda büyük gelişmeler oldu” dedi. “Bu bir tür sanat formu, ancak bu noktada gerçekten yüksek sanat seviyesine taşıdılar.”
Erdős'in sorunu yinelemeli emilim ile bile zordu. “Bu sorunun neden çözülmediği oldukça hızlı bir şekilde ortaya çıktı” dedi. Mehtaab Sawhneyile birlikte çözen dört araştırmacıdan biri Ashwin ŞahSawhney ile birlikte Massachusetts Teknoloji Enstitüsü'nde yüksek lisans öğrencisi olan; Michael SimkinHarvard Üniversitesi Matematik Bilimleri ve Uygulamaları Merkezi'nde doktora sonrası araştırmacı; ve Matthew KwanAvusturya Bilim ve Teknoloji Enstitüsü'nde matematikçi. "Oldukça ilginç, oldukça zor teknik görevler vardı."
Örneğin, yinelemeli absorpsiyonun diğer uygulamalarında, bir kümeyi - ya üçgenlerle, Steiner üçlü sistemleri için ya da başka problemler için başka yapılarla - kaplamayı bitirdiğinizde, onun ele alındığını düşünebilir ve onu unutabilirsiniz. Ancak Erdős'in koşulları dört matematikçinin bunu yapmasını engelledi. Sorunlu bir üçgen kümesi, birden fazla yutucu kümeden düğümleri kolayca içerebilir.
Sawhney, "500 adım önce seçtiğiniz bir üçgen, bunun hakkında nasıl düşüneceğinizi bir şekilde hatırlamanız gerekiyor" dedi.
Dördü sonunda anladı ki, eğer üçgenlerini dikkatli seçerlerse, her küçük şeyi takip etme ihtiyacını ortadan kaldırabilirlerdi. Sawhney, "Yapılması daha iyi olan şey, herhangi bir küçük 100 üçgen kümesini düşünmek ve bu üçgen kümesinin doğru olasılıkla seçildiğini garanti etmektir" dedi.
Yeni makalenin yazarları, tekniklerinin bu tek sorunun ötesine geçebileceği konusunda iyimserler. Onlarda var stratejilerini zaten uygulamışlar hakkında bir soruna Latin karelerbir sudoku bulmacasının basitleştirilmesi gibidir.
Bunun ötesinde, sonunda özümseme yöntemlerine yol açabilecek birkaç soru var, dedi Kwan. "Birleştiricilerde, özellikle de rastgele süreçlerin gerçekten güçlü bir araç olduğu tasarım teorisinde çok fazla sorun var." Böyle bir problem olan Ryser-Brualdi-Stein varsayımı da Latin kareleriyle ilgilidir ve 1960'lardan beri bir çözüm beklemektedir.
Emilim, bu soruna düşmeden önce daha fazla gelişmeye ihtiyaç duysa da, 30 önceki başlangıcından bu yana çok yol kat etti, dedi. Maya SteinŞili Üniversitesi Matematiksel Modelleme Merkezi müdür yardımcısı. "Bu yöntemlerin nasıl geliştiğini görmek gerçekten harika bir şey."
