След 90 години математици решиха най-известната задача на Рамзи

Ваня Милева Последна промяна на 27 ноември 2023 в 00:00 29209 0

Задачите на Рамзи, като r(4,5), са лесни за формулиране, но както е показано на този граф, възможните решения са почти безкрайни, което ги прави много трудни за решаване.

Кредит Jacques Verstraete / University of California, San Diego.

Задачите на Рамзи, като r(4,5), са лесни за формулиране, но както е показано на този граф, възможните решения са почти безкрайни, което ги прави много трудни за решаване.

Теорията на Рамзи е област от математиката, подкрепена от философията, че във всяка достатъчно голяма структура съществува относително голяма подредена подструктура.

Този клон на математиката е наречен на Франк Рамзи, но има корени в различни други математичвски области, включително логика, теория на множествата, топология, геометрия и теория на числата.

Двама математици от Калифорнийския университет в Сан Диего намериха отговора на r(4,t), дълго нерешена задача на Рамзи, която обърква света на математиката близо век.

Теорията на Рамзи се е превърнала в крайъгълен камък на съвременните комбинаторни изследвания, а централните стойности на изследване са известни като числа на Рамзи. По-подробно за задачата на Рамзи може да научите в статията "Числата на Рамзи: Какви гости да си поканим на парти".

Тази картина - математиците я наричат ​​граф - изглежда напълно хаотична. Със сигурност нямаме шестима приятели или шест непознати. Но все пак можем да попитаме: можем ли да намерим поне трима души в стаята, които са или приятели, или непознати? Казано по друг начин, можем ли да намерим син триъгълник (трима приятели) или червен триъгълник (трима непознати)? В този случай отговорът е "да". Чарли, Евелин и Фред са непознати един за друг. Но какво ще стане, ако оригиналният граф е бил различен? Винаги ли щяхме да можем да намерим подреден набор от трима души, дадени от монохроматичен триъгълник (всички в един цвят, от гръцки monos, „единичен“, и chroma , „цвят“)? Експериментирането с малко хартия и цветни моливи скоро ще ви убеди, че с шест души винаги има едноцветен триъгълник. Но как да докажем, че това е вярно? Един от начините би бил просто да изброим всички възможни оцветявания и да проверим всеки от тях. За съжаление има над 30 000 възможни оцветявания, така че това доказателство би било повече от досадно.

Класическият пример, който дава представа за задачата е твърдението, че парти от шестима души неизбежно ще има поне трима души, които всички се познават, или поне трима души, които не се познават. Това се изразява като r(3,3), като отговорът е 6.

"Това е факт от природата, абсолютна истина", казва Жак Верстраете (Jacques Verstraete), който заедно със Сам Матеус (Sam Mattheus) извършва новаторското откритие, което в момента се разглежда за публикуване от списанието Annals of Mathematics и може да се прочете в arXiv.

"Няма значение каква е ситуацията или кои шестима души ще изберете – ще намерите трима души, които помежду си се познават, или трима души, които не се познават. Може да успеете да намерите повече, но ви е гарантирано, че ще има поне три в едната или другата клика", обясняват математиците от Калифорнийския университет в Сан Диего Жак Верстраете и Сам Матеус в съобщение за пресата.

Оригиналната теория на Рамзи казва, че ако един граф е достатъчно голям – в математиката графът е набор от точки и линии между тези точки – можете да намерите ред сред целия този хаос.

Най-вече теоремата гласи, че набор от точки няма да има линии между тях или набор от точки с всички възможни линии между тях (известни още като клики). Това се изразява като r(s,t), където s означава "точки с линии" и t означава "точки без линии" (в графа горе те са обозначени като сини и червени).

Какво се случва, след като математиците установяват, че r(3,3) = 6?

Естествено, те решават да научат r(4,4), r(5,5) и r(4,t), където t броят на точките, които не са свързани, е променлива.

Може да видите как се доказва r(3,4) и r(4,4) в статията "Числата на Рамзи: Какви гости да си поканим на парти".

Решението на r(4,4) е 18 и това е доказано с помощта на теорема, създадена от Пол Ердос и Джордж Секереш през 30-те години на миналия век. В момента r(5,5) все още е неизвестно.

"Защо нещо толкова просто за формулиране е толкова трудно за решаване? Оказва се, че е по-сложно, отколкото изглежда", казват изследователите.

"Да приемем, че знаете, че решението на r(5,5) е някъде между 40-50. Ако започнете с 45 точки, ще има повече от 10 234 графа за разглеждане!"

Затова Жак Верстраете и Сам Матеус са намерили приблизително решение за r(4,t), където t означава, че "точки без линии" е променлива.

"Тъй като тези числа са изключително трудни за намиране, математиците търсят приблизителни оценки”, обяснява Верстраете в изявлението за пресата. "Това е, което Сам и аз постигнахме в нашата скорошна работа. Как да намерим не точния отговор, а най-добрите прогнози за това какви могат да бъдат тези числа на Рамзи?"

Тези задачи обикновено се решават с помощта на случайни графики, но този проблем на Рамзи изисква повече нестандартно мислене.

Използвайки концепция, наречена като псевдослучайни графи, Верстраете открива решение за r(3,t) през 2019 г.. Но техниката удря на камък, когато се приложи към прословутия сложен r(4,t) проблем, така че Верстраете се впуска в други области на математиката - по-специално, крайна геометрия (всяка геометрична система, която има само ограничен брой точки), за да разбере отговора.

Повече за границата  между някое огромно крайно число и следващото безкрайно голямо число може да научите в "Математици хвърлиха мост през пропастта между крайно и безкрайно".

Опирайки се на експертния опит на Матеус в тази област, изследователите откриват псевдограф в крайната геометрия, който може да помогне за решаването на r(4,t).

След една година фина настройка, в крайна сметка математиците разбират, че имат решение: r(4,t) е близо до кубична функция от t.

Ако искате парти, на което винаги ще има четирима души, които всички се познават, или t души, които не се познават, ще ви трябват приблизително t3 души.

И все пак не забравяйте, че това е приблизителна оценка, а не точен отговор. Но t3 е много близо до точния отговор.

Сега, след като е дал точна оценка, д-р Верстраете се надява, че техниката може да помогне за отварянето на нови математически граници, които все още чакат да бъдат изследвани.

"Наистина ни отне години, за да го разрешим", коментира д-р Верстраете. "И много пъти бяхме блокирани и се чудехме дали изобщо ще успеем да го разрешим."

"Но човек никога не трябва да се предава, независимо колко време отнема."

Справка: Sam Mattheus & Jacques Verstraete. 2023. The asymptotics of r(4,t). Annals of Mathematics, in press; arXiv: 2306.04007 https://arxiv.org/abs/2306.04007 

Източници: 

After 90 Years, Mathematicians Finally Solved the Most Notorious Ramsey, Popular mechanics

Mathematicians Solve Long-Standing Ramsey Problem, Sci.News

Най-важното
Всички новини
За писането на коментар е необходима регистрация.
Моля, регистрирайте се от TУК!
Ако вече имате регистрация, натиснете ТУК!

Няма коментари към тази новина !