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)