Кіріспе
Американдық математик (1935–2020)
Рональд Льюис Грэм (31 қазан 1935 – 6 шілде 2020) – американдық математик, Америка математикалық қоғамы «соңғы жылдары дискретті математиканың әлемдегі қарқынды дамуының негізгі сәулетшілерінің бірі» деп бағалаған. Ол Америка математикалық қоғамы мен Америка математикалық қауымдастығының президенті болды, сонымен қатар өмірлік жетістіктері үшін Лерой П. Стил сыйлығымен марапатталды және Ұлттық ғылым академиясына сайланды. Калифорния университетінде (Беркли) аспирантураны бітіргеннен кейін Грэм көп жылдар бойы Белл зертханасында, содан кейін Калифорния университетінде (Сан-Диего) жұмыс істеді. Ол кестелеу теориясы, есептеу геометриясы, Рамсей теориясы және квази-рандомдық салаларында маңызды еңбектер жасады, математиканың көптеген салалары оның есімімен аталады. Ол алты кітап және 400-ге жуық мақала жариялады, 200-ге жуық автормен бірлесіп жұмыс істеді, оның ішінде әйелі Фан Чунг және Пол Эрдоспен жасаған ынтымақтастық еңбектері бар. Грэм «Риплидің сенесіз бе, жоқ па» атты басылымда «әлемдегі ең көрнекті математиктердің бірі» ғана емес, сонымен қатар шебер трамплинші және жонглер ретінде танымал болды. Ол Халықаралық жонглерлер қауымдастығының президенті қызметін атқарды. Оның әкесі мұнай өндіруші, кейін теңіз саудагері болған. Грэм гимнастикаға қызығушылық танытқанмен, ол бойы кішкентай және спортқа бейім емес еді. Ол Калифорния мен Джорджия арасында жиі көшіп өсті, мектепте бірнеше сыныптан өтті және ешбір мектепте бір жылдан артық оқыған жоқ. Кейін Калифорния университетіне (Сан-Диего, UCSD) Ирвин және Джоан Джейкобс атындағы Компьютерлік және ақпараттық ғылымдар профессоры ретінде көшті. UCSD-де ол Калифорния телекоммуникациялар және ақпараттық технологиялар институтының бас ғылымына тағайындалды. 2003–2004 жылдары Америка математикалық қауымдастығының президенті болды. 2020 жылдың 6 шілдесінде Калифорния штатының Ла-Холла қаласында 84 жасында дүние салды.
Үлестер
Грэхам математика мен теориялық компьютерлік ғылымның бірнеше саласына маңызды үлес қосты. Ол шамамен 400 мақала жариялады, олардың төрттен бірі Чунгпен бірлесіп жазылған, алты кітап, соның ішінде Дональд Кнут пен Орен Паташникпен бірлескен «Конкретті математика» кітабы. Ердос саны жобасы оның 200-ге жуық әріптес авторы болғанын көрсетеді. Ол тоғыз студенттің докторлық диссертациясын басқарды: біреуін Нью-Йорк қалалық университетінде, біреуін Ратгерс университетінде (Белл зертханасында жұмыс істеген кезінде) және жеті студенттің диссертациясын Сан-Диего университетінде басқарды.
Сандар теориясы
Грэхамның докторлық диссертациясы сандар теориясы саласындағы Египет бөлшектеріне арналған еді, сондай-ақ, бүтін сандарды шекті сандағы сыныптарға бөлгенде, осы сыныптардың біріндегі шекті подсыныптың өзара сандарының қосындысы бірге тең болатыны туралы Эрдёс-Грэхам мәселесі де қарастырылған. 2003 жылы Эрни Крот бұл мәселені шешіп дәлелдеді. Грэхамның Египет бөлшектері туралы тағы бір мақаласы 2015 жылы Стив Батлермен және (Эрдёс қаза болғаннан кейін шамамен 20 жыл өткен соң) Эрдёспен бірлесіп жарияланды; бұл Эрдёстің жарық көрген соңғы мақаласы болды, соның арқасында Батлер оның 512-ші серік авторы атанды. 1964 жылғы мақаласында Грэхам жай сандарсыз тізбектерді зерттеуді Фибоначчи сандарымен сияқты бірдей рекурсивті қатынас арқылы анықталатын, бірақ тізбектегі ешбір элементі жай сан емес, сандар тізбектерінің бар екенін байқау арқылы бастады. Мұндай тізбектерді құруға қатысты мәселені кейін Дональд Кнут және басқалар қолға алды. Грэхамның 1980 жылы Эрдёспен бірлесіп жазған «Комбинаторлық сандар теориясының ескі және жаңа нәтижелері» кітабы сандар теориясының кең ауқымды салаларынан ашық мәселелер жинағын ұсынады.
Рамзи теориясы
Рамзи теориясындағы Грэм-Ротшильд теоремасын Грэм мен Брюс Ротшильд 1971 жылы жариялаған. Бұл теорема сөздердің комбинаторикасындағы комбинаторлық кубтарға Рамзи теориясын қолданады. Грэм осы теореманың бір мысалы үшін үлкен санды жоғарғы шек ретінде келтірді, ол қазір Грэм саны деп аталады. Бұл сан бұрын Гиннес рекордтар кітабында математикалық дәлелдемелерде қолданылған ең үлкен сан ретінде тіркелген, бірақ содан бері TREE(3) сияқты одан да үлкен сандар оны басып озды. Грэм Рамзи теориясындағы тағы бір мәселе – Бульдік Пифагор үштіктерін шешкендерге ақшалай сыйлық ұсынды, және бұл сыйлық 2016 жылы табылды. Грэм сонымен қатар Рамзи теориясы бойынша екі кітап жариялады.
Граф теориясы
Грэм-Поллак теоремасы, Грэм Генри О. Поллакпен 1971 және 1972 жылдары екі мақалада жариялаған, егер n төбесі бар толық графтың қабырғалары толық екібөлімді кішіграфтарға бөлінсе, онда кем дегенде n-1 кішіграф қажет етеді деп тұжырымдайды. Грэм мен Поллак сызықтық алгебраны қолдана отырып қарапайым дәлел келтірді; мәлімдеменің комбинаторлық табиғатына және олардың жұмысынан кейін баламалы дәлелдердің көптеген жарияланымдарына қарамастан, барлық белгілі дәлелдер сызықтық алгебраны талап етеді. Эндрю Томассонның еңбегімен квази-кезекті графтарды зерттеу басталғаннан кейін, Грэм 1989 жылы Чунг пен Р.М. Уилсонмен бірлесіп "квази-кезекті графтардың негізгі теоремасы" деп аталатын нәтижені жариялады, ол осы графтардың көптеген әртүрлі анықтамалары эквивалентті екенін көрсетеді. Грэмнің пибблинг гипотезасы, Чунгтың 1989 жылғы мақаласында пайда болды, графтардың декарт көбейтінділерінің пибблинг санына қатысты. 2019 жылға дейін ол шешілмей қалды.
Қаптау, жоспарлау және шамалау алгоритмдері
Грэмнің жұмыс орындарындағы кестелеу жөніндегі алғашқы жұмысы ең нашар жағдайға шамалау коэффициентін шамалау алгоритмдерін зерттеуге енгізді және онлайн алгоритмдердің бәсекелестік талдауының кейінгі дамуының негізін қалады. Бұл жұмыс кейіннен Грэмнің кейіннен жан-жақты зерттеген контейнерлерді жинақтау теориясы үшін де маңызды екені анықталды. Грэм 1972 жылы Эдвард Г. Коффман кішімен бірлесіп жариялаған Coffman–Graham алгоритмі екі машинадағы кестелеу үшін оңтайлы алгоритмді және көптеген машиналар үшін кепілді шамалау алгоритмін ұсынады. Ол қабатты графиктерді салуда да қолданылады. 1979 жылы жарияланған кестелеу алгоритмдері туралы шолу мақаласында Грэм және оның әріптестері теориялық кестелеу мәселелерін жіктеу үшін үш таңбалы нотацияны енгізді: олардың жұмыс істейтін машиналар жүйесі, синхрондау немесе үзіліссіздік талаптары сияқты тапсырмалар мен ресурстардың ерекшеліктері және оңтайландырылатын өнімділік өлшемі. Бұл жіктелу кейде "Грэм нотациясы" немесе "Грэмнің нотациясы" деп аталады.
Дискрет және есептеу геометриясы
Грэхам сканерлеуі – екі өлшемді нүктелер жиынтығының дөңгелек қабығын табу үшін кеңінен қолданылатын және практикалық алгоритм. Ол нүктелерді сұрыптап, содан кейін оларды сұрыпталған тәртіппен қабыққа енгізуге негізделген. Грэхам бұл алгоритмді 1972 жылы жариялады. Ең үлкен кішкентай көпбұрыш мәселесі белгілі бір диаметр үшін ең үлкен ауданы бар көпбұрышты табуды сұрайды. Қызығы, Грэхам байқағандай, жауабы әрқашан дұрыс көпбұрыш бола бермейді. Грэхамның 1975 жылғы осы көпбұрыштардың пішіні туралы болжамы 2007 жылы расталды. 1975 жылғы тағы бір жарияланымда Грэхам мен Эрдос бірлік шаршыларды бүтін емес қабырғалары бар үлкен шаршыға орналастыру үшін, қабырғаларына параллель шаршыларды пайдаланудан айырмашылығы, үлкен шаршының қабырғасының ұзындығына қарағанда кішірек болатын ашық қалған аумақты қалдыру үшін көлбеу шаршыларды қолдануға болатынын көрсетті. Клаус Рот пен Боб Воган кейде ашық қалған аумақ қабырға ұзындығының квадрат түбіріне пропорционалды болуы мүмкін екенін дәлелдеді; ашық қалған аумақтың нақты шегін табу әлі де шешілмеген мәселе болып қала береді.
Жонглерлік
Грэхам 15 жасынан бастап дағдылы жонглер болды және ол алты шарға дейін жонглерлікпен айналысты. Ол сондай-ақ Комбинаторика және оның қолданбалары институтының Эйлер медалін алған екі алғашқы лауреатының бірі болды, екіншісі Клод Берге. Грэхам 1985 жылы Ұлттық ғылым академиясының мүшесі болып сайланды. 1999 жылы ол ACM Fellow атағын «алгоритмдерді талдаудағы маңызды үлесі үшін, әсіресе эвристиканың нашар жағдайларын талдау, жоспарлау теориясы және есептеу геометриясы» үшін алды. 2009 жылы ол Индустриялық және қолданбалы математика қоғамының мүшесі болды; мүшелік сыйлығы оның «дискретті математикаға және оның қолданбаларына қосқан үлесін» атап көрсетті. 2012 жылы ол Америка математикалық қоғамының мүшесі болды. Грэхам 1982 жылғы Халықаралық математиктер конгресінде (Варшавада 1983 жылы өткен) шақырылған баяндамашы болды және Франсис Яомен бірлесіп жазған «Есептеу геометриясымен жылдам саяхат» мақалы үшін Америка математикалық айлығында Лестер Р. Форд сыйлығын алды (1990). Оның Перси Диакониспен бірге жазған «Сиқырлы математика» кітабы Эйлер кітап сыйлығын жеңіп алды. Integers 2005 конференциясының материалдары Рон Грэмнің 70 жылдық мерейтойына арналған құрметті жинақ ретінде жарияланды. 2015 жылы Грэмнің 80 жылдық мерейтойына арналған конференция материалдары 2018 жылы «Дискретті математикадағы байланыстар: Рон Грэмнің еңбегіне арналған құрмет» деген атпен кітап ретінде жарық көрді.