Václav Chvátal - Václav Chvátal

Václav Chvátal
Chvatal-kyoto2007-kostým-head.png
Václav Chvátal (2007)
narozený (1946-07-20) 20. července 1946 (věk 74)
Praha
Národnostkanadský, čeština
Alma materUniversity of Waterloo
Univerzita Karlova
OceněníCena Beale – Orchard-Hays (2000) [1]
Docteur Honoris Causa, Université de la Méditerranné (2003)
Cena Fredericka W. Lanchestera (2007) [2]
Cena teorie Johna von Neumanna (2015) [3]
Vědecká kariéra
PoleMatematika, Počítačová věda, Operační výzkum
InstituceConcordia University
Doktorský poradceCrispin Nash-Williams
DoktorandiDavid Avis (Stanford 1977)
Bruce Reed (McGill 1986)

Václav (Vašek) Chvátal (Čeština: [ˈVaːtslaf ˈxvaːtal] je emeritním profesorem na katedře výpočetní techniky a softwarového inženýrství na Concordia University v Montreal, Quebec, Kanada. K tématům publikoval rozsáhle v roce teorie grafů, kombinatorika, a kombinatorická optimalizace.

Životopis

Chvátal se narodil v roce Praha v roce 1946 vystudoval matematiku na Univerzita Karlova v Praze, kde studoval pod vedením Zdeňka Hedrlína.[4] Uprchl Československo v roce 1968, tři dny po Sovětská invaze,[5] a dokončil doktorát v matematice na University of Waterloo, pod dohledem Crispin St. J. A. Nash-Williams, na podzim roku 1970.[4][6] Následně zaujal pozice v McGill University (1971 a 1978-1986), Stanfordská Univerzita (1972 a 1974-1977) Université de Montréal (1972-1974 a 1977-1978) a Rutgersova univerzita (1986-2004) před návratem do Montrealu Canada Research Chair v kombinatorické optimalizaci [7][5]na Concordia (2004-2011) a Canada Research Chair v diskrétní matematice (2011–2014) až do svého odchodu do důchodu.

Výzkum

The Chvátalův graf

Chvátal se poprvé dozvěděl o teorii grafů v roce 1964, když našel knihu od Claude Berge v Plzeň knihkupectví [8] a hodně z jeho výzkumu zahrnuje teorii grafů:

  • Týkala se jeho první matematické publikace ve věku 19 let řízené grafy které nemohou být mapovány na sebe žádným netriviálním homomorfismus grafů [9]
  • Další grafově-teoretickým výsledkem Chvátala byla konstrukce nejmenší možné konstrukce z roku 1970 graf bez trojúhelníků to je 4-chromatický a 4-pravidelný, nyní známý jako Chvátalův graf.[4][10]
  • Papír z roku 1972 [11] týkající se Hamiltonovských cyklů s konektivitou a maximální nezávislá sada velikost grafu, získal Chvátal jeho Erdőovo číslo z 1. Konkrétně, pokud existuje s takový, že daný graf je s-připojen k vrcholu a nemás + 1) -vertexová nezávislá množina, graf musí být Hamiltonian. Avis a kol.[4] vyprávět příběh Chvátala a Erdős vypracování tohoto výsledku v průběhu dlouhého výletu a později poděkoval Louise Guy „za její vytrvalou jízdu“.
  • V článku z roku 1973[12] Chvátal představil koncept houževnatost grafu, míra připojení grafu která úzce souvisí s existencí Hamiltonovské cykly. Graf je t- pokud ano, pro každého k větší než 1, odstranění méně než tk vrcholy ponechává méně než k připojené komponenty ve zbývajícím podgrafu. Například v grafu s Hamiltonovským cyklem odstranění jakékoli neprázdné sady vrcholů rozděluje cyklus na maximálně tolik kusů, kolik je počet odstraněných vrcholů, takže Hamiltonovské grafy jsou těžké. Chvátal se domníval, že 3/2-tvrdé grafy a později 2-tvrdé grafy jsou vždy Hamiltonian; navzdory pozdějším výzkumníkům, kteří nalezli protiklady těchto domněnek, stále zůstává otevřené, zda je nějaká konstantní vazba na houževnatosti grafu dostatečná k zajištění Hamiltonicity.[13]

