Unendlicher Graph

Als unendlichen Graph bezeichnet man in der Graphentheorie einen Graphen, dessen Knoten- oder Kantenzahl unendlich ist. Spricht man hingegen von einem Graphen so wird oft angenommen, dass Knoten- und Kantenzahl endlich sind. Ein Graph wird als wegendlich bezeichnet, falls er, trotz möglicherweise unendlich vieler Knoten, keinen unendlich langen Weg besitzt.

Aussagen über unendliche Graphen lassen sich häufig mittels eines Kompaktheitsarguments aus entsprechenden Aussagen über endliche Graphen ableiten. Beispielsweise ist jeder unendliche planare Graph vierfärbbar, weil dies für jeden endlichen planaren Graphen gilt. Dies beruht auf dem Lemma von König.

Andere Aussagen sind nicht zwangsläufig auf unendliche Graphen übertragbar.

Der Cayleygraph der freien Gruppe mit zwei Erzeugern a und b

Beispiele

Cayley-Graphen unendlicher Gruppen ${\displaystyle \Gamma }$ sind Beispiele unendlicher Graphen mit sehr hoher Symmetrie. (Alle Elemente der Gruppe ${\displaystyle \Gamma }$ sind Symmetrien des Graphen.)

In vielen inner- und außermathematischen Anwendungen sind Expander-Graphen von Bedeutung.

Lokal endliche Graphen

Ein Graph heißt lokal endlich, wenn jeder Knoten nur endlich viele Nachbarn hat.

Farey-Graph: Knoten entsprechen ${\displaystyle \mathbb {Q} \cup \infty }$, die Kante ${\displaystyle (p/q,r/s)}$ existiert falls ${\displaystyle |ps-rq|=1}$

Feine Graphen

Eine in der geometrischen Gruppentheorie wichtige Klasse von Graphen sind feine Graphen, sie umfassen lokal endliche Graphen und zum Beispiel den Farey-Graph.

Anwendung

In der Funktionalanalysis treten unendliche Graphen als sogenannte Bratteli-Diagramme bei der Untersuchung von AF-C*-Algebren auf.

Sätze

Zu den Sätzen über endliche Graphen, die Erweiterungen auf unendliche Graphen haben, gehören:

• der Heiratssatz von Philip Hall, bewiesen von Ron Aharoni, Crispin Nash-Williams und Saharon Shelah.[1][2][3] Ebenso auf den unendlichen Fall übertragbar sind die Verallgemeinerung des Heiratssatzes von Richard Rado und der Satz von Dilworth.
• Der Satz von König, wie schon Paul Erdős vermutete und wie Aharoni bewies.[4][5]
• der Satz von Menger, bewiesen von Aharoni und Eli Berger.[6]

Literatur

• Dénes Kőnig: Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe, Akademische Verlagsgesellschaft, Leipzig 1936
• Reinhard Diestel: Infinite graphs, Kapitel 8 in Reinhard Diestel: Graph theory. 4th [electronic] edition 2010. Corrected reprint 2012, Springer, 2012, ISBN 978-3-642-14278-9, S. 203–268 (englisch; Inhaltsverzeichnis)

Einzelnachweise

1. R. Aharoni, C. S. J. A. Nash-Williams, S. Shelah,. Marriage in infinite societies, in: Progress in Graph Theory (Waterloo, Ontario, 1982), Academic Press, Toronto, 1984, S. 71–79
2. R. Aharoni, C. S. J. A. Nash-Williams, S. Shelah, A general criterion for the existence of transversals, Proceedings of the London Mathematical Society, Band 3, 1983, S. 43–68.
3. R. Aharoni, C. S. J. A. Nash-Williams, S. Shelah, Another Form of a Criterion for the Existence of Transversals, Journal of the London Mathematical Society, Band 2, 1984, S. 193–203
4. Aharoni, König's duality theorem for infinite bipartite graphs, Journal of the London Mathematical Society, Band 2, 1984, S. 1–12
5. Aharoni, On a duality principle in infinite bipartite graphs, Journal of the London Mathematical Society, Band 2, 1983, S. 385–392
6. R. Aharoni, E. Berger, Menger’s theorem for infinite graphs, Inventiones Mathematicae, Band 176, 2009, S. 1–62