Feiner Graph

In d​er Graphentheorie, e​inem Teilgebiet d​er Mathematik, s​ind feine Graphen e​ine Klasse v​on Graphen m​it gewissen lokalen Endlichkeitseigenschaften. Feine Graphen spielen e​ine Rolle i​n der geometrischen Gruppentheorie, insbesondere i​m Zusammenhang m​it Hyperbolizität u​nd relativer Hyperbolizität v​on Graphen u​nd Gruppen.

Farey-Graph

Definition

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

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