ヴァーツラフ・フヴァータル

ヴァーツラフ（ヴァシェク）・フヴァータル（チェコ語: [ ˈvaːtslaf ˈxvaːtal ] ）は、カナダ、ケベック州モントリオールのコンコルディア大学コンピュータ科学・ソフトウェア工学科の名誉教授であり、プラハのチャールズ大学の客員教授でもある。彼はグラフ理論、組み合わせ論、組み合わせ最適化の分野で数多くの論文を発表している。

フヴァータルは1946年にプラハで生まれ、プラハのカレル大学で数学の教育を受け、ズデニェク・ヘドルリンの指導の下で学んだ。^{[ 4 ]}彼は1968年、ソ連の侵攻から3日後にチェコスロバキアから脱出し、^{[ 5 ]}博士号を取得した。1970 年秋、クリスピン・セントの指導の下、ウォータールー大学で数学の学位を取得。JAナッシュ＝ウィリアムズ。 ^{[ 4 ] [ 6 ]}その後、マギル大学(1971 年および 1978 年～1986 年)、スタンフォード大学(1972 年および 1974 年～1977 年)、モントリオール大学 ( 1972 年～1974 年および 1977 年～1978 年)、ラトガース大学(1986 年～2004 年) で職に就き、その後モントリオールに戻り、コンコルディア大学 で組み合わせ最適化のカナダ研究講座^{[ 7 ] [ 5 ]} (2004 年～2011 年)、離散数学のカナダ研究講座(2011 年～2014 年) を務め、退職した。

フヴァータルは1964年にプルゼニの書店でクロード・ベルジュの本を見つけたことで初めてグラフ理論を知り^{[ 8 ]}、彼の研究の多くはグラフ理論に関係している。

• 彼が19歳の時に発表した最初の数学論文は、自明でないグラフ準同型写像によって自身に写像できない有向グラフに関するものであった^{[ 9 ]。}
• Chvátal のもう一つのグラフ理論的な成果は、1970 年に4彩色かつ 4正則である最小の三角形を含まないグラフを構成したことであり、これは現在Chvátal グラフとして知られています。^{[ 4 ] [ 10 ]}
• 1972年の論文^{[ 11 ]}は、ハミルトン閉路とグラフの連結性および最大独立集合サイズとの関係を示し、ChvátalはErdős数1を獲得した。具体的には、与えられたグラフがs頂点連結であり、( s + 1)頂点独立集合を持たないようなsが存在する場合、そのグラフはハミルトングラフでなければならない。Avisら^{[ 4 ]は}、ChvátalとErdősが長距離ドライブ中にこの結果を導き出し、後にLouise Guyに「安定した運転」に対して感謝したという話を語っている。  
• 1973年の論文^{[ 12 ]}で、Chvátalはグラフのタフネスという概念を導入しました。これは、ハミルトン閉路の存在と密接に関係するグラフの連結性の尺度です。グラフは、1より大きい任意のkに対して、tk個未満の頂点を除去しても、残りの部分グラフにk個未満の連結成分が残る場合、t-タフであると言います。たとえば、ハミルトン閉路を持つグラフでは、任意の空でない頂点の集合を除去すると、閉路は除去された頂点の数と同じ数以下の断片に分割されるため、ハミルトングラフは1-タフです。Chvátalは、3/2-タフグラフ、そして後に2-タフグラフは常にハミルトンであると予想しました。後の研究者がこれらの予想に対する反例を発見したにもかかわらず、グラフのタフネスに何らかの定数上限があればハミルトン性が保証されるかどうかは未解決のままです。^{[ 13 ]}

チャヴァタルの研究の一部は、集合の族、あるいは同等のハイパーグラフに関するものであり、これは彼がラムゼー理論も研究した博士論文にも既に登場するテーマである。

• エルデシュが「驚くべき」「美しい」と呼んだ1972年の予想^{[ 14 ]}（現在も未解決で、その解決に対してChvátalが10ドルの賞金を提供している）^{[ 15 ] [ 16 ]}では、部分集合を取る操作で閉じている任意の集合族において、ペアワイズ交差する最大の部分族は、いずれかの集合の要素を選択し、その要素を含むすべての集合を保持することによって常に見つけることができると提案した。
• 1979年、^{[ 17 ]}彼は重み付き集合被覆問題を研究し、貪欲アルゴリズムが最適解の良い近似値を提供することを証明し、 David S. Johnson (J. Comp. Sys. Sci. 1974) とLászló Lovász (Discrete Math. 1975) による以前の重みなし結果を一般化した。

チャヴァタルは、ウォータールー大学の学生だった頃、ジャック・エドモンズの影響で線形計画法に初めて興味を持つようになった。 ^{[ 4 ]}彼は、最大独立集合の計算などの組み合わせ最適化問題を解く上で切断平面が重要であることをすぐに認識し、特に切断平面証明の概念を導入した。^{[ 18 ] [ 19 ] [ 20 ] [ 21 ]} 1970年代にスタンフォード大学で、彼は人気の教科書『線形計画法』の執筆を開始し、1983年に出版した。^{[ 4 ]}

切断平面は、巡回セールスマン問題の効率的な解法で使用される分岐限定法の中心をなすものです。1988年から2005年にかけて、 David L. Applegate、Robert E. Bixby、Vašek Chvátal、William J. Cookのチームは、そのような解法の一つであるConcordeを開発しました。^{[ 22 ] [ 23 ]}このチームは、13,509都市のインスタンスの解法につながる分岐限定法のConcordeの改良点を列挙した10ページの論文[25]で、2000年に^{計算数学プログラミングの}優秀賞であるBeale-Orchard-Hays賞を受賞し[24]、^2007年には著書『巡回セールスマン問題：計算による研究』でFrederick W. Lanchester賞を受賞しました。

Chvátal は、美術館定理の証明^{[ 26 ] [ 27 ] [ 28 ] [ 29 ]}、自己記述デジタル シーケンスの研究^{[ 30 ] [ 31 ]} 、ランダム入力における最長共通部分列問題の挙動を制御するChvátal–Sankoff 定数に関するDavid Sankoffとの共同研究^{[ 32 ]} 、および分解定理証明の困難なインスタンスに関するEndre Szemerédiとの共同研究^{[ 33 ]}でも知られています。

• ヴァシェク・チュヴァータル (1983)。線形計画法。 WHフリーマン。ISBN 978-0-7167-1587-0。。日本語訳は啓学出版社、東京、1986年に出版。
• クロード・ベルジュ。ヴァシェク・チュヴァータル編。 （1984年）。パーフェクト グラフに関するトピック。アムステルダム;ニューヨーク : ニューヨーク : エルゼビア ノースホランド。ISBN 978-0-444-86587-8。
• デビッド・L・アップルゲイト;ロバート・E・ビクスビー;ヴァシェク・チュヴァータル。ウィリアム J. クック(2007)。巡回セールスマン問題: 計算による研究。プリンストン大学出版局。ISBN 978-0-691-12993-8。^{[ 34 ]}
• Vašek Chvátal 編 (2011).組み合わせ最適化: 方法と応用. IOS Press. ISBN 978-1-60750-717-82017年3月21日にオリジナルからアーカイブされました。 2017年3月22日に取得。
• ヴァシェク・チュヴァータル（2021）。パウル・エルデシュの離散数学的魅力。簡単な紹介。ケンブリッジ大学出版局。ISBN 978-1-108-92740-6。

• ウォータールー大学の関係者一覧

• Chvátal の Web サイト(encs.concordia.ca)