Feiner Graph

Farey-Graph

In der Graphentheorie, einem Teilgebiet der Mathematik, sind feine Graphen eine Klasse von Graphen mit gewissen lokalen Endlichkeitseigenschaften. Feine Graphen spielen eine Rolle in der geometrischen Gruppentheorie, insbesondere im Zusammenhang mit Hyperbolizität und relativer Hyperbolizität von Graphen und Gruppen.

Definition

Ein Graph $K=(V,E)$ heißt fein, wenn er eine (und damit jede) der folgenden äquivalenten Bedingungen erfüllt:

• Für jede Kante $e\in E$ und jedes $n\in \mathbb {N}$ gibt es nur endlich viele durch $e$ verlaufende Kreise der Länge $n$.
• Für alle Knoten $x,y\in V$ und jedes $n\in \mathbb {N}$ gibt es nur endlich viele $x$ und $y$ verbindende Wege ohne sich wiederholende Knoten.
• Für alle $x,y\in V,n\in \mathbb {N}$ gibt es keine unendliche Menge $x$ und $y$ verbindender paarweise unabhängiger Wege ohne sich wiederholende Knoten der Länge $n$. (Hierbei heißen zwei Wege unabhängig, wenn sie nur Anfangs- und Endpunkt gemeinsam haben.)
• Wenn $x,y\in V$ ein Paar unterschiedlicher Knoten und $n\in \mathbb {N}$ ist und ${\mathcal {L}}$ eine kanten-endliche Menge zusammenhängender Teilgraphen von $K$, die alle jeweils $n$ Knoten haben und $x$ und $y$ enthalten, dann muss ${\mathcal {L}}$ endlich sein. (Hierbei heißt eine Menge ${\mathcal {L}}$ kantenendlich, wenn jede Kante $e\in E$ nur in endlich vielen Teilgraphen aus ${\mathcal {L}}$ enthalten ist.)
• Für jeden Knoten $x\in V$ ist die Nachbarschaft $N_{K}(x)$ lokal endlich in $K-\left\{x\right\}$. (Das heißt, jeder Knoten in $N_{K}(x)$ ist in $K-\left\{x\right\}$ nur zu endlich vielen Knoten aus $N_{K}(x)$ adjazent.)

Beispiele

• Lokal endliche Graphen sind fein.
• Der Farey-Graph ist fein.

Literatur

• Brian Bowditch: Relatively hyperbolic groups. (PDF) In: Internat. J. Algebra Comput.. 22, Nr. 3, 2012. ., Abschnitt 2