Některé z Chvátalových prací se týkají rodin setů nebo ekvivalentně hypergrafy, předmět již se vyskytující v jeho Ph.D. diplomovou práci, kde také studoval Ramseyova teorie.

  • V domněnce z roku 1972, kterou Erdős nazval „překvapivou“ a „krásnou“,[14] a to zůstane otevřené (s cenou 10 $, kterou Chvátal nabídl za své řešení) [15][16] navrhl, aby v jakékoli rodině sad uzavřených v rámci operace odběru podmnožiny, největší podrodinu protínající se párem lze vždy najít výběrem prvku jedné ze sad a ponecháním všech sad obsahujících tento prvek.
  • V roce 1979[17] prostudoval váženou verzi nastavit problém s krytem, a dokázal, že a chamtivý algoritmus poskytuje dobré aproximace k optimálnímu řešení, generalizující předchozí nevážené výsledky o David S. Johnson (J. Comp. Sys. Sci. 1974) a László Lovász (Diskrétní matematika, 1975).

Chvátal se nejprve začal zajímat lineární programování vlivem Jack Edmonds zatímco Chvátal studoval na Waterloo.[4] Rychle si uvědomil důležitost řezací roviny pro útok na kombinatorické optimalizační problémy, jako je výpočetní technika maximální počet nezávislých sad a zejména zavedl pojem důkaz roviny řezu.[18][19][20][21] Ve Stanfordu v 70. letech začal psát svou populární učebnici Lineární programování, který byl publikován v roce 1983.[4]

Řezací letadla leží v srdci větev a řez metoda používaná efektivními řešiteli pro problém obchodního cestujícího. V letech 1988 až 2005 pracoval tým David L. Applegate, Robert E. Bixby, Vašek Chvátal a William J. Cook vyvinul jeden takový řešič, Concorde.[22][23] Tým získal v roce 2000 cenu Beale-Orchard-Hays za vynikající výsledky ve výpočetním matematickém programování za desetistránkový článek [24] vyjmenoval některá zdokonalení Concordeovy metody odbočky a řezu, která vedla k řešení instance města 13 509, a v roce 2007 získala za svou knihu cenu Fredericka W. Lanchestera, Problém obchodního cestujícího: výpočetní studie.

Chvátal je také známý tím, že dokazuje věta o umělecké galerii,[25][26][27][28] pro výzkum digitální popisující sekvence,[29][30] za jeho práci s David Sankoff na Chvátal – Sankoffovy konstanty řízení chování nejdelší společný problém s posloupností na náhodných vstupech,[31] a za jeho práci s Endre Szemerédi v těžkých případech pro důkaz věty o rozlišení.[32]

Knihy

  • Vašek Chvátal (1983). Lineární programování. W.H. Freemane. ISBN  978-0-7167-1587-0.. Japonský překlad publikoval Keigaku Shuppan, Tokio, 1986.
  • C. Berge a V. Chvátal (eds.) (1984). Témata o dokonalých grafech. Elsevier. ISBN  978-0-444-86587-8.CS1 maint: další text: seznam autorů (odkaz)
  • David L. Applegate; Robert E. Bixby; Vašek Chvátal; William J. Cook (2007). Problém obchodního cestujícího: výpočetní studie. Princeton University Press. ISBN  978-0-691-12993-8.
  • Vašek Chvátal (ed.) (2011). Kombinatorická optimalizace: Metody a aplikace. IOS Press. ISBN  978-1-60750-717-8.CS1 maint: další text: seznam autorů (odkaz)

