フランク・ハラリー

フランク・ハラリー
フランク・ハラリー（左）とクラウス・ワーグナー、オーバーヴォルファッハにて、1972年
生まれる	( 1921-03-11 )1921年3月11日 ニューヨーク市、ニューヨーク州、米国
死亡	2005年1月4日(2005-01-04)（享年83歳） ラスクルーセス、ニューメキシコ州、米国
母校	ブルックリンカレッジ カリフォルニア大学バークレー校
知られている	ゴールドナー・ハラリーグラフ ハラリーの一般化された三目並べ
科学者としてのキャリア
フィールド	数学
機関	ミシガン大学 ニューメキシコ州立大学
博士課程の指導教員	アルフレッド・L・フォスター

フランク・ハラリ（1921年3月11日 - 2005年1月4日）は、グラフ理論を専門とするアメリカの数学者だった。彼は、現代グラフ理論の「父」の一人として広く認められている。^[1] ハラリは明快な説明の達人で、多くの博士課程の学生とともにグラフの用語を標準化した。彼はこの分野の範囲を物理学、心理学、社会学、さらには人類学にまで広げた。鋭いユーモアのセンスに恵まれたハラリは、数学の洗練度を問わず、あらゆるレベルの聴衆に挑戦し、楽しませた。彼が用いた特別なトリックは、定理をゲームにすることだった。たとえば、学生は6つの頂点を持つグラフに赤い辺を追加して赤い三角形を作ろうとし、別のグループの学生は辺を追加して青い三角形を作ろうとする（グラフの各辺は青か赤でなければならない）。友人と他人に関する定理のため、どちらかのチームが勝つことになる。

フランク・ハラリーは、シリアとロシアからのユダヤ人移民の家族の長男としてニューヨーク市で生まれました。 1941年にブルックリン大学で学士号を、1945年に修士号を取得し^[2]、 1948年にカリフォルニア大学バークレー校でアルフレッド・L・フォスターの指導のもと博士号を取得しました。

教職に就く前、彼はミシガン大学の社会調査研究所の研究助手になった。

ハラリの最初の論文「有限根号を持つブール型原子環」は、1950年にデューク数学ジャーナルに掲載されるまでに多大な労力を要した。この論文は1948年11月にアメリカ数学会に最初に提出され、その後デューク数学ジャーナルに送られ、3回の改訂を経て、最終的に最初の提出から2年後に出版された。^[要出典]ハラリは1953年にミシガン大学で教職を開始し、最初は助教授、1959年に准教授、1964年に数学教授に任命され、1986年までその職を務めた。

1987年より、ニューメキシコ州立大学ラスクルーセス校のコンピュータサイエンス学部の教授（および名誉教授）を務めた。また、Journal of Combinatorial TheoryとJournal of Graph Theoryの創刊者の一人でもある。^[1]

1949年、ハラリは『結び目の代数的構造について』を出版した。この出版の直後の1953年、ハラリはジョージ・ウーレンベックとの共著で初の著書『フシミの木の数について』を出版した。この本をきっかけに、ハラリはグラフ理論における自身の業績で世界的な名声を築き始めた。1965年に初の著書『構造モデル：有向グラフ理論入門』を出版し、その後の生涯にわたって、ハラリの関心はグラフ理論の分野に向けられることになった。

1965年頃にグラフ理論の研究を始めたハラリは、アナーバーで不動産を購入し、購入した家をアパートに分割し始めた。これは、メンテナンスの悪さや「多数の建築基準法違反」、所有する6つの建物の差し押さえなどに対する批判につながった。1969年の新聞記事では、ハラリは「土地の価値のためにこれらの不動産が欲しかっただけ...入居者を追い出したかった」と述べている一方、妻のジェーンは「貧しい黒人がより良い住宅を見つけるのを助けたかったが、何度も非難されてきた」と述べている。^{[3] [4]}ハラリと妻のジェーンには、ミリアム、ナタリー、ジュディス、トーマス、ジョエル、チャヤの6人の子供がいた。

1973年から2007年にかけて、ハラリはグラフ理論の分野でさらに5冊の本を共同執筆した。死去するまでの間、ハラリは世界中を旅し、数学雑誌やその他の科学出版物に800本以上の論文（約300人の共著者）を研究・発表した。これはポール・エルデシュに次ぐ数学者だった。ハラリは、米国内の166の都市と80か国以上の約274の都市で講義したと記録している。ハラリは特に、ドイツのザンテンを訪れた際に「X」を含むアルファベットのすべての文字で始まる世界中の都市で講義をしたことを誇りに思っていた。ハラリはまた、受賞歴のある映画「グッド・ウィル・ハンティング」で興味深い役を演じた。この映画では、彼が発表した、恐ろしく難しいとされる木の列挙に関する公式が紹介された。^[5]

