Klaus Wagner

Klaus Wagner (dreapta) și Frank Harary în Oberwolfach în 1972.

Klaus Wagner ( Köln , 31 martie 1910 - 6 februarie 2000 ) a fost un matematician german , cunoscut pentru contribuțiile sale la teoria graficelor .

Biografie

Wagner a studiat topologia la Universitatea din Köln sub conducerea lui Karl Dorge, care la rândul său a fost un fost student al lui Issai Schur . În 1937 și-a luat doctoratul cu o disertație despre teorema curbei Jordan și teorema celor patru culori . După ce a predat câțiva ani la Köln ^[1] , în 1970 s-a mutat la Universitatea din Duisburg , unde a rămas până la pensionarea sa în 1978.

Teoria graficelor minore

Graficul Wagner, o scară Möbius cu opt vârfuri, generată de caracterizarea Wagner a graficelor minore.

K_{5}

{\ displaystyle K_ {5}}

{\ displaystyle K_ {5}}

( complet pe 5 vârfuri).

Wagner este cunoscut pentru contribuțiile sale la teoria graficelor și în special la teoria graficelor minore, care pot fi derivate dintr-un grafic mai mare prin contracție sau îndepărtare a muchiilor. Teorema lui Wagner caracterizează graficele plane ca acele grafice pentru care nu există nici un grafic minor minor, nici un grafic de tip $K_{5}$ ${\ displaystyle K_ {5}}$ ${\ displaystyle K_ {5}}$ (adică complet pe cinci vârfuri) și nici un grafic bipartit complet de tip $K_{3,3}$ ${\ displaystyle K_ {3,3}}$ ${\ displaystyle K_ {3,3}}$ (adică cu trei vârfuri pe fiecare parte a bipartiției sale).
. ^{[ neclar ]} Cu alte cuvinte, aceste două grafice sunt singurele grafice minore neplanare minore. Teorema lui Wagner este strâns legată, dar ar trebui distinsă, de teorema lui Kuratowski, conform căreia graficele plane sunt cele care nu conțin o partiție a $K_{5}$ ${\ displaystyle K_ {5}}$ ${\ displaystyle K_ {5}}$ tu urasti $K_{3,3}$ ${\ displaystyle K_ {3,3}}$ ${\ displaystyle K_ {3,3}}$ .

Un al doilea rezultat teoretic important, care este un corolar al teoremei lui Wagner, afirmă că un grafic conectat cu 4 vârf este plan dacă și numai dacă nu are un grafic minor de tip $K_{5}$ ${\ displaystyle K_ {5}}$ ${\ displaystyle K_ {5}}$ . Aceasta implică o caracterizare a graficelor fără minori $K_{5}$ ${\ displaystyle K_ {5}}$ ${\ displaystyle K_ {5}}$ , așa cum este construit din grafice plane și grafice Wagner (de exemplu, o scară Möbius cu opt vârfuri) „lipite” împreună cu o sumă de fisuri , o operație între grafice care implică lipirea subgrafelor până la trei vârfuri cu posibila îndepărtare a marginilor de la relativ fisuri. Această caracterizare a fost utilizată de Wagner pentru a demonstra că teorema celor patru culori este echivalentă cu un caz particular (pentru $k=5$ ${\ displaystyle k = 5}$ ${\ displaystyle k = 5}$ ) a conjecturii lui Hadwiger asupra numărului cromatic al unui $K_{k}$ ${\ displaystyle K_ {k}}$ ${\ displaystyle K_ {k}}$ -graf (de tip $K_{5}$ ${\ displaystyle K_ {5}}$ ${\ displaystyle K_ {5}}$ ) fără subgrafe minore. După această teoremă, caracterizările altor familii de grafuri în ceea ce privește sumele descompunerilor lor de clică au devenit standard în teoria graficelor minore.

În anii 1930, Wagner a conjecturat că în orice set infinit de grafice există cel puțin un grafic izomorf al graficului minor al unui alt element din set. Dacă această presupunere ar fi adevărată, acest lucru ar implica că orice operațiune închisă cu privire la operația de desenare a graficelor minore (cum ar fi graficele plane sunt de exemplu) poate fi caracterizată automat de mulți minori interzisi ^[2] într-un mod similar cu cel în care teorema lui Wagner caracterizează graficele plane.
Conjectura a fost făcută publică mult după ^[3] , până când matematicienii Neil Robertson și Paul Seymour au reușit să o demonstreze în 2004 cu ceea ce s-a numit Teorema Robertson-Seymour . ^[4]

Premii și recunoștințe

1990 : festschrift on theory graph ^[5] ;
2000 : festkollocviu postum la Universitatea din Köln .

Lucrări selectate

Wagner, K., Über eine Eigenschaft der ebenen Komplexe ^{[ link rupt ]} , în Mathematische Annalen , vol. 114, 1937, pp. 570–590, DOI : 10.1007 / BF01594196 .

Notă

^ Klaus Wagner , pe Math Genealogia Project .
^ În acest sens, puteți consulta intrarea Caracterizarea graficului interzis în Wikipedia engleză .
^ Bill Casselman,Variations on Graph Minor , American Mathematical Society.
^ Neil Robertson și Paul Seymour , Graph Minors XX: Wagner's Conjecture , în Journal of Combinatorial Theory, seria B , vol. 92, nr. 2, 2004, pp. 325–357, DOI : 10.1016 / j.jctb.2004.08.001 . .
^ Rainer Bodendieck (ed.), Contemporary Methods in Graph Theory: In honor of Prof. Dr. Klaus Wagner , Mannheim, Bibliographisches Institut, Wissenschaftsverlag, 1990, ISBN 978-3-411-14301-6 .

Bibliografie

(EN) Rudolf Halin , Probleme diverse pe grafice infinite în Teoria graficelor , vol. 35, nr. 2, Whiley, octombrie 2000, ISSN 0364-9024 ( WC ACNP ) ,OCLC 4640070745 . Găzduit pe archive.is . (doi: 10.1002 / 1097-0118 (200010) 35: 2 <128 :: AID-JGT6> 3.0.CO; 2-6)

Controlul autorității	VIAF (EN) 2555612 · ISNI (EN) 0000 0000 2791 580X · LCCN (EN) n85810995 · GND (DE) 118 770 713 · BNF (FR) cb123925925 (dată) · WorldCat Identities (EN) lccn-n85810995

Portal Biografii

Portalul de matematică

[1] Klaus Wagner , pe Math Genealogia Project .

[2] În acest sens, puteți consulta intrarea Caracterizarea graficului interzis în Wikipedia engleză .

[3] Bill Casselman,Variations on Graph Minor , American Mathematical Society.

[4] Neil Robertson și Paul Seymour , Graph Minors XX: Wagner's Conjecture , în Journal of Combinatorial Theory, seria B , vol. 92, nr. 2, 2004, pp. 325–357, DOI : 10.1016 / j.jctb.2004.08.001 . .

[5] Rainer Bodendieck (ed.), Contemporary Methods in Graph Theory: In honor of Prof. Dr. Klaus Wagner , Mannheim, Bibliographisches Institut, Wissenschaftsverlag, 1990, ISBN 978-3-411-14301-6 .

[1]

[2]

[3]

[4]

[5]