Reference

  1. ^ Minulí vítězové ceny Beale-Orchard-Hays.
  2. ^ Cena Fredericka W. Lanchestera 2007, vyvoláno 2017-03-19.
  3. ^ Cena John von Neumann Theory Prize 2015, vyvoláno 2017-03-19.
  4. ^ A b C d E F Avis, D.; Bondy, A .; Cook, W.; Reed, B. (2007). „Vasek Chvatal: Krátký úvod“ (PDF). Grafy a kombinatorika. 23: 41–66. CiteSeerX  10.1.1.127.5910. doi:10.1007 / s00373-007-0721-4.
  5. ^ A b Vasek Chvátal je ‚cestujícím profesorem ', Čtvrteční zpráva společnosti Concordia, 10. února 2005.
  6. ^ Projekt Matematická genealogie - Václav Chvátal
  7. ^ Vasek Chvatal oceněn Canada Research Chair, Čtvrteční zpráva společnosti Concordia, 23. října 2003.
  8. ^ Chvátal, Vašek (1997), „Na chválu Clauda Bergeho“, Diskrétní matematika, 165-166: 3–9, doi:10.1016 / s0012-365x (96) 00156-2,
  9. ^ Chvátal, Václav (1965), „Na konečných a spočetných rigidních grafech a turnajích“, Komentáře Mathematicae Universitatis Carolinae, 6: 429–438.
  10. ^ Weisstein, Eric W. "Chvátalův graf". MathWorld.
  11. ^ V. Chvátal; P. Erdős (1972), „Poznámka k hamiltonovským obvodům“ (PDF), Diskrétní matematika, 2 (2): 111–113, doi:10.1016 / 0012-365x (72) 90079-9,
  12. ^ Chvátal, V. (1973), „Tvrdé grafy a hamiltonovské obvody“, Diskrétní matematika, 5 (3): 215–228, doi:10.1016 / 0012-365x (73) 90138-6,
  13. ^ Lesniak, Linda, Chvátalův t0- důkladná domněnka (PDF)
  14. ^ Matematické recenze MR0369170
  15. ^ V. Chvátal; David A. Klarner; D.E. Knuth (1972), „Vybrané kombinatorické výzkumné problémy“ (PDF), Oddělení informatiky, Stanford University, Stan-CS-TR-72-292: Problém 25
  16. ^ Chvátal, Vašek, Domněnka v extremální kombinatorice
  17. ^ „Chamtivá heuristika pro problém pokrývající soubor“, Mathematics of Operations Research, 1979
  18. ^ Chvátal, Václav (1973), „Edmonds Polytopes and Slabě Hamiltonian Graphs“, Matematické programování, 5: 29–40, doi:10.1007 / BF01580109,
  19. ^ Chvátal, Václav (1973), „Edmonds Polytopes and a hierarchy of combineatorial problems“, Diskrétní matematika, 4 (4): 305–337, doi:10.1016 / 0012-365x (73) 90167-2,
  20. ^ Chvátal, Václav (1975), „Některé aspekty kombinatoriky s lineárním programováním“ (PDF), Congressus Numerantium, 13: 2–30,
  21. ^ Chvátal, V. (1975), „On certain polytopes associated with graphs“, Journal of Combinatorial Theory, Series B, 18 (2): 138–154, doi:10.1016/0095-8956(75)90041-6.
  22. ^ Matematický problém, dlouhý zmatek, pomalu výnosy. New York Times, 12. března 1991.
  23. ^ Umělecké trasy, Science News Online, 1. ledna 2005.
  24. ^ Applegate, David; Bixby, Robert; Chvátal, Vašek; Cook, William (1998), „K řešení problémů obchodního cestujícího“, Documenta Mathematica, Extra Volume ICM III
  25. ^ Weisstein, Eric W. „Věta umělecké galerie“. From MathWorld - A Wolfram Web Resource. http://mathworld.wolfram.com/ArtGalleryTheorem.html
  26. ^ Diagonals: Part I 4. Problémy s uměleckou galerií, Sloupec funkcí AMS od Josepha Malkevitche
  27. ^ Věta o umělecké galerii Chvatal v Alexander Bogomolny Cut the Knot
  28. ^ Posedlost, Numb3rs, epizoda 3, sezóna 2
  29. ^ Chvátal, Vašek (1993), „Poznámky k Kolakoskiho posloupnosti“, Technické zprávy DIMACS, TR: 93-84
  30. ^ Nebezpečné problémy, Science News Online, 13. července 2002.
  31. ^ Chvátal, Václav; Sankoff, David (1975), „Nejdelší společné posloupnosti dvou náhodných sekvencí“, Journal of Applied Probability, 12 (2): 306–315, doi:10.2307/3212444, JSTOR  3212444.
  32. ^ Chvátal, Vašek; Szemerédi, Endre (1988), „Mnoho tvrdých příkladů řešení“, Deník ACM, 35 (4): 759–768, doi:10.1145/48014.48016.

externí odkazy