ロナルド・グラハム

ロナルド・ルイス・グラハム（1935年10月31日- 2020年7月6日）^{[ 1 ]}はアメリカの数学者で、アメリカ数学会から「近年の離散数学の世界的急速な発展の主要な立役者の一人」と評価されている^{[ 2 ]} 。 彼はアメリカ数学会とアメリカ数学協会の両方の会長を務め、生涯の功績に対するリロイ・P・スティール賞や全米科学アカデミーへの選出などの栄誉を受けた。 

カリフォルニア大学バークレー校で大学院課程を修了後、グラハムはベル研究所で長年勤務し、その後カリフォルニア大学サンディエゴ校に移った。彼はスケジューリング理論、計算幾何学、ラムゼー理論、準ランダム性^{[ 3 ]}において重要な業績を残し、数学の多くの分野が彼の名にちなんで名付けられている。彼は6冊の著書と約400本の論文を発表し、妻のファン・チャンやポール・エルデシュとの共同研究を含む約200人の共著者がいる。

グラハムは「世界有数の数学者の一人」であるだけでなく、熟練したトランポリン選手でありジャグラーでもあることから、リプリーの「信じようと信じまいと！」で取り上げられた。彼は国際ジャグラー協会の会長を務めた。^{[ 3 ] [ 4 ] [ 5 ]}

グラハムは1935年10月31日にカリフォルニア州タフトで生まれた。^{[ 6 ]}彼の父親は油田作業員で、後に商船員になった。グラハムは後に体操に興味を持つようになったが、小柄で運動神経は良くなかった。^{[ 7 ]}彼はカリフォルニアとジョージアの間を頻繁に引っ越しながら育ち、そのたびに何学年も飛び級し、どの学校にも1年以上通うことはなかった。^{[ 1 ] [ 7 ]} 10代の頃、彼は当時離婚していた母親とフロリダに移り住み、そこで高校に通ったが卒業はしなかった。代わりに、15歳でフォード財団の奨学金を得てシカゴ大学に入学し、そこで体操を学んだが数学の授業は受けなかった。^{[ 1 ]}

3年後、奨学金の期限が切れると、彼はカリフォルニア大学バークレー校に移り、正式には電気工学の学生として、DH レーマーの下で数論も研究し、^{[ 1 ]}カリフォルニア州トランポリンチャンピオンのタイトルを獲得した。^{[ 7 ]}彼は1955年に資格年齢に達したときにアメリカ空軍に入隊し、 ^{[ 8 ]}学位を取得せずにバークレーを去り、アラスカ州フェアバンクスに駐屯し、そこで1959年にアラスカ大学フェアバンクス校で物理学の学士号をようやく取得した。^{[ 1 ]}大学院研究のためにバークレーに戻り、1962年に数学の博士号を取得した。レーマーの指導を受けた彼の博士論文は「有理数の有限和について」であった。^{[ 9 ]}大学院生の頃、彼はサーカスでトランポリンのパフォーマンスをして生計を立て、^{[ 8 ]}バークレーの数学学部生だったナンシー・ヤングと結婚し、2人の子供をもうけた。^{[ 1 ]}

グラハムは博士号を取得後、1962年にベル研究所に就職し、その後、ニュージャージー州にあるAT&T研究所の情報科学部長に就任した。1963年、コロラド州の会議で、ハンガリーの数学者ポール・エルデシュ（1913年～1996年）^{[ 1 ]}と出会い、親しい友人となり、頻繁に共同研究を行った。当時すでに中年だったエルデシュに卓球で負けたグラハムは悔しがり、ニュージャージーに戻って卓球の腕を磨こうと決意し、最終的にはベル研究所のチャンピオンになり、州のタイトルも獲得した。 ^{[ 1 ]}グラハムは後に、数学者の共同研究ネットワークにおけるエルデシュからの距離の尺度であるエルデシュ数の概念を広めた。 ^{[ 10 ] [ 8 ]}エルデシュとの共著には、未解決問題集^{[B1] [B5]}とエルデシュの最後の死後論文^[A15]などがある。グラハムは1970年代に離婚し、1983年にベル研究所の同僚で共著者でもあるファン・チャンと結婚した。^{[ 1 ]}

