imported>Neutronstar2: /* Graphentheorie */

2023-06-28T12:01:49Z

Graphentheorie

Neue Seite

'''Das BUCH der Beweise''' ({{enS|Proofs from THE BOOK}}) ist ein Buch der [[Mathematiker]] [[Martin Aigner]] und [[Günter M. Ziegler]] und versteht sich als eine Sammlung besonders eleganter [[Beweis (Mathematik)|mathematischer Beweise]].
Es wurde erstmals 1998 auf Englisch und 2002 auf [[Deutsche Sprache|Deutsch]] herausgegeben sowie in weiteren Sprachen veröffentlicht.

Das Buch ist dem Mathematiker [[Paul Erdős]] gewidmet und der Titel bezieht sich auf eine Idee von Erdős, dass es perfekte Beweise zu mathematischen Sätzen gibt, seine [[Platonismus|platonische]] Auffassung der Mathematik deutlich machend:
{{Zitat|Text=Ich bin nicht qualifiziert zu sagen, ob Gott existiert oder nicht – ich bezweifle eher seine Existenz. Nichtsdestoweniger sage ich immer, dass der SF<ref>{{lang|en|''Supreme Fascist''|de=Oberster Faschist}} ist eine von Erdős gerne benutzte Bezeichnung für Gott.</ref> dieses transfinite Buch hat, das die besten Beweise aller mathematischen Sätze enthält, Beweise, die elegant und perfekt sind.|ref=<ref>Erdős, zitiert in Paul Hoffman: ''The man who only loved numbers.'' 1998, S. 27.</ref>}}

