Всички сме били там: взирали се в тест по математика със задача, която изглежда невъзможна за решаване. Ами ако намирането на решението на даден проблем отнема почти век? За математиците, които се занимават с теорията на Рамзи, това е много вярно. Всъщност, малък напредък е постигнат в решаването на проблемите на Рамзи от 30-те години на миналия век.
Изследователите от Калифорнийския университет в Сан Диего Жак Верстраете и Сам Матеус са намерили отговора на r(4,t), дългогодишен проблем на Рамзи, който обърква света на математиката от десетилетия.
Какъв (беш)е проблемът на Рамзи?
На математически език графиката е поредица от точки и линиите между тези точки. Теорията на Рамзи предполага, че ако графиката е достатъчно голяма, вие гарантирано ще намерите някакъв ред в нея – или набор от точки без линии между тях, или набор от точки с всички възможни линии между тях (тези набори се наричат „клики“). Това се записва като r(s,t), където s са точките с прави и t са точките без прави.
За тези от нас, които не се занимават с теория на графите ,
най-известният проблем на Рамзи, r(3,3), понякога се нарича „теоремата за приятели и непознати“ и се обяснява чрез парти: в група от шест души, ще намерите поне трима души, които всички се познават, или трима души, които не се познават. Отговорът на r(3,3) е шест.
„Това е природен факт, абсолютна истина“, заявява Верстраете. „Няма значение каква е ситуацията или кои шестима души ще изберете – ще намерите трима души, които всички се познават, или трима души, които не се познават. Може да успеете да намерите повече, но вие сте гарантирано, че ще има поне трима в едната или другата клика.“
Какво се случи, след като математиците установиха, че r(3,3) = 6? Естествено, те искаха да знаят r(4,4), r(5,5) и r(4,t), където броят на точките, които не са свързани, е променлив. Решението на r(4,4) е 18 и е доказано с помощта на теорема, създадена от Пол Ердош и Джордж Секереш през 30-те години на миналия век.
В момента r(5,5) все още е неизвестен.
Добрият проблем отвръща на удара
Защо нещо толкова просто за изказване е толкова трудно за разрешаване? Оказва се, че е по-сложно, отколкото изглежда. Да приемем, че знаете, че решението на r(5,5) е някъде между 40–50. Ако сте започнали с 45 точки, ще има повече от 10 234 графики за разглеждане.
„Тъй като тези числа са изключително трудни за намиране, математиците търсят оценки“, обясни Верстраете. „Това е, което Сам и аз постигнахме в нашата скорошна работа. Как да намерим не точния отговор, а най-добрите оценки за това какви могат да бъдат тези числа на Рамзи?“
Студентите по математика научават за проблемите на Рамзи отрано, така че r(4,t) е на радара на Verstraete през по-голямата част от професионалната му кариера. Всъщност той за първи път видя проблема в печатен вид в Erdös on Graphs: His Legacy of Unsolved Problems, написана от двама професори от Калифорнийския университет в Сан Диего, Фан Чунг и покойния Рон Греъм. Проблемът е предположение от Erdös, който предложи $250 на първия човек, който може да го реши.
„Много хора са мислили за r(4,t) – това е открит проблем повече от 90 години“, каза Верстраете. „Но това не беше нещо, което беше в челните редици на моето изследване. Всеки знае, че е трудно и всеки се е опитал да го разбере, така че освен ако нямате нова идея, едва ли ще стигнете доникъде.“
След това преди около четири години Верстраете работеше върху различен проблем на Рамзи с математик от Университета на Илинойс-Чикаго, Друв Мубайи. Заедно те откриха, че псевдослучайните графики могат да разширят настоящите познания по тези стари проблеми.
През 1937 г. Ердос открива, че използването на произволни графики може да даде добри долни граници на проблемите на Рамзи. Това, което Verstraete и Mubayi откриха, беше, че вземането на проби от
псевдослучайни графики често дава по-добри граници на числата на Рамзи, отколкото произволните графики. Тези граници – горна и долна граница на възможния отговор – затегнаха обхвата на оценките, които можеха да направят. С други думи, те се доближаваха до истината.
През 2019 г., за радост на математическия свят, Verstraete и Mubayi използваха псевдослучайни графики за решаване на r(3,t). Въпреки това, Verstraete се бори да изгради псевдослучайна графика, която може да помогне за решаването на r(4,t).
Той започва да се занимава с различни области на математиката извън комбинаториката, включително крайна геометрия, алгебра и вероятност. В крайна сметка той обедини сили с Матеус, постдокторант от неговата група, чийто опит беше в крайната геометрия.
„Оказа се, че псевдослучайната графика, от която се нуждаехме, може да бъде намерена в крайна геометрия“, каза Верстраете. „Сам беше идеалният човек, който дойде и ни помогне да изградим това, от което се нуждаехме.“
След като разполагаха с псевдослучайната графика, те все още трябваше да разгадаят няколко математически елемента. Отне почти година, но в крайна сметка разбраха, че имат решение: r(4,t) е близо до кубична функция от t. Ако искате парти, на което винаги ще има четирима души, които всички се познават, или t хора, които всички не се познават, ще ви трябват приблизително t 3 души. Има малка звездичка (всъщност о), защото не забравяйте, че това е приблизителна оценка, а не точен отговор. Но t 3 е много близо до точния отговор.
Констатациите в момента се преразглеждат от Annals of Mathematics . Предпечат може да се види на arXiv .
„Наистина ни отне години да го решим“, каза Верстраете. „И имаше много моменти, в които бяхме блокирани и се чудехме дали изобщо ще успеем да го разрешим. Но човек никога не трябва да се предава, независимо колко време отнема.“
Верстраете подчертава важността на постоянството – нещо, което той често напомня на учениците си. „Ако установите, че проблемът е труден и сте заседнали, това означава, че проблемът е добър. Фан Чунг каза, че добрият проблем отвръща на удара. Не можете да очаквате той просто да се разкрие.“
Verstraete знае, че такава упорита решителност е добре възнаградена: „Получих обаждане от Фан и ми каза, че ми дължи 250 долара.“
…