ハラリーがミシガン大学の教授職を退いたのは、1986年、65歳の時でした。しかし、ハラリーは引退を軽く受け止めたわけではなく、引退後、ラスクルーセスにあるニューメキシコ州立大学のコンピュータサイエンスの特別教授に任命されました。彼は2005年に亡くなるまでこの職に就きました。引退と同年、ハラリーはインド国立科学アカデミーの名誉フェローに任命され、また、主にグラフ理論と組合せ理論に焦点を当てた約20の異なるジャーナルの編集者も務めました。ハラリーがカルカッタ数学会と南アフリカ数学会の名誉終身会員に選ばれたのは、引退後のことでした。

彼はニューメキシコ州ラスクルーセスのメモリアル医療センターで亡くなった。^[6]ラスクルーセスで彼が亡くなったとき、コンピュータサイエンス学部の他のメンバーは、かつて自分たちとともに働いていた偉大な頭脳を失ったことを悲しんだ。ハラリーの死去時にコンピュータサイエンス学部長を務めていたデシュ・ランジャンは、「ハラリー博士は真の学者であり、グラフ理論に対する純粋な愛情を持っていました。グラフ理論は、彼の人生の最後まで、彼にとって新しい発見、美しさ、好奇心、驚き、喜びの尽きない源でした。」と語った。

グラフ理論におけるハラリ氏の研究は多岐にわたります。彼が特に興味を持ったトピックには次のようなものがあります。

• グラフの列挙、つまり特定の種類のグラフを数えることです。^[7]彼はこのテーマに関する本を共著しました (Harary and Palmer 1973)。主な難しさは、同型の 2 つのグラフを 2 回カウントしてはならないことです。したがって、ポリアのグループ アクションによるカウント理論を適用する必要があります。Harary はこの分野の専門家でした。
• 符号付きグラフ。ハラリはグラフ理論のこの分野を発明した。^{[8] [9]}これは心理学者ドーウィン・カートライトとハラリが研究した理論的社会心理学の問題から生まれたものである。^[10]
• グラフ理論は多くの分野に応用されており、特にバランス理論、意見ダイナミクス、トーナメント理論などの社会科学に応用されています。^{[11]ハラリーはジョン・ワイリーの最初の}電子書籍『グラフ理論と地理学』の共著者でした。

ハラリが執筆した700本以上の学術論文のうち2本はポール・エルデシュとの共著であり、ハラリのエルデシュ数は1であった。^[12] 彼は頻繁に講演を行い、講演した都市のアルファベット順リストを作成していた。

ハラリーの最も有名な古典的著書『グラフ理論』は 1969 年に出版され、グラフ理論の分野への実践的な入門書となっています。この本や他の著書の中でハラリーが焦点を当てていたのは、グラフ理論を数学、物理学、その他多くの分野に多種多様に応用することであったことは明らかです。『グラフ理論』の序文から、ハラリーは次のように述べています...

「...グラフ理論は物理学、化学、コミュニケーション科学、コンピュータ技術、電気工学、土木工学、建築学、オペレーションズリサーチ、遺伝学、心理学、社会学、経済学、人類学、言語学のいくつかの分野に応用されています。」^[13]

ハラリはすぐにテキストを通じて探究型学習を推進し始め、それはムーア法の伝統に言及していることからも明らかです。ハラリはさまざまな研究分野を探求し、それらをグラフ理論に関連付けることに成功し、グラフ理論に多くの独自の貢献をしました。ハラリの古典的な著書「グラフ理論」は、読者に基本的なグラフに関する必要な知識の多くを提供することから始まり、次にグラフ理論に含まれるコンテンツの多様性を証明することにすぐに進みます。ハラリが著書でグラフ理論に直接関連付ける他の数学分野のいくつかは、第 13 章あたりから登場し始め、これらのトピックには線形代数や抽象代数が含まれます。

ハラリは社会学や行動経済学で用いられる社会的学習の理論にも大きな貢献をし、ジョン・R・P・フレンチの社会的権力モデルにおける合意形成の基準を導き出した。 ^[14]これは、特殊なケースではあるが、広く用いられているデグルート学習モデルを数十年も前から予見していた。

グラフ理論の研究の動機の1つは、ジェイコブ・L・モレノが記述したソシオグラムへの応用である。例えば、ソシオグラムの隣接行列はレオン・フェスティンガーによって使用された。^[15]フェスティンガーはグラフ理論のクリークを社会的クリークと同一視し、グループの隣接行列の立方体の対角線を調べてクリークを検出した。ハラリーはイアン・ロスと協力してフェスティンガーのクリーク検出を改良した。^[16]

隣接行列のべき乗を認めることで、ハラリーとロスは、木の隣接行列の2乗から完全グラフが得られることに気付きました。彼らはクリーク検出の研究に基づいて、隣接行列が木の隣接行列の2乗であるグラフのクラスを説明しました。^[17]

