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.

Farey-Graph

Definition

Bearbeiten

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

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

Beispiele

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

Literatur

Bearbeiten