Хватал, Вацлав

Хватал родился в Праге в 1946 году и получил математическое образование в Карловом университете в Праге, где он учился под руководством Зденека Хедрлина. Он бежал из Чехословакии в 1968 году, через три дня после советского вторжения, и защитил докторскую диссертацию. Осенью 1970 года получил степень магистра математики в Университете Ватерлоо под руководством Криспина Сент-Дж. А. Нэш-Уильямса. Впоследствии он занимал должности в Университете Макгилла (1971 и 1978-1986 гг.), Стэнфордском университете (1972 и 1974-1977 гг.)), Монреальского университета (1972-1974 гг. и 1977-1978 гг.) и Университета Рутгерса (1986-2004 гг.), прежде чем вернуться в Монреаль на кафедру канадских исследований комбинаторной оптимизации в Конкордии (2004-2011 гг.) и Канадскую кафедру дискретных исследований математики (2011-2014 гг.) до пенсии.

Хваталь впервые узнал о теории графов в 1964 году, когда нашел книгу Клода Берже в книжном магазине города Пльзень, и большая часть его исследований связана с теорией графов:

• Его первая математическая публикация в возрасте 19 лет касалась ориентированных графов, которые не могут быть отображены на самих себя никаким нетривиальным гомоморфизмом графов.

• Другим теоретико-графическим результатом Хватала было построение в 1970 году минимально возможного графа без треугольников, который является как 4-хроматическим, так и 4-регулярным графом, теперь известным как граф Хватала.

• В статье 1972 года, связывающей гамильтоновы циклы со связностью и максимальным размером независимого множества графа, Хваталю присвоено число Эрдеша 1. В частности, если существует такое s, что данный граф является s-вершинно-связным и не имеет (s + 1) -вершинно-независимое множество, граф должен быть гамильтоновым. Avis et al. Расскажит историю о том, как Хватал и Эрдёш достигли этого результата в ходе долгой поездки, а затем поблагодарили Луизу Гай «за её стабильное вождение».

• В статье 1973 года Хватал ввел понятие устойчивости графа, меру связности графа, которая тесно связана с существованием гамильтоновых циклов. Граф является t- жестким, если для каждого k больше 1 удаление менее чем tk вершин оставляет менее k компонент связности в оставшемся подграфе. Например, в графе с гамильтоновым циклом удаление любого непустого множества вершин разбивает цикл не более чем на столько частей, сколько удаленных вершин, поэтому гамильтоновы графы 1- жесткие. Хваталь предположил, что 3/2- жесткие графы, а позже и 2- жесткие графы, всегда гамильтоновы; несмотря на то, что более поздние исследователи нашли контрпримеры этим гипотезам, остается открытым вопрос о том, достаточно ли некоторой постоянной оценки устойчивости графа, чтобы гарантировать гамильтоничность.

Некоторые работы Хватала касаются семейств множеств или, что то же самое, гиперграфов, тема уже упоминалась в его докторской диссертации, диссертацию, где он также изучал теорию Рамсея.

• Vašek Chvátal (1983). Linear Programming. W.H. Freeman. ISBN 978-0-7167-1587-0.. Japanese translation published by Keigaku Shuppan, Tokyo, 1986.
• C. Berge and V. Chvátal (eds.) (1984). Topics on Perfect Graphs. Elsevier. ISBN 978-0-444-86587-8.
• David L. Applegate; Robert E. Bixby; Vašek Chvátal; William J. Cook (2007). The Traveling Salesman Problem: A Computational Study. Princeton University Press. ISBN 978-0-691-12993-8.
• Vašek Chvátal (ed.) (2011). Combinatorial Optimization: Methods and Applications. IOS Press. ISBN 978-1-60750-717-8.
• Vašek Chvátal (2021). Discrete Mathematical Charms of Paul Erdős. A Simple Introduction. Cambridge University Press. ISBN 978-1-108-92740-6.

• Домашняя страница Chvátal