• グラフGが木の平方である場合、それは一意の木平方根を持つ。
• この証明とここで使用されている方法を理解するために必要ないくつかの語彙は、Harary のThe Square of a Treeに記載されています: (cliqual、unicliqual、multicliqual、cocliqual、neighborhood、neighborly、cut point、block)
• あるグラフ G が木の平方であるかどうかを判断する方法。

グラフGが完全であるか、または次の5つの特性を満たす場合、G = T ²

(i) G のすべての点は隣接しており、G は連結されている。

(ii) 2 つのクリークが 1 つの点 b でのみ出会う場合、それらのクリークと b および正確に 1 つの他の点を共有する 3 番目のクリークが存在します。

(iii) Gのクリークと多重クリーク点bの間には1対1の対応があり、bに対応するクリークC(b)には、bを含むクリークの数とまったく同じ数の多重クリーク点が含まれる。

(iv) 2つのクリークは2点以上で交差しない。

(v) 2点で交わるクリークのペアの数は、クリークの数より1少ない。

• グラフ G のツリー平方根を求めるアルゴリズム。

ステップ 1: G のすべてのクリークを検索します。

ステップ 2: G のクリークを C ₁、...、C _nとし、条件 iii に従ってこれらのクリークに対応する多重クリーク ポイント b ₁、...、b _{nのコレクションを検討します。このコレクションの要素は、T の非端点です。n 個のクリークのすべてのペアワイズ交差点を見つけ、対応するクリーク C i}と C _{j が}2 つの点で交差する場合に限り、ポイント b _iと b _{j を}線で結んでグラフ S を形成します。条件 v により、S はツリーになります。

ステップ 3: G の各クリーク C _{iについて、n i を}単一クリーク点の数とします。ステップ 2 で取得したツリー S に、n _{i 個の}エンドポイントを bi _iに接続して、目的のツリー T を取得します。

問題の木ができたら、木 T の隣接行列を作成し、それが実際に探していた木であるかどうかを確認できます。T の隣接行列を二乗すると、最初に使用したグラフ G と同型のグラフの隣接行列が得られます。おそらく、この定理の実際の動作を観察する最も簡単な方法は、Harary がThe Square of a Tree で言及しているケースを観察することです。具体的には、問題の例は、K ₅のグラフに対応する木を説明しています。

「1 つの点と他のすべての点を結合したツリーを考えてみましょう。ツリーを 2 乗すると、完全なグラフになります。説明したいのは... T ² K ₅${\displaystyle =}$です。」

前述のツリーの隣接行列を二乗すると、定理が実際に成り立つことがわかります。また、「1 つのポイントが他のすべてのポイントと結合される」ツリーを設定するこのパターンは、すべての完全グラフに対して常に正しいツリーを生成することもわかります。

• 1965年: (ロバート・Z・ノーマン、ドーウィン・カートライト共著)、構造モデル: 有向グラフ理論入門、ニューヨーク: Wiley MR 0184874
• 1967年: (編集者)グラフ理論と理論物理学、Academic Press MR 0232694
• 1969年：グラフ理論、アディソン・ウェズリー MR 0256911
• 1971年: (ハーバート・ウィルフとの共編)電気回路網解析の数学的側面、SIAM-AMS Proceedings、第3巻、アメリカ数学会 MR 0329788
• 1973: (編集者)グラフ理論の新しい方向性: 1971 年グラフ理論に関するアナーバー会議の議事録、ミシガン大学、アカデミック プレスMR 0340065
• 1973年: (Edgar M. Palmerと共著) Graphical Enumeration、Academic Press MR 0357214
• 1979年: (編集者)グラフ理論のトピック、ニューヨーク科学アカデミー MR 557879
• 1984年：（Per Hageとの共著）人類学における構造モデル、ケンブリッジ社会文化人類学研究、ケンブリッジ大学出版局 MR 0738630
• 1990年: (フレッド・バックリーと共著)グラフにおける距離、Perseus Press MR 1045632
• 1991年：（Per Hageとの共著）『オセアニアにおける交換：グラフ理論的分析』、オックスフォード社会文化人類学研究、オックスフォード大学出版局。
• 2002年: (Sandra Lach Arlinghaus および William C. Arlinghaus と共著) グラフ理論と地理学: インタラクティブ電子書籍、John Wiley and Sons MR 1936840
• 2007年：（Per Hageとの共著）『Island Networks: Communication, Kinship, and Classification Structures in Oceania（Structural Analysis in the Social Sciences）』、ケンブリッジ大学出版局。

• 数学系譜プロジェクトのフランク・ハラリー
• ニューメキシコ州立大学のフランク・ハラリー記念館