ベル研究所に在籍中、グラハムは1986年にラトガース大学の数理科学教授の職にも就き、 1993年から1994年までアメリカ数学会の会長を務めた。1995年には研究所の主任科学者となった。 ^{[ 1 ]} 1999年に37年間勤めたA​​T&Tを退職し、^{[ 11 ]}カリフォルニア大学サンディエゴ校（UCSD）に移り、アーウィン・アンド・ジョーン・ジェイコブス記念コンピュータ・情報科学教授となった。^{[ 1 ] [ 8 ]} UCSDでは、カリフォルニア電気通信情報技術研究所の主任科学者にも就任した。^{[ 8 ] [ 5 ]} 2003年から2004年には、アメリカ数学協会の会長を務めた。^{[ 1 ]}

グラハムは2020年7月6日、カリフォルニア州ラホヤで気管支拡張症により84歳で亡くなった^{[ 12 ] 。 [ 6 ] [ 13 ]}

グラハムは、数学と理論計算機科学の複数の分野で重要な貢献をした。彼は約400の論文を発表し、そのうち4分の1はチャンとの共著である^{[ 14 ]} 。また、ドナルド・クヌースとオレン・パタシュニクとの共著『Concrete Mathematics』を含む6冊の著書を出版している^[B4]。エルデシュ数プロジェクトでは、彼の共著者は200人近くに上るとされている^{[ 15 ]} 。彼は、ベル研究所に在籍していたときにニューヨーク市立大学とラトガース大学でそれぞれ1人ずつ、そしてカリフォルニア大学サンディエゴ校で7人の博士課程学生の指導を行った^{[ 9 ] 。}

グラハムにちなんで名付けられた数学の注目すべきトピックには、エジプト分数に関するエルデシュ・グラハム問題、パラメータ語のラムゼー理論におけるグラハム・ロスチャイルド定理とそこから導出されるグラハム数、グラフ理論におけるグラハム・ポラック定理とグラハムのペブリング予想、近似スケジューリングとグラフ描画のためのコフマン・グラハムアルゴリズム、凸包のためのグラハムスキャンアルゴリズムなどがある。彼はまた、素数を含まない数列、ブールピタゴラス三つ組問題、最大の小さな多角形、正方形への正方形の詰め込みなどの研究も始めた。

グラハムは、メンバーの頭文字をとって名付けられた匿名の数学者グループGW Peckの出版物の寄稿者の1人であり、グラハムは「G」であった。 ^{[ 16 ]}グラハムはまた、トム・オッダという匿名でエルデシュ数に関する論文も執筆した。^{[ 17 ] [ 18 ]}

グラフ理論

グラハムがヘンリー・O・ポラックと共同で1971年と1972年に発表した2つの論文^{[A71b] [A72a]}は、${\displaystyle n}$-頂点完全グラフが完全二部グラフに分割されると、少なくとも${\displaystyle n-1}$部分グラフが必要です。グラハムとポラックは線形代数を用いた簡単な証明を提供しました。この命題の組み合わせ論的な性質や、彼らの研究以降に複数の代替証明が発表されているにもかかわらず、既知の証明はすべて線形代数を必要とします。^{[ 25 ]}

準ランダムグラフの研究がアンドリュー・トマソンの研究で始まって間もなく、グラハムは1989年にチャンとRMウィルソンと共に、これらのグラフの多くの異なる定義が同等であると述べる「準ランダムグラフの基本定理」と呼ばれる結果を発表した。^{[A89a] [ 26 ]}

1989年にChungによって発表された論文^{[ 27 ]}に登場したGrahamのペブリング予想は、グラフのデカルト積のペブリング数に関する未解決問題である^{[ 28 ]}。

離散幾何学と計算幾何学

グラハムスキャンは、2次元点集合の凸包を求めるための広く用いられている実用的なアルゴリズムであり、点をソートしてから、ソートされた順序で凸包に挿入することに基づいています。^{[ 33 ]}グラハムはこのアルゴリズムを1972年に発表しました。^[A72c]

最大の小さな多角形問題は、与えられた直径に対して最大の面積を持つ多角形を求める問題です。驚くべきことに、グラハムが指摘したように、答えは必ずしも正多角形ではありません。^[A75a]グラハムが1975年に提唱したこれらの多角形の形状に関する予想は、2007年にようやく証明されました。^{[ 34 ]}

1975年の別の出版物で、グラハムとエルデシュは、非整数辺長のより大きな正方形に単位正方形を詰め込む場合、軸に沿った正方形による明らかな詰め込みとは異なり、傾斜した正方形を使用することで、より大きな正方形の辺長に対して線形未満の未被覆領域を残すことができることを指摘した。 ^[A75b]クラウス・ロスとボブ・ヴォーンは、少なくとも辺長の平方根に比例する未被覆領域が必要になる場合があることを証明したが、未被覆領域の厳密な上限を証明することは未解決問題のままである。^{[ 35 ]}