Erdős verwies in Vorträgen häufig scherzhaft auf „Das Buch“ (''The Book''), wobei eine der bekanntesten Aussagen ist, man brauche als Mathematiker zwar nicht an Gott zu glauben, jedoch sollte man an das Buch glauben ({{"|lang=en|You don’t have to believe in God, but you should believe in The Book}}).<ref>Aigner, Ziegler im Vorwort von ''Das Buch der Beweise.''</ref><ref>Paul Hoffman: ''The Man who only loved numbers.'' 1998, Kapitel 1 ''Straight from the Book.''</ref> Nach den Aussagen von Erdős’ engem Mitarbeiter [[Béla Bollobás]] nahm er die Idee allerdings nicht allzu ernst.<ref>{{"|lang=en|So he always used ‘The Book’ as a joke to enliven his lectures. It should not be taken seriously.}}<br />In: {{Webarchiv|url=http://www2.ims.nus.edu.sg/imprints/interviews/BelaBollobas.pdf |wayback=20120722072452 |text=''Béla Bollobás: Graphs Extremal and Random.'' }} Interview, Universität Singapur, 2007, PDF.</ref> Wenn er einem Mathematiker ein Kompliment für ein in seinen Augen besonders elegantes Theorem machen wollte, pflegte er zu sagen, der Beweis „würde geradeheraus aus dem Buch“ kommen ({{"|lang=en|It’s straight from the Book}}).<ref>Hoffman: ''The Man who only loved numbers.'' S. 26.</ref>

Erdős beteiligte sich noch mit Notizen und Vorschlägen an den Ausarbeitungen, verstarb aber noch vor der Veröffentlichung des Buches.<ref>Aigner, Ziegler, Vorwort zu ''Das Buch der Beweise.''</ref>

Die Autoren bemühten sich, nur Beweise zu wählen, die mit den Kenntnissen des Mathematik-Grundstudiums verständlich sind.

Das Buch behandelt die fünf Bereiche [[Zahlentheorie]], [[Geometrie]], [[Analysis]], [[Kombinatorik]] und [[Graphentheorie]] in 40 Kapiteln. Das [[Kusszahlenproblem]] (Problem der 13 Kugeln) wurde ab der zweiten Auflage weggelassen, da sich der Beweis, der einer Skizze von [[John Leech (Mathematiker)|John Leech]] von 1956 folgte und diese zu vervollständigen suchte, als unvollständig erwies und der Versuch seiner Ergänzung als zu umfangreich.

== Kapitel ==

=== Zahlentheorie ===
* Kapitel 1: Sechs Beweise für die Unendlichkeit der Primzahlen (neben [[Euklid]]s Beweis drei ''Folklore-Beweise'', ein Beweis von Erdős und [[Fürstenbergs Beweis der Unendlichkeit der Primzahlen]]).
* Kapitel 2: Das [[Bertrandsches Postulat|Bertrandsche Postulat]] (nach der ersten publizierten Arbeit von [[Paul Erdős]] 1932).<ref>Andere Beweise gaben [[Pafnuti Lwowitsch Tschebyschow|P. L. Tschebyschow]] und [[S. Ramanujan]].</ref>
* Kapitel 3: Der [[Satz von Erdős (Binomialkoeffizienten)|Satz von Erdős]] (1934) über die Darstellung von [[Binomialkoeffizient]]en als l-te Potenzen. Erdős leitet ihn aus einer Verschärfung des Bertrandschen Postulats durch [[James Joseph Sylvester]] ab.
* Kapitel 4: Der [[Zwei-Quadrate-Satz]] von [[Pierre de Fermat|Fermat]]: Jede Primzahl der Form 4n+1 ist als Summe zweier Quadrate natürlicher Zahlen darstellbar. Es werden der Beweis von [[Roger Heath-Brown]] (1984) (mit Verbesserung von [[Don Zagier]]) und der von [[Axel Thue]] (1902) vorgestellt. Einer der Beweise benutzt einen Spezialfall des [[Quadratisches Reziprozitätsgesetz|Quadratischen Reziprozitätsgesetzes]].
* Kapitel 5: Quadratisches Reziprozitätsgesetz, mit Beweisen nach dem dritten und sechsten Beweis des Satzes von [[Carl Friedrich Gauß]].
* Kapitel 6: Der [[Satz von Wedderburn]] (''Jeder endliche Schiefkörper ist kommutativ.'') mit dem Beweis von [[Ernst Witt]] (1931).
* Kapitel 7: Beweis der [[irrationale Zahl|Irrationalität]] von [[Kreiszahl|Pi]] (nach [[Ivan Niven]] 1947<ref>[[:Wikibooks:de:Formelsammlung Mathematik: Irrationalität und Transzendenz#Die Kreiszahl π ist irrational|Beweis auf Wikibooks]]. {{Literatur |Autor=Ivan Niven |Titel=A simple proof that π is irrational |Sammelwerk=Bulletin of the American Mathematical Society |Band=53 |Datum=1947 |Seiten=509 |Sprache=en |Online=[https://mathscinet.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=RT&pg7=ALLF&pg8=ET&review_format=html&s4=Niven&s5=Irrational&s6=&s7=&s8=All&sort=Newest&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=5&mx-pid=21013 MR0021013]}}</ref>) und einiger anderer Zahlen wie der [[Eulersche Zahl|Eulerschen Zahl]] und ihrer Potenzen (nach [[Joseph Liouville]], [[Charles Hermite]]).
* Kapitel 8: Beweise für [[Leonhard Euler|Eulers]] Satz ([[Basler Problem]]) <math>\zeta (2) = \sum_{n=1}^{\infty} \frac {1}{n^2} =\frac {\pi^2}{6}</math>. Unter anderem werden Beweise von [[Akiva Jaglom]] und [[Isaak Jaglom]], [[William LeVeque]], [[Frits Beukers]] (mit C. Kolb, E. Calabi) vorgestellt.<ref name=":0">In der vierten englischen Auflage, Springer Verlag 2009.</ref>

=== Geometrie ===
* Kapitel 9: [[Hilbertsche Probleme#Hilberts drittes Problem|Hilberts drittes Problem: Zerlegung von Polyedern]], nach den Verbesserungen und Vervollständigungen von [[Max Dehn]]s Beweis durch [[Hugo Hadwiger]], [[Weniamin Fjodorowitsch Kagan|Kagan]], [[Wladimir Grigorjewitsch Boltjanski|Boltjanski]] und andere.
* Kapitel 10: [[Satz von Sylvester-Gallai|Satz von Sylvester und Tibor Gallai]]: Für jede Anordnung von n Punkten in der Ebene, die nicht alle auf einer Geraden liegen, gibt es eine Gerade, die genau zwei der Punkte enthält. Gegeben wird der Beweis von L. M. Kelly, den [[Harold Scott MacDonald Coxeter|Coxeter]] 1948 veröffentlichte. Auch Verallgemeinerungen des Satzes von [[Nicolaas Govert de Bruijn]] und Erdős werden behandelt.
* Kapitel 11: eine von P. R. Scott 1970 ausgesprochene Vermutung, dass <math>n \geq 3</math> Punkte in der Ebene, die nicht alle auf einer Geraden liegen, mindestens n-1 Steigungen der durch je zwei Punkte verlaufenden Geraden haben. Präsentiert wird der Beweis von [[Eli Goodman]], [[Ricky Pollack]] und [[Peter Ungar]] (1982).
* Kapitel 12: Drei Anwendungen der [[Eulerscher Polyedersatz|Eulerschen Polyederformel]] (für die der Beweis [[Karl Georg Christian von Staudt|von Staudts]] präsentiert wird). Unter anderem wird ein weiterer Beweis des Satzes von Sylvester und Gallai daraus abgeleitet (nach [[Norman Steenrod]]) und ein Satz von [[Georg Pick (Mathematiker)|Georg Pick]] (1899): Jedes elementare Dreieck, das heißt mit Eckpunkten, die auf einem ganzzahligen Gitter liegen, das aber keine weiteren Gitterpunkte enthält, hat den Flächeninhalt <math>\tfrac 12</math>.
* Kapitel 13: Der [[Starrheitssatz von Cauchy|Starrheitssatz]] für dreidimensionale Polyeder von [[Augustin Louis Cauchy]], mit dem Beweis von Cauchy.
* Kapitel 14: Die Frage der maximalen Anzahl sich paarweise berührender d-dimensionaler Simplizes in d Dimensionen. Ergebnisse von [[Joseph Zaks]] und [[Micha Perles]] werden präsentiert.
* Kapitel 15: Eine Vermutung von Erdős (1950), dass jede Menge von mehr als <math>2^d</math> Punkten im d-dimensionalen euklidischen Raum mindestens einen Winkel zwischen den Verbindungslinien der Punkte liefert, der kein spitzer Winkel ist. Beweis von [[Ludwig Danzer]] und [[Branko Grünbaum]] (1962), wobei sie gleichzeitig eine erweiterte Vermutung von [[Victor Klee]] bewiesen.
* Kapitel 16: Die Widerlegung der [[Borsuk-Vermutung]] über die Zerlegung konvexer Mengen im d-dimensionalen Raum (zuerst durch [[Jeff Kahn]] und [[Gil Kalai]] 1994), mit dem Beweis von [[Noga Alon|A. Nilli]].<ref name=":0" />

=== Analysis ===
* Kapitel 17: Verschiedene Sätze der Mengenlehre, unter anderem [[Georg Cantor]]s Beweis (Diagonalargument) der Nichtabzählbarkeit der reellen Zahlen und ein Beweis des [[Satz von Schröder-Bernstein|Satzes von Schröder-Bernstein]] von [[Ernst Schröder (Mathematiker)|Ernst Schröder]] und [[Felix Bernstein]] nach [[Paul Cohen (Mathematiker)|Paul Cohen]]. Präsentiert wird auch ein elementarer Satz über Familien analytischer Funktionen von Wetzel (1962), dessen Lösung von der [[Kontinuumshypothese]] abhängt (Beweis von Erdős), und die Aufzählung der rationalen Zahlen nach [[John Williams Calkin]] und [[Herbert Wilf]].
* Kapitel 18: [[Cauchy-Schwarzsche Ungleichung]] und Ungleichung für das [[Harmonisches Mittel|harmonische]], [[Arithmetisches Mittel|arithmetische]] und [[Geometrisches Mittel|geometrische Mittel]] (Beweis von Cauchy und H. Alzer). Letztere Ungleichung wird auf den Satz von [[Edmond Laguerre|Laguerre]] über die Lage der Nullstellen von Polynomen (mit nur reellen Nullstellen) angewandt und auf einen [[Satz von Erdős-Gallai|Satz von Erdős und Gallai]], der diesen verallgemeinert (nach [[George Polya]] 1940), sowie auf einen Satz der Graphentheorie von [[Pál Turán]].
* Kapitel 19: [[Fundamentalsatz der Algebra]], präsentiert wird der Beweis nach einer Grundidee von [[d’Alembert]] (1746).
* Kapitel 20: Die Frage, ob man ein Quadrat in eine ungerade Anzahl Dreiecke gleicher Fläche zerlegen kann (siehe [[Zerlegung in flächengleiche Dreiecke]]).<ref>Die Zerlegung in eine gerade Anzahl ist trivial.</ref> Dies ist nicht möglich. Präsentiert wird der Beweis von [[Paul Monsky]],<ref>Monsky, in: ''American Mathematical Monthly.'' Bd. 77, 1970, S. 161.</ref> der einzige bisher bekannte Beweis. Er benutzt die [[Bewertungstheorie]].
* Kapitel 21: Ein Satz von [[George Polya]] (1928) über komplexe Polynome f n-ten Grades (mit führendem Koeffizienten 1). C sei die Menge, die von f auf den Kreis mit Radius 2 in der komplexen Ebene abgebildet wird, L eine beliebige Gerade in der komplexen Ebene. Dann ist die [[Orthogonalprojektion|orthogonale Projektion]] von C auf L maximal von der Länge 4. Polya führte den Beweis auf einen Satz von [[Pafnuti Lwowitsch Tschebyschow|Tschebyschow]] zurück.
* Kapitel 22: Beweis eines Lemmas von [[John Edensor Littlewood]] und [[Cyril Offord]] (1943, verbessert von Erdős) durch [[Daniel Kleitman]] (1970). Das Lemma macht Aussagen über die Anzahl der Punkte im Einheitskreis in der komplexen Ebene, die als Linearkombination von n Punkten vom Betrag größer oder gleich 1 mit Koeffizienten ±1 dargestellt werden können.
* Kapitel 23: [[Partialbruchzerlegung]] der [[Kotangens]]funktion, zuerst von Euler gegeben, mit dem Beweis von [[Gustav Herglotz]].
* Kapitel 24: Das [[Buffonsches Nadelproblem|Buffonsche Nadelproblem]], nach E. Barbier (1860).<ref name=":0" />

=== Kombinatorik ===
* Kapitel 25: [[Schubfachprinzip]] und [[doppeltes Abzählen]]. Unter anderem wird dort eine von Erdős Lieblingsfragen an angehende junge Mathematiker erwähnt, die er auch [[Lajos Pósa]] bei ihrer ersten Begegnung stellte. Als Anwendung des doppelten Abzählens wird [[Emanuel Sperner#Sätze|Sperners Lemma]] (von [[Emanuel Sperner]]) erwähnt, aus dem der [[Brouwerscher Fixpunktsatz|Brouwersche Fixpunktsatz]] abgeleitet wird.
* Kapitel 26: Zerlegung von Rechtecken in Rechtecke nach Max Dehn, Nicolaas Govert de Bruijn.
* Kapitel 27: Drei ''berühmte Beweise über endliche Mengen''. Der [[Emanuel Sperner#Sätze|Satz von Sperner]] (Beweis von David Lubell), der [[Satz von Erdős-Ko-Rado]] (nach [[Gyula Katona]]) und der [[Heiratssatz]] von Hall (nach T. E. Easterfield und [[Paul Halmos]] / H. Vaughan) aus der Kombinatorik.
* Kapitel 28: Analyse perfekter [[Mischen (Spielkarten)|Kartenmischungen]] (Riffle Shuffle, analysiert von Edgar Gilbert und [[Claude Shannon]] 1955) nach [[Persi Diaconis]] und [[David Aldous]] (1986). Präsentiert wird der Beweis im Buch für mindestens 12 Mischungen, Diaconis und Aldous bewiesen, dass sieben ausreichen (aber nicht weniger).
* Kapitel 29: Lemma von Gessel und Viennot ([[Ira Gessel]], [[Gerard Viennot]] 1985) in der abzählenden Kombinatorik, mit Anwendungen zum Beispiel auf Determinanten.<ref>Gefunden wurde es schon 1972 durch [[Bernt Lindström]], aber damals wenig beachtet.</ref>
* Kapitel 30: Die [[Cayley-Formel]] über die Anzahl beschrifteter Bäume ([[Arthur Cayley]] 1889). Es werden vier Beweise gegeben.
* Kapitel 31: Identitäten für Produkte unendlicher Reihen und Reihen mit Zerfällungen ([[Partitionsfunktion|Partitionen]]), wie sie zum Beispiel von Euler und Ramanujan behandelt wurden. Behandelt wird ein Bijektions-Beweis für eine Identität von Euler nach [[Doron Zeilberger]] und [[David Bressoud]].
* Kapitel 32: Vervollständigung von [[Lateinisches Quadrat|lateinischen Quadraten]]. Die Möglichkeit dazu wurde vermutet von [[Trevor Evans]] 1960, bewiesen von [[Bohdan Smetaniuk]] 1981.<ref name=":0" />

=== Graphentheorie ===
* Kapitel 33: Problem von [[Jeff Dinitz]] (1978) über Graphenfärbung, bewiesen von [[Fred Galvin]] 1995 nach Vorarbeit von Jeanette Janssen (1992). Ist es möglich, die Zellen eines n×n-Quadrats so zu färben, dass die Farben in jeder Reihe und Spalte verschieden sind? Dabei wird jeder Zelle eine Palette (Liste) von n Farben zugewiesen, die auch von Zelle zu Zelle verschieden sein kann. Galvin bewies, dass es möglich ist.
* Kapitel 34: Der [[Fünf-Farben-Satz]] mit Farblisten (wie im Dinitz-Problem) mit dem Beweis von [[Carsten Thomassen (Mathematiker)|Carsten Thomassen]] (1979).
* Kapitel 35: Das [[Problem der Museumswächter]] von Victor Klee, mit der Lösung von [[Vašek Chvátal]]: Bei n Wänden sind mindestens <math>\lfloor \frac {n}{3} \rfloor</math> Wachen nötig für die „schlechtestmögliche“ Anordnung der Wände.<ref>Chvatal, in: ''Journal of Combinatorial Theory.'' Bd. 18, 1975, S. 39.</ref>
* Kapitel 36: der Satz von Turan in der [[Extremale Graphentheorie|extremalen Graphentheorie]], für den fünf Beweise gegeben werden (unter anderem von Turan, Erdős).
* Kapitel 37: Berechnung der Kapazität von Kommunikationskanälen und Graphen nach [[Claude Shannon]] (mit einem Beweis von [[Laszlo Lovasz]]).
* Kapitel 38: Beweis der [[Topologische Kombinatorik|Vermutung]] von [[Martin Kneser]] (1955) über die [[Chromatische Zahl|Färbungszahl]] von Kneser-Graphen, für den nach dem Beweis von Laszlo Lovasz 1978 [[Imre Bárány]] und Joshua Greene (2002) vereinfachte Beweise gaben. Präsentiert wird der Beweis von Greene.
* Kapitel 39: Der Freundschaftssatz der Graphentheorie von Erdős, [[Alfred Renyi]] und [[Vera T. Sós]] (mit deren Beweis).
* Kapitel 40: Anwendungen der [[Probabilistische Methode|probabilistischen Methode]] in der Graphentheorie nach Erdős und [[Alfréd Rényi|Rényi]], zum Beispiel auf die Abschätzung von [[Ramsey-Zahl]]en.<ref name=":0" />

== Sonstiges ==
* Andere Mathematiker haben ihre eigenen Kandidaten veröffentlicht, zum Beispiel [[Sergei Tabachnikov]].<ref>Tabachnikov, Proofs (not) from the book, Mathematical Intelligencer, 2014, Nr. 2</ref>
* Der Zahlentheoretiker [[Godfrey Harold Hardy]] verfasste im Jahr 1940 den Essay „[[Apologie eines Mathematikers]]“, in dem er sich grundsätzlich mit der Frage nach der [[Ästhetik]] in der Mathematik auseinandersetzt und auch die Frage nach den „elegantesten Beweisen“ stellt.
* [[George Pólya]] wurde bekannt durch sein Buch „Vom Lösen mathematischer Probleme“ (egl. „How to solve it“), das zuerst 1945 bei Princeton University Press erschien, in 17 Sprachen übersetzt wurde und sich über eine Million Mal verkaufte.<ref>''Schule des Denkens. Vom Lösen mathematischer Probleme'' („How to solve it“). 4. Aufl. Francke Verlag, Tübingen 1995, ISBN 3-7720-0608-6 (Sammlung Dalp).
- Englische Ausgabe: ''How to solve it'', Princeton University Press 2004 (mit Vorwort von [[John Horton Conway]], erweiterte Ausgabe)</ref>
*[[David Hilbert]] stellte das Problem der Einfachheit von Beweisen, manchmal auch als [[Hilberts 24. Problem]] bezeichnet.

== Quellen und Weblinks ==
* ''Proofs from THE BOOK.'' Springer, Berlin 2014, ISBN 3-540-63698-6 (5. Auflage: ISBN 978-3-662-44205-0).
* ''Das BUCH der Beweise.'' Springer, Berlin 2014, ISBN 3-540-42535-7 (4. Auflage: ISBN 978-3-662-44456-6).
* [https://www.mi.fu-berlin.de/math/groups/discgeom/ziegler Günter M. Zieglers Homepage] mit einer [https://www.mi.fu-berlin.de/math/groups/discgeom/ziegler/Publikationen/index.html Liste der Auflagen und Sprachversionen.]
* [http://mathdl.maa.org/mathDL/19/?pa=reviews&sa=viewBook&bookId=68821 Review of Proofs from THE BOOK] von Mary Shepard, [[Mathematical Association of America]] (1999).
* [http://www.zeit.de/2002/25/Gottes_geheimes_Werk?page=all ''Gottes geheimes Werk.''] Bei: ''[[Die Zeit|Zeit.de.]]''
* Aigner, Ziegler: [https://www.mi.fu-berlin.de/math/groups/discgeom/ziegler/Preprintfiles/087PREPRINT.pdf?1397057419 ''Brillanten für das „Buch der Beweise“.''] PDF.

== Verweise ==
<references />

{{SORTIERUNG:Buch der Beweise #Das}}
[[Kategorie:Literarisches Werk]]
[[Kategorie:Literatur (Englisch)]]
[[Kategorie:Literatur (20. Jahrhundert)]]
[[Kategorie:Sachliteratur (Mathematik)]]
[[Kategorie:Beweis (Mathematik)]]
[[Kategorie:Paul Erdős]]

Das Buch der Beweise - Versionsgeschichte

imported>Neutronstar2: /* Graphentheorie */