ジャグリング

グラハムは15歳からジャグラーとして腕を磨き、最大6個のボールをジャグリングする練習をしていた。^{[ 4 ]}（掲載された写真には彼が12個のボールをジャグリングしている姿が写っているが、^{[ 5 ]}これは加工された画像である。^{[ 3 ]}）彼は国際ジャグラー協会選手権で何度も優勝したスティーブ・ミルズにジャグリングを教え、ミルズとの活動はミルズがミルズ・メス・ジャグリング・パターンを開発するきっかけとなった。また、グラハムはサイトスワップに関する一連の出版物を含め、ジャグリングの理論に大きく貢献した。1972年には国際ジャグラー協会の会長に選出された。^{[ 4 ]}

2003年、グラハムはアメリカ数学会の生涯功労賞であるリロイ・P・スティール賞を受賞した。この賞は、離散数学への貢献、講演や著作を通じた数学の普及、ベル研究所でのリーダーシップ、そして同協会の会長としての功績を称えたものである。^{[ 2 ]}彼は産業応用数学会のジョージ・ポリア賞の初代受賞者5人のうちの1人で、ラムゼー理論の仲間であるクラウス・リープ、ブルース・ロスチャイルド、アルフレッド・ヘイルズ、ロバート・I・ジュエットと共同受賞した。^{[ 38 ]}また、組合せ論とその応用研究所のオイラー・メダルの初代受賞者2人のうちの1人でもあり、もう1人はクロード・ベルジュであった。^{[ 39 ]}

グラハムは1985年に米国科学アカデミーに選出された。^{[ 40 ]} 1999年には「アルゴリズムの解析、特にヒューリスティクスの最悪ケース解析、スケジューリング理論、計算幾何学への先駆的な貢献」によりACMフェローに選出された。 ^{[ 41 ]} 2009年には産業応用数学会のフェローとなり、フェロー賞では「離散数学とその応用への貢献」が挙げられた。^{[ 42 ]} 2012年には米国数学会のフェローとなった。^{[ 43 ]}

^{グラハムは、} 1982年の国際数学者会議（1983年にワルシャワで開催）に招待講演者として招かれ、 「ラムゼー理論の最近の発展」について講演した。^{[ 13 ]}彼は2001年と2015年に2度、ジョサイア・ウィラード・ギブス記念講演者となった。 ^{[ 13 ]}アメリカ数学協会は、 チャンとマーティン・ガードナーとの共著論文「チェッカーボード上のシュタイナー木」（ Mathematics Magazine、1989年）でカール・アレンデルファー賞を、 ^{[A89b] [ 44 ]}フランシス・ヤオとの共著論文「計算幾何学の旋風ツアー」 （ American Mathematical Monthly、1990年）でレスター・R・フォード賞を授与した。 ^{[A90] [ 45 ]}パーシー・ディアコニスとの共著『魔法の数学』 ^[B6]はオイラー書籍賞を受賞した。^{[ 46 ]}

Integers 2005会議の議事録は、ロン・グラハムの 70 歳の誕生日を記念した記念論文集として出版された。 ^{[ 47 ]} 2015 年にグラハムの 80 歳の誕生日を記念して開催された会議から生まれた別の記念論文集は、2018 年に『Connections in discrete mathematics: a celebration of the work of Ron Graham』という本として出版された。^{[ 48 ]}

• グラハム氏のUCSD教員研究プロフィール
• ロン・グラハムの論文集–ロン・グラハムが執筆した論文の包括的なアーカイブ 
• ロン・グラハムについて–グラハムの生涯と数学に関するいくつかの側面をまとめたページ–ファン・チャン氏のウェブサイトの一部  
• 「サイモンズ財団：ロナルド・グラハム（1935年～2020年）」。サイモンズ財団。2016年1月11日。– 長尺のビデオインタビュー。
• 「2020年に亡くなった3人の数学者：ジョン・コンウェイ、ロナルド・グラハム、フリーマン・ダイソンは皆、その知性で世界を探求した」ダン・ロックモア（2020年12月31日）ニューヨーカー。
• Buhler, Joe; Butler, Steve; Spencer, Joel (2021年12月). 「ロナルド・ルイス・グラハム (1935–2020)」(PDF) .アメリカ数学会報. 68 (11): 1931– 1950. doi : 10.1090/noti2382 .
• Google Scholarに索引付けされているロナルド・グラハムの出版物